luogu2839题解

[国家集训队] middle

题目分析

代码如下。

#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;
}