题面

给一个序列 \(s\) ，回答 \(Q\) 个这样的询问：\(s\) 的左端点在 \([a,b]\) 中，右端点在 \([c,d]\) 中的子区间的最大中位数。

题解

首先要知道中位数怎么求：

二分出一个 \(mid\) ，判断中位数 \(m\) 与 \(mid\) 的大小关系。将询问区间 \([l,r]\) 内所有 \(s_i < mid\) 赋值为 \(-1\) ，\(s_i\geq mid\) 赋值为 \(1\) ，令 \(sum=\sum_{i=l}^rs_i\) 分类讨论：

  • 若 \(sum \geq 0\) ，则 \(m \geq mid\) 。
  • 若 \(sum<0\) ，则 \(m<mid\) 。

但是由于本题询问的区间不固定，上面的做法就需要改动。

题目中要求 \(m\) 最大，所以对于一个值 \(mid\) ，我们要让 \(sum\) 尽量大，而区间 \([b+1,c-1]\) 的 \(sum\) 是一定的，所以等价于区间 \([a,b],[c,d]\) 的 \(sum\) 尽量大，这相当于求区间 \([a,b]\) 和最大的后缀与区间 \([c,d]\) 和最大的前缀（这里的前缀后缀长度都不为 \(0\) ）。

然后就有一个做法了：对于离散化后中位数可能取到的每一个值开一棵线段树，维护区间和 \(sum\) 、最大前缀和 \(lsum\) 、最大后缀和 \(rsum\) 。但是这样空间复杂度有 \(O(n^2 {\rm{log}}n)\) ，显然爆炸。

不难发现值 \(x\) 对应的线段树与值 \(x+1\) 对应的线段树差别不大，也就是说我们记录了很多重复信息。显然，由 \(x\) 到 \(x+1\) ，只有原序列中值为 \(x\) 的数对应的值由 \(1\) 变为了 \(-1\) ，这里就可以用一个类似主席树的东西继承值 \(x\) 对应的线段树上的信息。

用 \(\text{vector}\) 记录每个值的出现位置，每次以上一次修改为模板进行修改。

\(\text{Code}:\)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#define maxn 20005
#define Rint register int
#define INF 0x3f3f3f3f
using namespace std;
typedef long long lxl;

template <typename T>
inline T read()
{
    T x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}

int n,m,Q;
int A[maxn],B[maxn];
std::vector<int> P[maxn];
int rt[maxn];

struct Segment_Tree
{
    struct node
    {
        int sum,lsum,rsum;
        node(int x=0){sum=lsum=rsum=x;}
        inline node operator + (const node &T)const
        {
            node res;
            res.sum=sum+T.sum;
            res.lsum=max(lsum,sum+T.lsum);
            res.rsum=max(T.rsum,T.sum+rsum);
            return res;
        }
    }tree[maxn<<5];
    int tot,ch[maxn<<5][2];
    inline int build(int l,int r,int d)
    {
        int p=++tot;
        if(l==r) {tree[p]=node(A[l]>=d?1:-1);return p;}
        int mid=(l+r)>>1;
        ch[p][0]=build(l,mid,d);
        ch[p][1]=build(mid+1,r,d);
        tree[p]=tree[ch[p][0]]+tree[ch[p][1]];
        return p;
    }
    inline int update(int l,int r,int pos,int tmp)
    {
        int p=++tot;
        tree[p]=tree[tmp];
        ch[p][0]=ch[tmp][0];ch[p][1]=ch[tmp][1];
        if(l==r) {tree[p]=node(-1);return p;}
        int mid=(l+r)>>1;
        if(pos<=mid)
            ch[p][0]=update(l,mid,pos,ch[tmp][0]);
        else
            ch[p][1]=update(mid+1,r,pos,ch[tmp][1]);
        tree[p]=tree[ch[p][0]]+tree[ch[p][1]];
        return p;
    }
    inline node query(int p,int l,int r,int L,int R)
    {
        if(L<=l&&r<=R) return tree[p];
        int mid=(l+r)>>1;
        if(R<=mid) return query(ch[p][0],l,mid,L,R);
        else if(L>mid) return query(ch[p][1],mid+1,r,L,R);
        else return query(ch[p][0],l,mid,L,R)+query(ch[p][1],mid+1,r,L,R);
    }
}st;

int a,b,c,d;

inline int check(int mid)
{
    int res=0;
    if(b+1<=c-1) res+=st.query(rt[mid],1,n,b+1,c-1).sum;
    res+=st.query(rt[mid],1,n,a,b).rsum;
    res+=st.query(rt[mid],1,n,c,d).lsum;
    return res;
}

int main()
{
    // freopen("P2839.in","r",stdin);
    n=read<int >();
    for(int i=1;i<=n;++i)
        A[i]=B[i]=read<int >();
    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;
        P[A[i]].push_back(i);
    }
    rt[1]=st.build(1,n,1);
    for(int i=2;i<=m;++i)
    {
        rt[i]=rt[i-1];
        for(vector<int>::iterator it=P[i-1].begin();it!=P[i-1].end();++it)
            rt[i]=st.update(1,n,*it,rt[i]);
    }
    int x=0,q[4];
    Q=read<int >();
    while(Q--)
    {
        q[0]=(read<int >()+x)%n+1,q[1]=(read<int >()+x)%n+1;
		q[2]=(read<int >()+x)%n+1,q[3]=(read<int >()+x)%n+1;
		sort(q,q+4);
		a=q[0],b=q[1],c=q[2],d=q[3];
        int l=1,r=m,res=-1;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(check(mid)>=0) res=mid,l=mid+1;
            else r=mid-1;
        }
        printf("%d\n",x=B[res]);
    }
    return 0;
}