连续子段的差异

题目

给出一个长度为n的数列,求有几个区间满足:区间内最大值-最小值<=k。(1<=n<=5e4,0<=k<=1e9,0<=a[i]<=1e9)

思路

用两个单调队列,一个记录区间最大值,一个记录区间最小值。
若一个区间满足条件,那它的子区间也满足条件。
两个指针l,r表示当前枚举的可行区间。
枚举r,再不断调整l,使这个区间可行,此时答案加上r-l+1。
为什么加上r-l+1就不会少也不会重复呢?
因为此时区间[l,r],[l+1,r]…[r,r]都是可行的,并不与之前重复。
(代码中的l有点不一样,所以不是加r-l+1,而是加r-l)

代码

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
#include<bits/stdc++.h>
using namespace std;
#define getchar() ((p1==p2?p1=bf,p2=bf+fread(bf,1,1<<21,stdin),p1:p1)==p2?EOF:*p1++)
#define rgt register
char bf[1 << 21], *p1, *p2;
template<typename T>
inline T read( rgt T &x ){ x = 0; rgt char aa=getchar();
while(aa<'0'||aa>'9') aa=getchar();
while(aa>='0'&&aa<='9') x=(x<<3)+(x<<1)+aa-'0',aa=getchar();
} //以上快读为机房大佬给我加的
const int maxn=5e4+7;
int n,k,a[maxn],ans;
deque<int>q1,q2;
int main(){
read(n),read(k);
for(rgt int i=1;i<=n;i++) read(a[i]);
int l=0;
for(rgt int r=1;r<=n;r++){
while(q1.size()&&a[r]>=a[q1.back()]) q1.pop_back();//维护最大值
while(q2.size()&&a[r]<=a[q2.back()]) q2.pop_back();//维护最小值
q1.push_back(r),q2.push_back(r);//压入当前的位置
while(a[q1.front()]-a[q2.front()]>k)//调整l,使区间可行。
if(q1.front()<q2.front()) l=q1.front(),q1.pop_front();
else l=q2.front(),q2.pop_front();//选下标靠前的那个
ans+=r-l;//记录答案
}
printf("%d\n",ans);
return 0;
}

结束,又水了一题(哈哈),谢谢!!