主席树大好题……这道题让主席树不仅停留在了区间第k大上，而是让它能执行像线段树一样的操作。
首先我们先说点套路的事。求中位数有一个二分法，就是每次二分答案，把大于等于当前二分的数设为1，小于的设为-1，之后我们只要看和是否大于0就能判断限制二分的值是大是小。然后虽然区间是不确定的，但是我们要求最大的中位数，只要取中间固定的一段+左区间最大后缀+右区间最大前缀判断即可。
不过这样的话每次暴力的时候，查询是(O(nlogn))的，再套上查询次数会超时。如何优化一下呢？如果我们用线段树对于每一个二分的值，都维护一下它当前的值和最大前后缀，这样的话我们就只需要(O(log^2n))的复杂度来完成一次查询。但是这样会(MLE)。
然后在每两棵树之间，其实只有(i-1)发生了变化，从1变成了-1.这样的话我们就可以把这些线段树建成主席树，用主席树来实现线段树一样的操作就好了。注意这道题是把以当前这个数的值为根，以位置为值域，注意访问区间不要开小（我就因为这个大数据(MLE)），最开始建树的地方比较重要，我们需要开一个(vector)来把数的值一样，多次出现的数的位置都存起来，然后按照值的大小按顺序修改即可。
看一下代码。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<set>
#include<vector>
#include<map>
#include<queue>
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('
')
#define fr friend inline
#define y1 poj
#define mp make_pair
#define pr pair<int,int>
#define fi first
#define sc second
#define pb push_back
#define I puts("Oops")
using namespace std;
typedef long long ll;
const int M = 20005;
const int N = 1000005;
const int INF = 1000000009;
const double eps = 1e-7;
int read()
{
int ans = 0,op = 1;char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') op = -1;ch = getchar();}
while(ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0',ch = getchar();
return ans * op;
}
struct node
{
int ls,rs,v,lv,rv;
}t[N<<2];
int n,Q,a[M],b[M],root[M],q[6],x,y,z,e,tot,la,L,R,g,idx;
vector <int> V[M];
void update(int p)
{
t[p].v = t[t[p].ls].v + t[t[p].rs].v;
t[p].lv = max(t[t[p].ls].lv,t[t[p].ls].v + t[t[p].rs].lv);
t[p].rv = max(t[t[p].rs].rv,t[t[p].rs].v + t[t[p].ls].rv);
}
void build(int &p,int l,int r)
{
if(!p) p = ++idx;
if(l == r) {t[p].v = t[p].lv = t[p].rv = 1;return;}
int mid = (l+r) >> 1;
build(t[p].ls,l,mid),build(t[p].rs,mid+1,r);
update(p);
}
void modify(int old,int &p,int l,int r,int val)
{
p = ++idx;
t[p] = t[old];
if(l == r) {t[p].v = t[p].lv = t[p].rv = -1;return;}
int mid = (l+r) >> 1;
if(val <= mid) modify(t[old].ls,t[p].ls,l,mid,val);
else modify(t[old].rs,t[p].rs,mid+1,r,val);
update(p);
}
int query(int p,int l,int r,int kl,int kr)
{
//I;
if(kr < kl) return 0;
if(l == kl && r == kr) return t[p].v;
int mid = (l+r) >> 1;
if(kr <= mid) return query(t[p].ls,l,mid,kl,kr);
else if(kl > mid) return query(t[p].rs,mid+1,r,kl,kr);
else return query(t[p].ls,l,mid,kl,mid) + query(t[p].rs,mid+1,r,mid+1,kr);
}
int ask(int p,int l,int r,int kl,int kr,bool flag)//1 left , 0 right
{
//I;
//printf("#%d %d %d %d
",l,r,kl,kr);
if(l == kl && r == kr) return flag ? t[p].lv : t[p].rv;
int mid = (l+r) >> 1;
if(kr <= mid) return ask(t[p].ls,l,mid,kl,kr,flag);
else if(kl > mid) return ask(t[p].rs,mid+1,r,kl,kr,flag);
else
{
int cur1 = 0,cur2 = 0;
cur1 = flag ? ask(t[p].ls,l,mid,kl,mid,flag) : ask(t[p].rs,mid+1,r,mid+1,kr,flag);
if(flag) cur2 = query(t[p].ls,l,mid,kl,mid) + ask(t[p].rs,mid+1,r,mid+1,kr,flag);
else cur2 = query(t[p].rs,mid+1,r,mid+1,kr) + ask(t[p].ls,l,mid,kl,mid,flag);
return max(cur1,cur2);
}
}
bool judge(int x)
{
int cur1 = query(root[x],1,n,q[2]+1,q[3]-1);
int cur2 = ask(root[x],1,n,q[1],q[2],0);
int cur3 = ask(root[x],1,n,q[3],q[4],1);
return cur1 + cur2 + cur3 >= 0;
}
int main()
{
n = read(),build(root[0],1,n);
rep(i,1,n) a[i] = b[i] = read();
sort(b+1,b+1+n),tot = unique(b+1,b+1+n) - b - 1;
rep(i,1,n) a[i] = lower_bound(b+1,b+1+tot,a[i]) - b,V[a[i]].pb(i);
rep(i,1,tot)
{
root[i] = root[i-1];
rep(j,0,(int)V[i-1].size()-1) modify(root[i],root[i],1,n,V[i-1][j]);
}
Q = read();
rep(i,1,Q)
{
rep(j,1,4) q[j] = read(),q[j] = (q[j] + la) % n + 1;
sort(q+1,q+5),L = 1,R = tot;
while(L < R)
{
int mid = (L+R+1) >> 1;
if(judge(mid)) L = mid;
else R = mid - 1;
}
la = b[L];
printf("%d
",la);
}
return 0;
}