题目
做法
完全把主席树当作线段树维护
有一种经典的办法：二分+变化数列
一个数列中(a[i]<x)则为(0)否则为(1)，只有这个数列的和(≥0)才成立，二分值域就好了
通俗易懂地说((l,r,x)：sumlimits{i=l}^r[a[i]≥x]≥sumlimits{i=l}^r [a[i]<x])
位置一排，值域线段树似乎不好做；但转换一下，值域一排，普通线段树就容易多了
至于(([a,b][c,d]))这两段，后/前缀最大子序列就好了，毕竟烂大街的操作就不讲了
My complete code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn=1e7;
inline LL Read(){
LL x(0),f(1); char c=getchar();
while(c<'0' || c>'9'){ if(c=='-')c=-1; c=getchar(); }
while(c>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*f;
}
struct node{
LL val,x;
bool operator < (const node &b)const{
return val<b.val;
}
}a[maxn];
LL n,q,nod,lst;
LL son[maxn][2],lx[maxn],rx[maxn],sum[maxn],root[maxn],tmp[10];
inline void Update(LL now){
LL lc(son[now][0]),rc(son[now][1]);
sum[now]=sum[lc]+sum[rc];
lx[now]=max(lx[lc],sum[lc]+lx[rc]),
rx[now]=max(rx[rc],sum[rc]+rx[lc]);
}
void Build(LL &now,LL l,LL r){
now=++nod;
if(l==r){
lx[now]=rx[now]=sum[now]=1;
return;
}
LL mid(l+r>>1);
Build(son[now][0],l,mid), Build(son[now][1],mid+1,r);
Update(now);
}
void Merge(LL &now,LL pre,LL l,LL r,LL c){
now=++nod;
if(l==r){
lx[now]=rx[now]=sum[now]=-1; return;
}
LL mid(l+r>>1);
if(c<=mid) Merge(son[now][0],son[pre][0],l,mid,c), son[now][1]=son[pre][1];
else Merge(son[now][1],son[pre][1],mid+1,r,c), son[now][0]=son[pre][0];
Update(now);
}
LL Query_sum(LL now,LL l,LL r,LL lt,LL rt){
if(lt<=l && rt>=r) return sum[now];
LL mid(l+r>>1),ret(0);
if(lt<=mid) ret+=Query_sum(son[now][0],l,mid,lt,rt);
if(rt>mid) ret+=Query_sum(son[now][1],mid+1,r,lt,rt);
return ret;
}
LL Query_rsum(LL now,LL l,LL r,LL lt,LL rt){
if(lt<=l && rt>=r) return rx[now];
LL mid(l+r>>1);
if(lt>=mid+1) return Query_rsum(son[now][1],mid+1,r,lt,rt);
else if(rt<=mid) return Query_rsum(son[now][0],l,mid,lt,rt);
else return max(Query_rsum(son[now][1],mid+1,r,lt,rt),Query_rsum(son[now][0],l,mid,lt,rt)+Query_sum(son[now][1],mid+1,r,lt,rt));
}
LL Query_lsum(LL now,LL l,LL r,LL lt,LL rt){
if(lt<=l && rt>=r) return lx[now];
LL mid(l+r>>1);
if(lt>=mid+1) return Query_lsum(son[now][1],mid+1,r,lt,rt);
else if(rt<=mid) return Query_lsum(son[now][0],l,mid,lt,rt);
else return max(Query_lsum(son[now][0],l,mid,lt,rt),Query_lsum(son[now][1],mid+1,r,lt,rt)+Query_sum(son[now][0],l,mid,lt,rt));
}
inline LL Check(LL l1,LL r1,LL l2,LL r2,LL mid){
LL sum(0);
if(r1+1<=l2-1) sum+=Query_sum(root[mid],1,n,r1+1,l2-1);
sum+=Query_rsum(root[mid],1,n,l1,r1);
sum+=Query_lsum(root[mid],1,n,l2,r2);
return sum>=0;
}
inline LL Solve(LL l1,LL r1,LL l2,LL r2){
LL l(1),r(n),ans(0);
while(l<=r){
LL mid(l+r>>1);
if(Check(l1,r1,l2,r2,mid)) l=mid+1,ans=mid;
else r=mid-1;
}return ans;
}
int main(){
n=Read();
for(LL i=1;i<=n;++i) a[i]=(node){Read(),i};
sort(a+1,a+1+n);
Build(root[1],1,n);
for(LL i=2;i<=n;++i)
Merge(root[i],root[i-1],1,n,a[i-1].x);
q=Read();
while(q--){
LL a1(Read()),b1(Read()),c1(Read()),d1(Read());
tmp[1]=(a1+lst)%n+1,tmp[2]=(b1+lst)%n+1,tmp[3]=(c1+lst)%n+1,tmp[4]=(d1+lst)%n+1;
sort(tmp+1,tmp+5);
printf("%lld
",lst=a[Solve(tmp[1],tmp[2],tmp[3],tmp[4])].val);
}return 0;
}