由于查询区间长度固定，所以ST可以省掉一维
测试结果吓尿我了，比用deque的单调队列还快。。。
是我单调队列写渣了吗。。。。
CODE:
#include<cstdio>

const int maxn=1010000;
int n,m,d[maxn],dx[maxn],di[maxn],i,j;

inline int max(int a,int b)
{ return a>b?a:b; }
inline int min(int a,int b)
{ return a<b?a:b; }
int main() {
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++) scanf("%d",d+i);
	for(i=0;i<n;i++) dx[i]=di[i]=d[i];
	for(j=1;j*2<m;j*=2)
		for(i=0;i+j<n;i++) {
			dx[i]=max(dx[i],dx[i+j]);
			di[i]=min(di[i],di[i+j]);
		}
	for(i=0;i+m<=n;i++)
		printf("%d ",min(di[i],di[i+m-j]));
	printf("\n");
	for(i=0;i+m<=n;i++)
		printf("%d ",max(dx[i],dx[i+m-j]));
	printf("\n");
	return 0;
}

• Re:用一维的ST算法比用deque的单调队列还快！！！！ (6) leeleeon 2014-01-21 11:37:50