CLJ的题目真是猛……我调了一个晚上……才发现是开始的排序出了问题……真是……人弱没办法……
二分+可持久化线段树。
#include<cstdio> #include<algorithm> using namespace std; int n,Q,a[20005],b[20005],m,root[20005],cnt,ms[4],ans; pair<int,int> s[20005]; struct SegTree{ int nl,nr,cnt,lx,rx; }tree[1000005]; void OutNode(SegTree d){ puts("\nThis is a SegTree Node:"); printf("nl:%d nr:%d cnt:%d lx:%d rx:%d\n\n",d.nl,d.nr,d.cnt,d.lx,d.rx); } void OutTree(int l,int r,int root){ printf("%d %d The Tree:%d %d %d\n",l,r,tree[root].lx,tree[root].cnt,tree[root].rx); if(l==r)return; int mid=l+r>>1; OutTree(l,mid,tree[root].nl); OutTree(mid+1,r,tree[root].nr); } void Pushup(int root){ tree[root].lx=max(tree[tree[root].nl].lx,tree[tree[root].nl].cnt+tree[tree[root].nr].lx); tree[root].rx=max(tree[tree[root].nr].rx,tree[tree[root].nr].cnt+tree[tree[root].nl].rx); tree[root].cnt=tree[tree[root].nl].cnt+tree[tree[root].nr].cnt; } void Build(int l,int r,int &root){ root=++cnt; if(l==r){ tree[root].lx=1; tree[root].rx=1; tree[root].cnt=1; tree[root].nl=0; tree[root].nr=0; //printf("--------------------L:%d\n",l); return; } int mid=l+r>>1; Build(l,mid,tree[root].nl); Build(mid+1,r,tree[root].nr); Pushup(root); return; } void Update(int l,int r,int &root,int lastroot,int pos){ root=++cnt; tree[root].nl=tree[lastroot].nl; tree[root].nr=tree[lastroot].nr; if(l==r){ tree[root].cnt=-1; tree[root].lx=-1; tree[root].rx=-1; //printf("----------------------R:%d\n",tree[root].rx); return; } int mid=l+r>>1; if(pos<=mid)Update(l,mid,tree[root].nl,tree[lastroot].nl,pos); else Update(mid+1,r,tree[root].nr,tree[lastroot].nr,pos); Pushup(root); } SegTree Ask(int root,int l,int r,int L,int R){ if(l>r)return tree[0]; if(L>=l && R<=r)return tree[root]; int mid=L+R>>1; SegTree a=tree[0],b=tree[0]; if(l>mid)return Ask(tree[root].nr,l,r,mid+1,R); if(r<=mid)return Ask(tree[root].nl,l,r,L,mid); a=Ask(tree[root].nl,l,r,L,mid); b=Ask(tree[root].nr,l,r,mid+1,R); SegTree c; c.lx=max(a.lx,a.cnt+b.lx); c.rx=max(b.rx,b.cnt+a.rx); c.cnt=a.cnt+b.cnt; //OutNode(c); return c; } int Query(){ int l=1,r=n+1,Ans=0; while(l<r){ int mid=l+r>>1; SegTree a=Ask(root[mid],ms[0],ms[1],1,m),b=Ask(root[mid],ms[1]+1,ms[2]-1,1,m),c=Ask(root[mid],ms[2],ms[3],1,m); //OutTree(1,n,root[mid]); //printf("MID:%d %d %d %d %d\n",mid,root[mid],a.rx,b.cnt,c.lx); int sum=a.rx+b.cnt+c.lx; if(sum>=0)l=mid+1,Ans=mid; else r=mid; } return Ans; } int main(){ //freopen("2653.in","r",stdin); //freopen("2653.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); b[i]=a[i]; } sort(b+1,b+n+1); m=unique(b+1,b+n+1)-b-1; for(int i=1;i<=n;i++){a[i]=lower_bound(b+1,b+m+1,a[i])-b;s[i].first=a[i];s[i].second=i;/*printf("Ai:%d\n",a[i]);*/} sort(s+1,s+n+1); //for(int i=1;i<=n;i++)printf("Si:%d\n",s[i].second); Build(1,m,root[1]); for(int i=2;i<=n;i++)Update(1,m,root[i],root[i-1],s[i-1].second); scanf("%d",&Q); while(Q--){ scanf("%d %d %d %d",&ms[0],&ms[1],&ms[2],&ms[3]); ms[0]=(ms[0]+ans)%n+1; ms[1]=(ms[1]+ans)%n+1; ms[2]=(ms[2]+ans)%n+1; ms[3]=(ms[3]+ans)%n+1; sort(ms,ms+4); //printf("MS:%d %d %d %d\n",ms[0],ms[1],ms[2],ms[3]); ans=b[Query()]; //printf("QUERY:%d\n",Query()); printf("%d\n",ans); } return 0; }