【2021牛客暑期多校训练营5】K King of Range（单调队列）

K King of Range

题意：

• 给出一个长为n的序列，m次操作，每次操作求对于一个指定的k，原序列存在多少个连续子序列，满足该区间内最大值减最小值严格大于k。

思路：

• 令 Ri 为 l=i 时，满足极差大于 k 的最小的 r，如果不存在则记 Ri = n+1。那么显然有 R1 ≤ R2 ≤ … ≤ Rn。
• 首先可以用 Set 之类的 STL 工具来快速维护极差，所以可以在均摊 O(log n) 的时间求 Ri。
• 一个线性的做法：注意到因为区间端点都是单调的，所以可以维护两个单调队列，其中一个递增序列，队首维护最小值，一个递减序列，队首维护最大值，每次弹出两个队列中队首靠前的一个，直到极差 ≤ k。那么就可以在均摊 O(1) 的时间内求 Ri 了。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
LL a[maxn];
int main(){
	LL n, m;  cin>>n>>m;
	for(int i = 1; i <= n; i++)cin>>a[i];
	while(m--){
		LL k;  cin>>k;
		deque<LL>ma, mi;   //维护区间[l,i]的最大值和最小值，按顺序入队
		LL ans = 0, l = 1; //ans维护极差≤k的区间个数
		for(LL i = 1; i <= n; i++){
			while(ma.size()&&a[ma.back()]<a[i])ma.pop_back();//递减序列,队首维护最大值
			ma.push_back(i);
			while(mi.size()&&a[mi.back()]>a[i])mi.pop_back();//递增序列,队首维护最小值
			mi.push_back(i);
			while(mi.size()&&ma.size()&&a[ma.front()]-a[mi.front()]>k){
				if(ma.front()==l)ma.pop_front();
				if(mi.front()==l)mi.pop_front();
				l++;
			}
			ans += i-l+1;//如果a[l..i]满足条件,其(i-l+1)个子数组都满足条件
		}
		cout<<n*(n+1)/2-ans<<"\n";
	}
	return 0;
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/119782440