转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
一个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号,除法取下整。
给你一个长度为n的序列s。
回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。
其中a<b<c<d。
位置也从0开始标号。
http://www.lydsy.com/JudgeOnline/problem.php?id=2653
CLJ的题，强制在线处理了。
要求中位数最大，首先二分中位数，然后判断可行不可行。
判断X可行不可行，对于区间内的数，凡是>=X的标为1，否则为-1。这样的话，求一次最大区间和
如果大于等于0，则说明可行。
检验一下就很明白了。
这就是关键了，不过不能每次去暴力。快速求解子段和可以用线段树解决 ，但是对于不同的X，不可能建立多棵线段树
这就可以用主席树解决
对于初始的数，可以离散化，也可以不需要，直接排序，然后按从小到大依次建立主席树。
初始的话全为1，然后不断修改-1。有了之前的可持久化的基础，这步就很轻松了
然后就类似线段树一样，维护一个区间和，最大的左连续和，最大的右连续和。
结合在一起的时候，debug了下。。。。弱爆了
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<stack>
#include<string>
#include<ctime>
#include<queue>
#include<cassert>
#define inf 1000000005
#define M 2560005
#define N 20005
#define maxn 210005
#define eps 1e-8
#define zero(a) fabs(a)<eps
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define MOD 1000000007
#define sqr(a) ((a)*(a))
#define Key_value ch[ch[root][1]][0]
#define test puts("OK");
#define pi acos(-1.0)
#define lowbit(x) ((-(x))&(x))
#define HASH1 1331
#define HASH2 10001
#define C 240
#define vi vector<int>
#define TIME 10
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
int a[N],n,q;
int T[M],lson[M],rson[M],sum[M],lx[M],rx[M],tot=0;
pair<int,int>h[N];
void Push_up(int root){
int l=lson[root];
int r=rson[root];
sum[root]=sum[l]+sum[r];
lx[root]=max(lx[l],sum[l]+lx[r]);
rx[root]=max(rx[r],sum[r]+rx[l]);
}
int bulid(int l,int r){
int root=tot++;
if(l==r){
lx[root]=rx[root]=sum[root]=1;
return root;
}
int mid=(l+r)>>1;
lson[root]=bulid(l,mid);
rson[root]=bulid(mid+1,r);
Push_up(root);
return root;
}
int update(int root,int l,int r,int pos,int val){
int newroot=tot++;
if(l==r){
sum[newroot]=lx[newroot]=rx[newroot]=val;
return newroot;
}
int mid=(l+r)>>1;
if(pos<=mid){
lson[newroot]=update(lson[root],l,mid,pos,val);
rson[newroot]=rson[root];
root=lson[root];
}
else{
rson[newroot]=update(rson[root],mid+1,r,pos,val);
lson[newroot]=lson[root];
root=rson[root];
}
Push_up(newroot);
return newroot;
}
int query_all(int root,int L,int R,int l,int r){
if(l==L&&r==R) return sum[root];
int mid=(L+R)>>1;
if(r<=mid) return query_all(lson[root],L,mid,l,r);
else if(l>mid) return query_all(rson[root],mid+1,R,l,r);
else return query_all(lson[root],L,mid,l,mid)+query_all(rson[root],mid+1,R,mid+1,r);
}
int query_left(int root,int L,int R,int l,int r){
if(l==L&&r==R) return lx[root];
int mid=(L+R)>>1;
if(r<=mid) return query_left(lson[root],L,mid,l,r);
else if(l>mid) return query_left(rson[root],mid+1,R,l,r);
else return max(query_left(lson[root],L,mid,l,mid),query_all(lson[root],L,mid,l,mid)+query_left(rson[root],mid+1,R,mid+1,r));
}
int query_right(int root,int L,int R,int l,int r){
if(l==L&&r==R) return rx[root];
int mid=(L+R)>>1;
if(r<=mid) return query_right(lson[root],L,mid,l,r);
else if(l>mid) return query_right(rson[root],mid+1,R,l,r);
else return max(query_right(rson[root],mid+1,R,mid+1,r),query_all(rson[root],mid+1,R,mid+1,r)+query_right(lson[root],L,mid,l,mid));
}
int check(int k,int a,int b,int c,int d){
int val=0;
if(b+1<c) val+=query_all(T[k],0,n-1,b+1,c-1);
val+=query_right(T[k],0,n-1,a,b);
val+=query_left(T[k],0,n-1,c,d);
return val>=0;
}
void debug(int root,int l,int r){
cout<<l<<" "<<r<<" "<<sum[root]<<endl;
if(l!=r){
int m=(l+r)>>1;
debug(lson[root],l,m);
debug(rson[root],m+1,r);
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
h[i]=mp(a[i],i);
}
sort(h,h+n);
T[0]=bulid(0,n-1);
for(int i=1;i<n;i++)
T[i]=update(T[i-1],0,n-1,h[i-1].second,-1);
scanf("%d",&q);
int ans=0,p[4];
while(q--){
scanf("%d%d%d%d",&p[0],&p[1],&p[2],&p[3]);
for(int i=0;i<4;i++)
p[i]=(p[i]+ans)%n;
sort(p,p+4);
int low=0,high=n-1,mid,ret;
while(low<=high){
mid=(low+high)>>1;
if(check(mid,p[0],p[1],p[2],p[3])){
low=mid+1;
ret=mid;
}
else
high=mid-1;
}
ans=h[ret].first;
printf("%d\n",ans);
}
return 0;
}