Lvat_s Blog

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;
}