BZOJ2276 [Poi2011]Temperature

题面在这里

​

考虑枚举右端点

因为\(a_i\)递增的部分都可以取到，直接维护\(a_i\)递减的单调队列

​

示例程序：

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=1000005;
int n,l[maxn],r[maxn],que[maxn];
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d",&l[i],&r[i]);
	int ans=0,hed=1,til=0;
	for (int i=1;i<=n;i++){
		while (hed<=til&&l[que[hed]]>r[i]) hed++;
		ans=max(ans,i-que[hed-1]);
		while (hed<=til&&l[que[til]]<=l[i]) til--;
		que[++til]=i;
	}
	printf("%d",ans);
	return 0;
}