连续子段的差异

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

题目

给出一个长度为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;
}

结束，又水了一题（哈哈），谢谢！！