[国家集训队]middle
（upda:2023.1.26 没想到挂了4年的题解在代码上有个小bug，现在已经修复代码，通过了hack数据。感谢 @出言不逊王子 同学提供的hack数据，对因此给大家学习造成的不便表示歉意）
（题解本身没有问题，改之前是在代码中第一棵主席树，也就是build函数那里初始化出现了错误。另外也增加了代码注释）
—————————————————————————————————— 以下为题解：
这个题就比较的巧妙了。不像之前的套路性的第k问题。
这个是真真正正地用主席树替代了线段树。
首先，对于区间中位数一个比较套路的做法是：
二分一个答案mid，把所有>=mid的数值设成1，<mid的值设为-1
查询区间内的和是否>=0（这个题是>=0，题意中，偶数项的中位数是中间的那两个靠后的那一个）
是，中位数应该更大，
否则，中位数只能更小。
先不考虑复杂度。
给[a,d]区间的数赋值为1、-1
这个题，区间都不是固定的。
但是，[b+1,c-1]的值是必选的。计算一下这个区间的和。
对于[a,b],[c,d]
因为要让中位数尽可能的大。
所以，争取选择尽可能多的1
找一个[a,b]的最大后缀，[c,d]的最大前缀。
这三个和就是对于mid的最大的和了，可以进行判断。
因为多组询问，而数组不会改变，
而离散化之后，中位数的值在1~n之间。
所以，对于每一个二分的mid值，建一棵线段树。
线段树以区间下标为下标，记录区间和，区间最大后缀，最大前缀。
就可以O(logn)判断mid是否可以更优了。
空间又炸了。所以主席树闪亮登场！！！
发现，对于mid变成mid+1，只有值为mid的数的值会从+1变成-1.
主席树在前者的基础上暴力修改。
每一个数就会改一次，所以均摊logn空间。、
时间复杂度：nlogn^2
空间复杂度：nlogn
代码：(vector 记录数字出现的位置）（这个代码可以通过新增的hack数据）
#include<bits/stdc++.h>
using namespace std;
const int N=20000+10;
int n,m;
int a[N],num[N],mem;
int rt[N];
int x1,x2,x3,x4;
int li(int x){//离散化
return lower_bound(num+1,num+mem+1,x)-num;
}
struct node{//线段树节点结构体
int sum,lmx,rmx;
int lson,rson;
bool ncl,ncr;//这两个变量的意义是当前节点有没有“新建”的左右儿子，如果有，该值为true。“儿子是新建的”意思是，这个儿子不是用的前一个树的
#define s(x) t[x].sum
#define ls(x) t[x].lson
#define rs(x) t[x].rson
#define lm(x) t[x].lmx
#define rm(x) t[x].rmx
#define cl(x) t[x].ncl
#define cr(x) t[x].ncr
}t[N*40];
int tot;
vector<int>pos[N];//记录大小从1~n的每个数字出现的位置
void pushup(int x){
s(x)=s(ls(x))+s(rs(x));
lm(x)=max(lm(ls(x)),s(ls(x))+lm(rs(x)));
rm(x)=max(rm(rs(x)),s(rs(x))+rm(ls(x)));
}
int build(int l,int r){//构建第一棵树
int id=++tot;
if(l==r){
s(id)=lm(id)=rm(id)=1;
return id;
}
int mid=(l+r)>>1;cl(id)=1;cr(id)=1;
ls(id)=build(l,mid);rs(id)=build(mid+1,r);
pushup(id);
return id;
}
void upda(int &x,int y,int l,int r,int to,int c,bool nc){//在y主席树的基础上更新x主席树，x这里取引用
if(!nc) {//新建节点语句
x=++tot;
}
if(l==r){
s(x)=lm(x)=rm(x)=c;
return;
}
int mid=(l+r)>>1;
if(to<=mid){//向左递归
if(!cr(x)) rs(x)=rs(y); //如果x没有新建的右儿子 那么指向y的右儿子
if(!cl(x)){//如果x没有新建的左儿子，那么要新建一个左儿子了
cl(x)=1;//有了新建的左儿子
upda(ls(x),ls(y),l,mid,to,c,0);//这里nc=0，递归下去后会执行新建节点语句
}
else{//有新建过的左儿子，直接从左儿子下去，不用再新建了
upda(ls(x),ls(y),l,mid,to,c,1);
}
}
else{//向右递归，其他语句代码和向左递归类似
if(!cl(x)) ls(x)=ls(y);
if(!cr(x)){
cr(x)=1;
upda(rs(x),rs(y),mid+1,r,to,c,0);
}
else{
upda(rs(x),rs(y),mid+1,r,to,c,1);
}
}
pushup(x);
}
int qs(int x,int l,int r,int L,int R){//求区间和
if(L<=l&&r<=R){
return s(x);
}
int mid=(l+r)>>1;int ret=0;
if(L<=mid) ret+=qs(ls(x),l,mid,L,R);
if(mid<R) ret+=qs(rs(x),mid+1,r,L,R);
return ret;
}
node ql(int x,int l,int r,int L,int R){//求区间最大前缀
if(L<=l&&r<=R){
return t[x];
}
int mid=(l+r)>>1;
if(L<=mid&&mid<R){
node ret;
node le=ql(ls(x),l,mid,L,R);
node ri=ql(rs(x),mid+1,r,L,R);
ret.sum=le.sum+ri.sum;
ret.lmx=max(le.lmx,le.sum+ri.lmx);
return ret;
}
else if(L<=mid){
return ql(ls(x),l,mid,L,R);
}
else {
return ql(rs(x),mid+1,r,L,R);
}
}
node qr(int x,int l,int r,int L,int R){//求区间最大后缀
if(L<=l&&r<=R){
return t[x];
}
int mid=(l+r)>>1;
if(L<=mid&&mid<R){
node ret;
node le=qr(ls(x),l,mid,L,R);
node ri=qr(rs(x),mid+1,r,L,R);
ret.sum=le.sum+ri.sum;
ret.rmx=max(ri.rmx,ri.sum+le.rmx);
return ret;
}
else if(L<=mid){
return qr(ls(x),l,mid,L,R);
}
else {
return qr(rs(x),mid+1,r,L,R);
}
}
bool che(int val){//检查val值是否合法
int sz=0;
if(x2+1<=x3-1) sz=qs(rt[val],1,n,x2+1,x3-1);
int sr=ql(rt[val],1,n,x3,x4).lmx;
int sl=qr(rt[val],1,n,x1,x2).rmx;
return (sl+sz+sr)>=0;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),num[++mem]=a[i];
sort(num+1,num+mem+1);
mem=unique(num+1,num+mem+1)-num-1;
for(int i=1;i<=n;i++){
pos[li(a[i])].push_back(i);
}
rt[1]=build(1,n);//建树
for(int i=2;i<=mem;i++){//建树
for(int j=0;j<pos[i-1].size();j++){
int go=pos[i-1][j];
upda(rt[i],rt[i-1],1,n,go,-1,rt[i]>0);
}
}
scanf("%d",&m);
int las=0;
int ch[6];
while(m--){
scanf("%d%d%d%d",&x1,&x2,&x3,&x4);
ch[1]=(x1+las)%n;
ch[2]=(x2+las)%n;
ch[3]=(x3+las)%n;
ch[4]=(x4+las)%n;
sort(ch+1,ch+4+1);
x1=ch[1]+1,x2=ch[2]+1,x3=ch[3]+1,x4=ch[4]+1;
int l=1,r=mem;
int ans=0;
while(l<=r){//进行二分
int mid=(l+r)>>1;
if(che(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
las=num[ans];
printf("%d\n",las);
}
return 0;
}