主席树爆零求调

#include<iostream>
#include<algorithm>
const int sz=2e4+10;
struct ST{
    struct vtype{
        int sum,maxl,maxr;
        vtype operator+(const vtype&a)const{
            vtype res;
            res.sum=sum+a.sum;
            res.maxl=std::max(maxl,sum+a.maxl);
            res.maxr=std::max(a.maxr,maxr+a.sum);
            return res;
        }
    };
    struct node{
        int lson,rson;
        vtype val={0,0,0};
    }tree[sz<<6];
    int num=0;
    void build(int &p,int ln,int rn){
        p=++num;
        if(ln==rn)return tree[p].val={1,1,1},void();
        int mid=ln+rn>>1;
        build(tree[p].lson,ln,mid);
        build(tree[p].rson,mid+1,rn);
        tree[p].val=tree[tree[p].lson].val+tree[tree[p].rson].val;
    }
    void modify(int&p,int srt,int ln,int rn,int pos){
        p=++num,tree[p]=tree[srt];
        if(ln==rn)return tree[p].val={-1,-1,-1},void();
        int mid=ln+rn>>1;
        if(pos<=mid)modify(tree[p].lson,tree[srt].lson,ln,mid,pos);
        else modify(tree[p].rson,tree[srt].rson,mid+1,rn,pos);
        tree[p].val=tree[tree[p].lson].val+tree[tree[p].rson].val;
    }
    vtype query(int p,int ln,int rn,int l,int r){
        if(ln>=l&&rn<=r)return tree[p].val;
        int mid=ln+rn>>1;
        if(l<=mid&&r>mid)
            return query(tree[p].lson,ln,mid,l,r)+query(tree[p].rson,mid+1,rn,l,r);
        if(l<=mid)return query(tree[p].lson,ln,mid,l,r);
        return query(tree[p].rson,mid+1,rn,l,r);
    }   
}st;
struct num{
    int val,id;
    bool operator<(const num&a)const{
        return val<a.val;
    }
}arr[sz];
int q[4],root[sz],n,m,carr[sz];
bool check(int k){
    int res=0;
    if(q[1]+1<q[2])res+=st.query(root[k],1,n,q[1]+1,q[2]-1).sum;
    res+=st.query(root[k],1,n,q[0],q[1]).maxr;
    res+=st.query(root[k],1,n,q[2],q[3]).maxl;
    return res>=0;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin>>n;
    for(int i=1;i<=n;i++)
        std::cin>>arr[i].val,arr[i].id=i,carr[i]=arr[i].val;
    std::sort(arr+1,arr+n+1);
    std::sort(carr+1,carr+n+1);
    int f=std::unique(carr+1,carr+n+1)-carr-1,x=1;
    for(int i=1;i<=n;i++)
        arr[i].val=std::lower_bound(carr+1,carr+f+1,arr[i].val)-carr;
    st.build(root[1],1,n);
    for(int i=2;i<=f;i++){
        root[i]=root[i-1];
        while(arr[x].val==i-1)
            st.modify(root[i],root[i],1,n,arr[x].id),x++;
    }
    int lans=0;
    std::cin>>m;
    while(m--){
        for(int i=0;i<4;i++)std::cin>>q[i],q[i]=(q[i]+lans)%n+1;
        std::sort(q,q+4);
        int l=1,r=f,res=-1;
        while(l<r){
            int mid=l+r>>1;
            if(check(mid))l=mid+1,res=mid;
            else r=mid-1;
        }
        lans=carr[res];
        std::cout<<lans<<"\n";
    }
    return 0;
}