链接
考虑区间的中位数为 (v) 应该满足什么条件。
让该区间中小于 (v) 的值等于 (-1)，大于等于 (v) 的值等于 (1)，若和大于等于 (0)，则该区间的中位数大于等于 (v)，否则小于 (v)。
（注意数的个数为偶数时，则取偏大的值作为中位数
所以我们可以二分答案，以权值为根，下标为叶子按上述方式储存前缀和建一棵主席树。
具体的，在根为 (rt_i) 的树中，序列里小于等于第 (i) 小值的为 (-1)，大于的为 (1)，储存其前缀和的最大值和最小值。
所以我们要维护的操作为区间最大值，区间最小值，区间修改，用标记永久化实现。
(code)（洛谷 (rk1)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define pb push_back
using namespace std;
const int N=2e4+3,inf=0x3f3f3f3f;
int n,m,num,cnt,ls[N*400],rs[N*400],Max[N*400],Min[N*400],add[N*400],rt[N];
int a[N],b[N],q[5],ans;
vector<int>p[N];
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
void build(int &o,int l,int r){
o=++cnt,Max[o]=r,Min[o]=l;
if(l==r) return;
int mid=l+r>>1;
build(ls[o],l,mid),build(rs[o],mid+1,r);
}
void mdy(int &o,int p,int l,int r,int ll,int rr){
o=++cnt,ls[o]=ls[p],rs[o]=rs[p],add[o]=add[p];
if(l>=ll&&r<=rr){add[o]=add[p]-2,Max[o]=Max[p]-2,Min[o]=Min[p]-2;return;}
int mid=l+r>>1;
if(ll<=mid) mdy(ls[o],ls[p],l,mid,ll,rr);
if(rr>mid) mdy(rs[o],rs[p],mid+1,r,ll,rr);
Max[o]=max(Max[ls[o]],Max[rs[o]])+add[o],
Min[o]=min(Min[ls[o]],Min[rs[o]])+add[o];
}
int query_Max(int o,int l,int r,int ll,int rr){
if(l>=ll&&r<=rr) return Max[o];
int mid=l+r>>1,res=-inf;
if(ll<=mid) res=max(res,query_Max(ls[o],l,mid,ll,rr)+add[o]);
if(rr>mid) res=max(res,query_Max(rs[o],mid+1,r,ll,rr)+add[o]);
return res;
}
int query_Min(int o,int l,int r,int ll,int rr){
if(l>=ll&&r<=rr) return Min[o];
int mid=l+r>>1,res=inf;
if(ll<=mid) res=min(res,query_Min(ls[o],l,mid,ll,rr)+add[o]);
if(rr>mid) res=min(res,query_Min(rs[o],mid+1,r,ll,rr)+add[o]);
return res;
}
void solve(){
for(int i=1;i<=4;++i) q[i]=(in()+ans)%n+1;sort(q+1,q+5);
int l=1,r=num;
while(l<r){
int mid=l+r+1>>1;
int qr=query_Max(rt[mid-1],1,n,q[3],q[4]),ql;
if(q[1]^1) ql=query_Min(rt[mid-1],1,n,q[1]-1,q[2]-1);
else ql=min(0,query_Min(rt[mid-1],1,n,q[1],q[2]-1));
if(qr-ql>=0) l=mid;else r=mid-1;
}
printf("%d
",ans=b[l]);
}
int main()
{
n=in();Min[0]=inf,Max[0]=-inf;
for(int i=1;i<=n;++i) a[i]=b[i]=in();
sort(b+1,b+n+1),num=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+num+1,a[i])-b,p[a[i]].pb(i);
build(rt[0],1,n);
for(int i=1;i<=num;++i)
for(int j=0;j<p[i].size();++j)
if(!j) mdy(rt[i],rt[i-1],1,n,p[i][j],n);
else mdy(rt[i],rt[i],1,n,p[i][j],n);
m=in();
while(m--) solve();
return 0;
}