题目分析
代码如下。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=2e4+10;
int x,n,Q,a[MAXN],q[6],root[MAXN],b[MAXN],tot;
vector<int> locp[MAXN];
struct SegmentTreeNode{
int l,r,lson,rson;
int sum,lsum,rsum;
}tr[MAXN*25];
int newnode(){
return ++tot;
}
void pushup(int id){
tr[id].sum=tr[tr[id].lson].sum+tr[tr[id].rson].sum;
tr[id].lsum=max(tr[tr[id].lson].lsum,tr[tr[id].lson].sum+tr[tr[id].rson].lsum);
tr[id].rsum=max(tr[tr[id].rson].rsum,tr[tr[id].lson].rsum+tr[tr[id].rson].sum);
}
int build(int l,int r){
int p=newnode();
tr[p].l=l;tr[p].r=r;
if(l==r){
tr[p].lsum=tr[p].rsum=tr[p].sum=1;
return p;
}
int mid=(l+r)>>1;
tr[p].lson=build(l,mid);
tr[p].rson=build(mid+1,r);
pushup(p);
return p;
}
void change(int p1,int &p2,int loc){//默认修改为-1
p2=newnode();
tr[p2].l=tr[p1].l;tr[p2].r=tr[p1].r;
if(tr[p1].l==tr[p1].r){
tr[p2].lsum=tr[p2].rsum=tr[p2].sum=-1;
return;
}
int mid=(tr[p1].l+tr[p1].r)>>1;
if(loc<=mid){
change(tr[p1].lson,tr[p2].lson,loc);
tr[p2].rson=tr[p1].rson;
}else{
tr[p2].lson=tr[p1].lson;
change(tr[p1].rson,tr[p2].rson,loc);
}
pushup(p2);
}
SegmentTreeNode query(int p,int l,int r){
if(tr[p].l==l&&tr[p].r==r)return tr[p];
if(r<=tr[tr[p].lson].r)return query(tr[p].lson,l,r);
else if(tr[tr[p].rson].l<=l)return query(tr[p].rson,l,r);
else{
SegmentTreeNode ln=query(tr[p].lson,l,tr[tr[p].lson].r),rn=query(tr[p].rson,tr[tr[p].rson].l,r),rt;
rt.lsum=max(ln.lsum,ln.sum+rn.lsum);
rt.rsum=max(ln.rsum+rn.sum,rn.rsum);
rt.sum=ln.sum+rn.sum;
return rt;
}
}
int read(){
int f=1,x=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
return f*x;
}
int main(){
n=read();
for(int i=0;i<n;++i){
b[i]=a[i]=read();
}
sort(b,b+n);
int bn=unique(b,b+n)-b;
for(int i=0;i<n;++i){
locp[lower_bound(b,b+bn,a[i])-b].push_back(i);
}
root[0]=build(0,n-1);
for(int i=1;i<bn;++i){
root[i]=root[i-1];
for(int j:locp[i-1]){
change(root[i],root[i],j);
}
}
Q=read();
while(Q){
--Q;
for(int i=0;i<4;++i){
q[i]=(read()+x)%n;
}
sort(q,q+4);
int l=0,r=bn-1;
while(l<r){
int mid=(l+r+1)>>1;
int mval=query(root[mid],q[0],q[1]).rsum;
if((q[1]+1)<=(q[2]-1))mval+=query(root[mid],q[1]+1,q[2]-1).sum;
mval+=query(root[mid],q[2],q[3]).lsum; if(mval>=0)l=mid;
else r=mid-1;
}
x=b[l];
printf("%d\n",b[l]);
}
return 0;
}