传送门 题意：略
排序后序列单调，满足二分性，对于一个数x，在区间内大于它的+1，小于它的-1。如果区间和不小于0，则可以让x变大，否则x变小。所以按数组（排序前原数组！）下标建主席树，0~(n-1)每棵树维护所有区间关于数a[i]的区间和（+1，-1的和）（这个要好好想想，反正脑瓜不好使的我想了好久好久），以及区间最大前后缀和（用途见代码judge()函数）。
注意：排序前一定要分配编号！！！否则就找不回原序列了。。。
#include<bits/stdc++.h> #define lson lc[rt],l,mid #define rson rc[rt],mid+1,r using namespace std; const int maxn=2e4+2; int n,m; int tim=0,last=0; int root[maxn],lc[maxn*20],rc[maxn*20],lm[maxn*20],rm[maxn*20],sum[maxn*20]; int b[4]; struct A { int v,p; friend bool operator <(const A &a,const A &b) { return a.v<b.v; } }aa[maxn]; inline int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x*f; } inline void pushup(int rt) { sum[rt]=sum[lc[rt]]+sum[rc[rt]], lm[rt]=max(lm[lc[rt]],sum[lc[rt]]+lm[rc[rt]]), rm[rt]=max(rm[rc[rt]],sum[rc[rt]]+rm[lc[rt]]); } void build(int &rt,int l,int r) { rt=++tim; if (l==r) { sum[rt]=lm[rt]=rm[rt]=1; return ; } int mid=(l+r)>>1; build(lson), build(rson); pushup(rt); } void insert(int pre,int &rt,int l,int r,int p,int v) { rt=++tim; if (l==r) { sum[rt]=lm[rt]=rm[rt]=v; return ; } lc[rt]=lc[pre],rc[rt]=rc[pre]; int mid=(l+r)>>1; if (p<=mid) insert(lc[pre],lson,p,v); else insert(rc[pre],rson,p,v); pushup(rt); } int qsum(int rt,int l,int r,int L,int R) { if (L==l&&r==R) return sum[rt]; int mid=(l+r)>>1; if (R<=mid) return qsum(lson,L,R); else if (L>mid) return qsum(rson,L,R); else return qsum(lson,L,mid)+qsum(rson,mid+1,R); } int ql(int rt,int l,int r,int L,int R) { if (L==l&&r==R) return lm[rt]; int mid=(l+r)>>1; if (R<=mid) return ql(lson,L,R); else if (L>mid) return ql(rson,L,R); else return max(ql(lson,L,mid),qsum(lson,L,mid)+ql(rson,mid+1,R)); } int qr(int rt,int l,int r,int L,int R) { if (L==l&&r==R) return rm[rt]; int mid=(l+r)>>1; if (R<=mid) return qr(lson,L,R); else if (L>mid) return qr(rson,L,R); else return max(qr(rson,mid+1,R),qsum(rson,mid+1,R)+qr(lson,L,mid)); } bool judge(int rt,int a,int b,int c,int d) { int temp=0; if (c-b>1) temp+=qsum(root[rt],0,n-1,b+1,c-1); temp+=(qr(root[rt],0,n-1,a,b)+ql(root[rt],0,n-1,c,d)); return temp>=0; } int main() { // freopen("bzoj 2653.in","r",stdin); n=read(); for (register int i=0;i<n;++i) aa[i].v=read(),aa[i].p=i; sort(aa,aa+n); build(root[0],0,n-1); for (register int i=1;i<n;++i) insert(root[i-1],root[i],0,n-1,aa[i-1].p,-1); m=read(); while (m--) { b[0]=read(),b[1]=read(),b[2]=read(),b[3]=read(); for (int i=0;i<4;++i) b[i]=(b[i]+last)%n; sort(b,b+4); int l=0,r=n-1,x; while (l<=r) { int mid=(l+r)>>1; if (judge(mid,b[0],b[1],b[2],b[3])) x=mid,l=mid+1; else r=mid-1; } printf("%d\n",last=aa[x].v); } return 0; }