BZOJ 1342 [Baltic2007]Sound静音问题

题目大意

给你一个序列，求其有哪些子序列使得这个子序列中的最大值-最小值<阈(yù)值。

经典set单调队列题。这题放到考场谁敢写set啊……

单调队列也不是很难，不过数组开小是什么鬼= =

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,c,a[1000010],minh=1,maxh=1,mint,maxt,qmin[1000010],qmax[1000010],ans[1000010],tot;
void init()
{
	for(int i=1;i<=m;++i)
	{
		while(maxh<=maxt&&a[qmax[maxt]]<a[i]) maxt--;
		while(minh<=mint&&a[qmin[mint]]>a[i]) mint--;
		qmax[++maxt]=i;
		qmin[++mint]=i;
	}
	if(a[qmax[maxh]]-a[qmin[minh]]<=c) ans[++tot]=1;
}
int main()
{
	scanf("%d%d%d",&n,&m,&c);
	for(int i=1;i<=n;++i) scanf("%d",a+i);
	init();
	for(int i=2;i+m-1<=n;++i)
	{
		while(maxh<=maxt&&qmax[maxh]<i) ++maxh;
		while(minh<=mint&&qmin[minh]<i) ++minh;
		while(maxh<=maxt&&a[qmax[maxt]]<a[i+m-1]) maxt--;
		while(minh<=mint&&a[qmin[mint]]>a[i+m-1]) mint--;
		qmax[++maxt]=i+m-1;
		qmin[++mint]=i+m-1;
		if(abs(a[qmax[maxh]]-a[qmin[minh]])<=c) ans[++tot]=i;
	}
	if(tot) for(int i=1;i<=tot;++i) printf("%d\n",ans[i]);
	else printf("NONE\n");
	return 0;
}