学步园

首先膜拜clj。。。

这道题初看没头绪，看了诸多题解后，发现时先二分，在把大于等于它的为1，小于它的为-1，一段区间最大连续和非负就行

然后想了N久都没想通，终于，在昨天在外拜年时想通了，就是以每个数建可持久化线段树，然后维护sum,lsum,rsum这样初始化就nlogn，每次询问log2n，总复杂度O(Qlog2n+nlongn)；代码写得还是蛮短的，就是怎么搞都只是rank 6。。。

#include<cstdio>
#include<iostream>
#include<algorithm>
#define Ls p->lson
#define Rs p->rson
#define Lson (Ls==nol?Ls=t+(++tot):Ls),l,mid
#define Rson (Rs==nol?Rs=t+(++tot):Rs),mid+1,r
using namespace std;
const int maxn=20011,maxt=maxn*30;
inline int get(){
    int tmp=0;char ch;
    while(ch=getchar())if('0'<=ch&&ch<='9')break;
    for(;'0'<=ch&&ch<='9';ch=getchar())tmp=tmp*10+ch-'0';
    return tmp;
}
int n;
int a[maxn];
void init(){
    n=get();
    for (int i=1;i<=n;++i) a[i]=get();
}
struct Tree{
    int lsum,rsum,sum;
    Tree *lson,*rson;
}t[maxt],*nol;
void initialize(Tree &x){x.lson=nol;x.rson=nol;}
void update(Tree *p){
    p->sum=Ls->sum+Rs->sum;
    p->lsum=max(Ls->lsum,Ls->sum+Rs->lsum);
    p->rsum=max(Rs->rsum,Rs->sum+Ls->rsum);
}
int tot;
void build(Tree *p,int l,int r){
    if (l==r){p->lsum=p->rsum=p->sum=1;return;}
    int mid=(l+r)>>1;
    build(Lson);build(Rson);
    update(p);
}
void ins(Tree *pre,Tree *p,int l,int r,int m){
    if (l==r){p->lsum=p->rsum=p->sum=-1;return;}
    int mid=(l+r)>>1;
    if (m<=mid){Rs=pre->rson;ins(pre->lson,Lson,m);}
    else{Ls=pre->lson;ins(pre->rson,Rson,m);}
    update(p);
}
inline bool cmp(int *x,int *y){return *x<*y;}
int *p[maxn];
void prepare(){
    for (int i=n*30;i>=0;--i) initialize(t[i]);
    for (int i=1;i<=n;++i) p[i]=a+i;
    sort(p+1,p+n+1,cmp);tot=n;
    build(t,1,n);
    for (int i=1;i<=n;++i)
        ins(t+(i-1),t+i,1,n,p[i]-a);
}
int Querys(Tree *p,int l,int r,int x,int y){
    if (x>y) return 0;
    if (l>=x && r<=y) return p->sum;
    int tmp=0,mid=(l+r)>>1;
    if (x<=mid) tmp+=Querys(Lson,x,y);
    if (y>mid) tmp+=Querys(Rson,x,y);
    return tmp;
}
int ll,sum,rr;
void Queryl(Tree *p,int l,int r,int x,int y){
    if (l>=x && r<=y){
        ll=max(ll,sum+p->lsum);sum+=p->sum;return;
    }
    int mid=(l+r)>>1;
    if (x<=mid) Queryl(Lson,x,y);
    if (y>mid) Queryl(Rson,x,y);
}
void Queryr(Tree *p,int l,int r,int x,int y){
    if (l>=x && r<=y){
        rr=max(rr,sum+p->rsum);sum+=p->sum;return;
    }
    int mid=(l+r)>>1;
    if (y>mid) Queryr(Rson,x,y);
    if (x<=mid) Queryr(Lson,x,y);
}
int q[5];
bool check(int x){
    sum=0;ll=-1;Queryl(t+x,1,n,q[2],q[3]);
    sum=0;rr=-1;Queryr(t+x,1,n,q[0],q[1]);
    int tmp=Querys(t+x,1,n,q[1]+1,q[2]-1);
    return ll+rr+tmp>=0;
}
int binary(){
    int l=1,r=n;
    while (l<=r){
        int mid=(l+r)>>1;
        if (check(mid-1)) l=mid+1;
        else r=mid-1;
    }
    return *p[l-1];
}
void work(){
    prepare();
    int x=0;
    int m=get();
    while (m--){
        for (int i=0;i<4;++i) q[i]=(get()+x)%n+1;
        sort(q,q+4);
        printf("%d\n",x=binary());
    }
}
int main(){
    init();
    work();
    return 0;
}