Description
一个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号,除法取下整。
给你一个长度为n的序列s。
回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。
其中a<b<c<d。
位置也从0开始标号。
我会使用一些方式强制你在线。
Input
第一行序列长度n。
接下来n行按顺序给出a中的数。
接下来一行Q。
然后Q行每行a,b,c,d，我们令上个询问的答案是x(如果这是第一个询问则x=0)。
令数组q={(a+x)%n,(b+x)%n,(c+x)%n,(d+x)%n}。
将q从小到大排序之后，令真正的要询问的a=q[0],b=q[1],c=q[2],d=q[3]。
输入保证满足条件。
Output
Q行依次给出询问的答案。
Sample Input
5
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0
271451044
271451044
969056313
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0
271451044
271451044
969056313
Sample Output
HINT
0:n,Q<=100
1,...,5:n<=2000
0,...,19:n<=20000,Q<=25000
/* 二分+主席树 （感觉主席树越来越神奇） 首先要明白中位数怎么求，可以二分，当我们二分出一个答案时，把区间中大于这个数标为1，小于则标为-1，求和。。。 对于这道题来说，要是中位数越大越好，如果按照上面的方法，1越多，代表中位数越大，所以二分出答案后，用GSS的方法求RGSS(a,b)+sum(b,c)+LGSS(c,d)， 判断是否大于0。 至于怎么快速求出1/-1数组，用主席树维护（？） */ #include<cstdio> #include<iostream> #include<algorithm> #define N 20010 using namespace std; int n,m,cnt,ans; int a[N],id[N],rt[N],sum[N*20],lx[N*20],rx[N*20],son[N*20][2]; bool cmp(const int &x1,const int &x2){ return a[x1]<a[x2]; } void pushup(int x){ sum[x]=sum[son[x][0]]+sum[son[x][1]]; lx[x]=max(lx[son[x][0]],sum[son[x][0]]+lx[son[x][1]]); rx[x]=max(rx[son[x][1]],sum[son[x][1]]+rx[son[x][0]]); } void build(int l,int r,int &rt){ if(l==r){ rt=++cnt;sum[rt]=lx[rt]=rx[rt]=1; return; } rt=++cnt; int mid=l+r>>1; build(l,mid,son[rt][0]); build(mid+1,r,son[rt][1]); pushup(rt); } void insert(int x,int &y,int l,int r,int pos,int val){ y=++cnt; sum[y]=sum[x];lx[y]=lx[x];rx[y]=rx[x]; son[y][0]=son[x][0];son[y][1]=son[x][1]; if(l==r){ lx[y]=rx[y]=sum[y]=val; return; } int mid=l+r>>1; if(pos<=mid) insert(son[x][0],son[y][0],l,mid,pos,val); else insert(son[x][1],son[y][1],mid+1,r,pos,val); pushup(y); } int get_all(int rt,int l,int r,int x,int y){ if(l==x&&r==y) return sum[rt]; int mid=l+r>>1; if(y<=mid) return get_all(son[rt][0],l,mid,x,y); else if(x>mid) return get_all(son[rt][1],mid+1,r,x,y); else return get_all(son[rt][0],l,mid,x,mid)+get_all(son[rt][1],mid+1,r,mid+1,y); } int get_lx(int rt,int l,int r,int x,int y){ if(l==x&&r==y) return lx[rt]; int mid=l+r>>1; if(y<=mid) return get_lx(son[rt][0],l,mid,x,y); else if(x>mid) return get_lx(son[rt][1],mid+1,r,x,y); else return max(get_lx(son[rt][0],l,mid,x,mid),get_all(son[rt][0],l,mid,x,mid)+get_lx(son[rt][1],mid+1,r,mid+1,y)); } int get_rx(int rt,int l,int r,int x,int y){ if(l==x&&r==y) return rx[rt]; int mid=l+r>>1; if(y<=mid) return get_rx(son[rt][0],l,mid,x,y); else if(x>mid) return get_rx(son[rt][1],mid+1,r,x,y); else return max(get_rx(son[rt][1],mid+1,r,mid+1,y),get_all(son[rt][1],mid+1,r,mid+1,y)+get_rx(son[rt][0],l,mid,x,mid)); } bool check(int k,int a,int b,int c,int d){ int sum=0; if(c>b+1) sum+=get_all(rt[k],0,n-1,b+1,c-1); sum+=get_rx(rt[k],0,n-1,a,b); sum+=get_lx(rt[k],0,n-1,c,d); return sum>=0; } int main(){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&a[i]);id[i]=i; } sort(id,id+n,cmp); build(0,n-1,rt[0]); for(int i=1;i<n;i++) insert(rt[i-1],rt[i],0,n-1,id[i-1],-1); int ord[4]; scanf("%d",&m); while(m--){ scanf("%d%d%d%d",&ord[0],&ord[1],&ord[2],&ord[3]); for(int i=0;i<4;i++) ord[i]=(ord[i]+ans)%n; sort(ord,ord+4); int l=0,r=n,mid; while(l+1<r){ mid=l+r>>1; if(check(mid,ord[0],ord[1],ord[2],ord[3]))l=mid; else r=mid; } ans=a[id[l]]; printf("%d ",ans); } return 0; }