题目大意

给你一个序列,多次询问左端点在$[a,b]$,右端点在$[c,d]$的子序列的最大的中位数。


二分中位数,把大于等于中位数的看作1,小于的看作-1,于是问题转化成了求一段子序列的和大于等于0.

对于$[b,c]$这段区间可以直接求和,但是对于$[a,b]$,$[c,d]$却无从下手。

考虑用主席树维护,初始令所有数都为1,之后从小到大赋值为-1.维护一段区间包含左端点/右端点的最大区间和和整个区间的和,在查询的时候查询对应区间即可。

注意修改的时候是单点修改……线段树维护的是该区间而不是前缀和。

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int ri()
{
    int ret=0;char tmp=nc();
    while(!isdigit(tmp)) tmp=nc();
    while(isdigit(tmp)) ret=ret*10+(tmp-'0'),tmp=nc();
    return ret;
}
struct element{int id,vl;}e[20100];
bool cmp(const element &x,const element &y){return x.vl<y.vl;}
int n,m,q[4],la;
int sum[1000010],lsm[1000010],rsm[1000010],ls[1000010],rs[1000010],rt[1000010],pts;
int a[20010],b[20010],tot;
void pushup(int pos)
{
    sum[pos]=sum[ls[pos]]+sum[rs[pos]];
    lsm[pos]=max(lsm[ls[pos]],sum[ls[pos]]+lsm[rs[pos]]);
    rsm[pos]=max(rsm[rs[pos]],sum[rs[pos]]+rsm[ls[pos]]);
}
void build(int &pos,int l,int r)
{
    pos=++pts;
    if(l==r)
    {
        sum[pos]=lsm[pos]=rsm[pos]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(ls[pos],l,mid),build(rs[pos],mid+1,r);
    pushup(pos);
}
void update(int lp,int &rp,int l,int r,int x)
{
    rp=++pts;
    if(l==r)
    {
        sum[rp]=lsm[rp]=rsm[rp]=-1;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) update(ls[lp],ls[rp],l,mid,x),rs[rp]=rs[lp];
    else update(rs[lp],rs[rp],mid+1,r,x),ls[rp]=ls[lp];
    pushup(rp);
}
void qyl(int pos,int l,int r,int x,int y)
{
    if(x<=l&&r<=y) {++tot,a[tot]=lsm[pos],b[tot]=sum[pos];return;}
    int mid=(l+r)>>1;
    if(x<=mid) qyl(ls[pos],l,mid,x,y);
    if(y>mid) qyl(rs[pos],mid+1,r,x,y);
}
void qyr(int pos,int l,int r,int x,int y)
{
    if(x<=l&&r<=y) {++tot,a[tot]=rsm[pos],b[tot]=sum[pos];return;}
    int mid=(l+r)>>1;
    if(y>mid) qyr(rs[pos],mid+1,r,x,y);
    if(x<=mid) qyr(ls[pos],l,mid,x,y);
}
int ql(int z,int x,int y)
{
    int i,ret=-0x3f3f3f3f;
    tot=0;
    qyl(rt[z],1,n,x,y);
    a[0]=b[0]=0;
    for(i=1;i<=tot;++i) ret=max(ret,b[i-1]+a[i]),b[i]+=b[i-1];
    return ret;
}
int qr(int z,int x,int y)
{
    int i,ret=-0x3f3f3f3f;
    tot=0;
    qyr(rt[z],1,n,x,y);
    a[0]=b[0]=0;
    for(i=1;i<=tot;++i) ret=max(ret,b[i-1]+a[i]),b[i]+=b[i-1];
    return ret;
}
int qs(int pos,int l,int r,int x,int y)
{
    if(x>y) return 0;
    if(x<=l&&r<=y) return sum[pos];
    int mid=(l+r)>>1,ret=0;
    if(x<=mid) ret+=qs(ls[pos],l,mid,x,y);
    if(y>mid) ret+=qs(rs[pos],mid+1,r,x,y);
    return ret;
}
int bisection(int a,int b,int c,int d)
{
    int l=0,r=n+1,mid;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(qr(mid,a,b)+ql(mid,c,d)+qs(rt[mid],1,n,b+1,c-1)>=0) l=mid+1;
        else r=mid;
    }
    return e[l].vl;
}
int main()
{
    int i;
    n=ri();
    for(i=1;i<=n;++i) e[i].id=i,e[i].vl=ri();
    build(rt[0],1,n);
    sort(e+1,e+n+1,cmp);
    for(i=1;i<=n;++i) update(rt[i-1],rt[i],1,n,e[i].id);
    m=ri();
    while(m--)
    {
        q[0]=(ri()+la)%n,q[1]=(ri()+la)%n,q[2]=(ri()+la)%n,q[3]=(ri()+la)%n;
        sort(q,q+4);
        printf("%d\n",la=bisection(q[0]+1,q[1]+1,q[2]+1,q[3]+1));
    }
    return 0;
}