https://www.lydsy.com/JudgeOnline/problem.php?id=2653
因为是两个方向向外延伸所以不能对编号取前缀和(这里只有前缀和向后传递的性质，不是实际意义的和)，那么对排序后的数字取前缀和，线段树维护编号然后二分就可以了。
在一个值相对的线段树中，数小于该值的位置视为-1，数大于等于该值的位置视为+1. 那么当可取的区间内可以的到的最大的和>=0时该数就是合法的。
维护lmx, rmx, sum三个值分别表示该区间从左向右能得到的最大前缀和、从右向左能得到的最大前缀和、区间和。
二分到区间没有的数也没有关系，二分终究会收敛到区间中存在的数。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define LL long long
#define pa pair<int,int>
const int maxn=;
pa a[maxn];
int n,m;
int q[]={};
int rt[maxn]={};
int siz[maxn*]={},lmx[maxn*]={},rmx[maxn*]={},lc[maxn*]={},rc[maxn*]={},tot=;
inline void updata(int x){
siz[x]=siz[lc[x]]+siz[rc[x]];
lmx[x]=max(lmx[lc[x]],siz[lc[x]]+lmx[rc[x]]);
rmx[x]=max(rmx[rc[x]],siz[rc[x]]+rmx[lc[x]]);
}
void build(int &x,int l,int r){
x=++tot; siz[x]=lmx[x]=rmx[x]=(r-l+);
if(l==r)return;
int mid=(l+r)/;
build(lc[x],l,mid);
build(rc[x],mid+,r);
}
void inser(int &x,int y,int l,int r,int z){
x=++tot;siz[x]=siz[y];lmx[x]=lmx[y];rmx[x]=rmx[y];lc[x]=lc[y];rc[x]=rc[y];
if(l==r){siz[x]=-;lmx[x]=;rmx[x]=;return;}
int mid=(l+r)/;
if(z<=mid) inser(lc[x],lc[y],l,mid,z);
else inser(rc[x],rc[y],mid+,r,z);
updata(x);
}
int getsum(int x,int l,int r,int zl,int zr){
if(zl>zr)return ;
if(zl<=l&&r<=zr){return siz[x];}
int mid=(l+r)/,ans=;
if(zl<=mid)ans=getsum(lc[x],l,mid,zl,zr);
if(mid<zr)ans+=getsum(rc[x],mid+,r,zl,zr);
return ans;
}
int getl(int x,int l,int r,int zl,int zr){
if(zl>zr)return ;
if(zl<=l&&r<=zr)return lmx[x];
int mid=(l+r)/,ans=;
if(zl<=mid)ans=getl(lc[x],l,mid,zl,zr);
if(mid<zr)ans=max(ans,getl(rc[x],mid+,r,zl,zr)+getsum(lc[x],l,mid,zl,mid));
return ans;
}
int getr(int x,int l,int r,int zl,int zr){
if(zl>zr)return ;
if(zl<=l&&r<=zr)return rmx[x];
int mid=(l+r)/,ans=;
if(mid<zr)ans=getr(rc[x],mid+,r,zl,zr);
if(zl<=mid)ans=max(ans,getr(lc[x],l,mid,zl,zr)+getsum(rc[x],mid+,r,mid+,zr));
return ans;
}
bool check(int x){
int z=getsum(rt[x],,n,q[],q[]);//cout<<z<<endl;
int w=getl(rt[x],,n,q[]+,q[]);//cout<<w<<endl;
int k=getr(rt[x],,n,q[],q[]-);//cout<<k<<endl;
if(z+w+k>=)return ;
else return ;
}
inline int find(){
int l=,r=n,mid;
while(l<r){
mid=(l+r+)/;
if(check(mid))l=mid;
else r=mid-;
}return l;
}
int main(){
scanf("%d",&n);
int x;
for(int i=;i<=n;i++){ scanf("%d",&x); a[i]=make_pair(x,i); }
sort(a+,a++n);build(rt[],,n);
for(int i=;i<=n;i++){ rt[i]=rt[i-];inser(rt[i],rt[i],,n,a[i-].second); }
int ans=;scanf("%d",&m);
for(int i=;i<=m;i++){
scanf("%d%d%d%d",&q[],&q[],&q[],&q[]);
q[]=(q[]+ans)%n+;q[]=(q[]+ans)%n+;
q[]=(q[]+ans)%n+;q[]=(q[]+ans)%n+;
sort(q,q+);ans=a[find()].first;
printf("%d\n",ans);
}
return ;
}