记录编号	258236	评测结果	AAAAAAAAA
题目名称	495.[POJ 2823]滑动窗口	最终得分	100
用户昵称	洛克索耶夫	是否通过	通过
代码语言	C++	运行时间	4.989 s
提交时间	2016-05-05 11:00:53	内存使用	194.90 MiB

#include<bits/stdc++.h>

int n,q;
int rmax[1000200][25],rmin[1000200][25],a[1000200];

inline int GetMax(const int& a, const int& b)
{
	return a>b?a:b;
}

inline int GetMin(const int& a, const int& b)
{
	return a<b?a:b;
}

int Read()
{
	int a=0,minus=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')	minus=-1;
		ch=getchar();
	}	
	while(ch>='0'&&ch<='9'){
		a=a*10+ch-'0';
		ch=getchar();
	}
	return a*minus;
}

int RmqInit()
{
	int m=log(n*1.0)/log(2.0);
	//换底公式,因为log(a)默认是以e为底a的对数
	//loga(b)=logc(b)/logc(a) 
	//log2(8)=ln(8)/ln(2) 
	for(int j=1;j<=m;j++)
		for(int i=1;i<=n;i++){
			rmax[i][j]=rmax[i][j-1];
			rmin[i][j]=rmin[i][j-1];
			int k=1<<(j-1);	
			if(i+k<=n){
				rmax[i][j]=GetMax(rmax[i][j-1],rmax[i+k][j-1]);
				rmin[i][j]=GetMin(rmin[i][j-1],rmin[i+k][j-1]);
				//类似动规 
			}	
		}
}

inline int RmqMax(const int& s, const int& t)
{
	int m=log((t-s+1)*1.0)/log(2.0);
	int k=1<<m;
	return GetMax(rmax[s][m],rmax[t-k+1][m]);
	//中间可以有部分重复 
} 

inline int RmqMin(const int& s, const int& t)
{
	int m=log((t-s+1)*1.0)/log(2.0);//转换成double 
	int k=1<<m;
	return GetMin(rmin[s][m],rmin[t-k+1][m]);
	//中间可以有部分重复 
} 

void Init()
{
	n=Read(),q=Read();
	for(int i=1;i<=n;i++){
		a[i]=Read();
		rmax[i][0]=a[i];
		rmin[i][0]=a[i];
		//rmax[i][j]:从i开始,长度为2的j次方的一段元素的最值 
	}
	RmqInit();
	int s,t;
	for(t=q;t<=n;t++){
		s=t-q+1;
		printf("%d ",RmqMin(s,t));
	}
	printf("\n");
	for(t=q;t<=n;t++){
		s=t-q+1;
		printf("%d ",RmqMax(s,t));
	}	
}

int main()
{
	freopen("window.in","r",stdin);
	freopen("window.out","w",stdout);
	Init();
	return 0;
}