记录编号	463495	评测结果	AAAAAAAAAA
题目名称	beautiful序列	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	1.494 s
提交时间	2017-10-24 11:10:47	内存使用	0.36 MiB

# include "iostream"
# include "stdio.h"
# include "algorithm"
# include "math.h"
# include "string.h"
# include "queue"
# define maxn 2005
# define inf 0x3fffffff
using namespace std;
int n,q,l,r,w[maxn];//,ans[maxn][maxn];
struct nodeL{int w,id;bool operator<(nodeL A) const{return w==A.w?id<A.id:w<A.w;}};//堆顶大元素
struct nodeR{int w,id;bool operator<(nodeR A) const{return w==A.w?id>A.id:w>A.w;}};//堆顶小元素
int maxx[maxn],gmax[maxn*4];
void search(int x){
	 //ans[x][x]=w[x];
	 int now=w[x],id=x;
     maxx[x]=max(maxx[x],1);
	 priority_queue<nodeL> L;
	 priority_queue<nodeR> R;
	 while(!L.empty()) L.pop();
	 while(!R.empty()) R.pop();
     for(int i=x+2;i<=n;i+=2){
     	 int a=w[i],b=w[i-1],ida=i,idb=i-1;
     	 if(a>=now&&b>=now){
     	    nodeL A; 
     	    A.w=now,A.id=id;L.push(A);
     	 	nodeR B,C,D;
     	 	B.w=a,B.id=ida;R.push(B);
     	 	C.w=b,C.id=idb;R.push(C);
     	 	D=R.top();R.pop();
     	 	now=D.w,id=D.id;
     	 	//ans[x][i]=now;
     	 	maxx[id]=max(maxx[id],i-x+1);
     	    continue;
     	 }
     	 if(a<now&&b<now){
     	 	nodeR A;
     	 	A.w=now,A.id=id;R.push(A);
     	 	nodeL B,C,D;
     	 	B.w=a,B.id=ida;L.push(B);
     	 	C.w=b,C.id=idb;L.push(C);
     	 	D=L.top();L.pop();
     	 	now=D.w,id=D.id;
     	 	//ans[x][i]=now;
     	 	maxx[id]=max(maxx[id],i-x+1);
     	 	continue;
     	 }
     	 if(a<now&&b>=now){
     	 	nodeL A; nodeR B;
     	 	A.w=a,A.id=ida;
     	 	B.w=b,B.id=idb;
     	 	L.push(A);
     	 	R.push(B);
     	 	//ans[x][i]=now;
     	 	maxx[id]=max(maxx[id],i-x+1);
     	 	continue;
     	 }
     	 if(a>=now&&b<now){
     	 	nodeL A; nodeR B;
     	 	A.w=b,A.id=idb;
     	 	B.w=a,B.id=ida;
     	 	L.push(A);
     	 	R.push(B);
     	 	//ans[x][i]=now;
     	 	maxx[id]=max(maxx[id],i-x+1);
     	 	continue;
     	 }
     }
}
void buildtree(int l,int r,int rt){
	 if(l==r){
	 	gmax[rt]=maxx[l];
	 	return;
	 }int mid=(l+r)>>1;
	 buildtree(l,mid,rt*2);
	 buildtree(mid+1,r,rt*2+1);
	 gmax[rt]=max(gmax[rt*2],gmax[rt*2+1]);
}
int query(int l,int r,int rt,int L,int R){
	if(L<=l&&R>=r) return gmax[rt];
	int mid=(l+r)>>1,ret=-inf;
	if(mid>=L) ret=max(ret,query(l,mid,rt*2,L,R));
	if(R>mid) ret=max(ret,query(mid+1,r,rt*2+1,L,R));
	return ret;
}
int main(){
	freopen("abeautiful.in","r",stdin);
	freopen("abeautiful.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    for(int i=1;i<=n;i++) search(i);
    buildtree(1,n,1);
    scanf("%d",&q);
    while(q--){
    	  scanf("%d%d",&l,&r);
    	  printf("%d\n",query(1,n,1,l,r));
    }    
}

/*
8
16 19 7 8 9 11 20 16
8
3 8
1 4
2 3
1 1
5 5
1 2
2 8
7 8
*/