题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2653
对于每一个询问，我们可以用二分答案来判断当前值可不可行。
先不考虑多组询问，可以把每一个大于等于二分值的数字设成1，小于二分值的数字设成-1，然后求出[b+1,c-1]的区间和以及[a,b]的右端最大连续和以及[c,d]的左端最大连续和，这几个操作可以用传递结构体的线段树来判定，看这三个加起来是否大于等于0。如果是则表示应该继续向上二分
但是怎么能让对于任意一个二分的值，我们都有一颗已经建好的线段树，数值大于它的位置权值为1，数值小于它的位置权值为-1？
把原数组按值排序之后按数值从小到大建立主席树，每颗主席树和上一颗主席树的区别是该数值在原数组中的位置变成-1。
这样二分的时候通过找到它的那颗线段树然后查询判定就好了
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N=100005; const int M=1000005; int n,m,a[N],ans,q[10],num[N],rt[N],lim=1e9,cnt; int ls[M],rs[M]; struct pp{int v,num;} b[N]; struct data{int maxl,maxr,maxn,sum;} T[M]; data operator +(data l,data r) { data ret; ret.sum=l.sum+r.sum; ret.maxn=(l.maxr+r.maxl,max(l.maxn,r.maxn)); ret.maxl=max(l.maxl,l.sum+r.maxl); ret.maxr=max(r.maxr,r.sum+l.maxr); return ret; } bool cmp(pp u,pp v) {return u.v<v.v;} void pushup(int x) { T[x]=T[ls[x]]+T[rs[x]]; } void build(int &x,int l,int r) { if(!x) x=++cnt; if(l==r) { T[x]=(data){1,1,1,1}; return; } int mid=(l+r)>>1; build(ls[x],l,mid); build(rs[x],mid+1,r); pushup(x); } void addnew(int x,int &y,int l,int r,int k) { y=++cnt; if(l==r) { T[y]=(data){-1,-1,-1,-1}; return; } ls[y]=ls[x],rs[y]=rs[x]; int mid=(l+r)>>1; if(k<=mid) addnew(ls[x],ls[y],l,mid,k); else addnew(rs[x],rs[y],mid+1,r,k); pushup(y); } int Qsum(int x,int l,int r,int L,int R) { if(l==L&&r==R) return T[x].sum; int mid=(L+R)>>1; if(r<=mid) return Qsum(ls[x],l,r,L,mid); else if(l>mid) return Qsum(rs[x],l,r,mid+1,R); else return Qsum(ls[x],l,mid,L,mid)+Qsum(rs[x],mid+1,r,mid+1,R); } data Qleft(int x,int l,int r,int L,int R) { if(l==L&&r==R) return T[x]; int mid=(L+R)>>1; if(r<=mid) return Qleft(ls[x],l,r,L,mid); else if(l>mid) return Qleft(rs[x],l,r,mid+1,R); else return Qleft(ls[x],l,mid,L,mid)+Qleft(rs[x],mid+1,r,mid+1,R); } data Qright(int x,int l,int r,int L,int R) { if(l==L&&r==R) return T[x]; int mid=(L+R)>>1; if(r<=mid) return Qright(ls[x],l,r,L,mid); else if(l>mid) return Qright(rs[x],l,r,mid+1,R); else return Qright(ls[x],l,mid,L,mid)+Qright(rs[x],mid+1,r,mid+1,R); } bool judge(int x,int aa,int bb,int cc,int dd) { int ret=0; if(bb+1<=cc-1) ret+=Qsum(rt[x-1],bb+1,cc-1,1,n); ret+=Qright(rt[x-1],aa,bb,1,n).maxr; ret+=Qleft(rt[x-1],cc,dd,1,n).maxl; return ret>=0; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i].v=a[i]; b[i].num=i; } sort(b+1,b+n+1,cmp); build(rt[0],1,n); for(int i=1;i<=n;i++) addnew(rt[i-1],rt[i],1,n,b[i].num); scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&q[1],&q[2],&q[3],&q[4]); q[1]=(q[1]+ans)%n; q[2]=(q[2]+ans)%n; q[3]=(q[3]+ans)%n; q[4]=(q[4]+ans)%n; sort(q+1,q+5); int l=1,r=n; ans=0; while(l<=r) { int mid=(l+r)>>1; if(judge(mid,q[1]+1,q[2]+1,q[3]+1,q[4]+1)) ans=mid,l=mid+1; else r=mid-1; } ans=b[ans].v; printf("%d\n",ans); } }
