求条

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+1;
struct Segment_tree
{
	int ls,rs,lsum,rsum,sum;
}tree[N*20];
struct Result
{
	int lsum,rsum,sum;
};
int n,a[N],A[N],Q,root[N],m,tot;
vector<int>upd[N];
void build(int &id,int l,int r)
{
	id=++tot;
	tree[id].lsum=tree[id].rsum=tree[id].sum=r-l+1;
	if(l==r)return;
	int mid=l+r>>1;
	build(tree[id].ls,l,mid);
	build(tree[id].rs,mid+1,r); 
}
void push_up(int id)
{
	tree[id].lsum=max(tree[tree[id].ls].lsum,tree[tree[id].ls].sum+tree[tree[id].rs].lsum);
	tree[id].rsum=max(tree[tree[id].rs].rsum,tree[tree[id].rs].sum+tree[tree[id].ls].rsum);
	tree[id].sum=tree[tree[id].ls].sum+tree[tree[id].rs].sum;
}
void update(int &id,int p,int l,int r)
{
	if(p<l||p>r)return;
	tree[++tot]=tree[id];
	id=tot;
	if(l==r)
	{
		tree[id].lsum=tree[id].rsum=tree[id].sum=-1;
		return;
	}
	int mid=l+r>>1;
	update(tree[id].ls,p,l,mid);
	update(tree[id].rs,p,mid+1,r);
	push_up(id);
}
Result query(int id,int ql,int qr,int l,int r)
{
	if(ql>qr)return {0,0,0};
	if(ql<=l&&r<=qr)return {tree[id].lsum,tree[id].rsum,tree[id].sum};
	int mid=l+r>>1;
	if(qr<=mid)return query(tree[id].ls,ql,qr,l,mid);
	if(ql>mid)return query(tree[id].rs,ql,qr,mid+1,r);
	Result res1=query(tree[id].ls,ql,qr,l,mid),res2=query(tree[id].rs,ql,qr,mid+1,r);
	return {max(res1.lsum,res1.sum+res2.lsum),max(res2.rsum,res2.sum+res1.rsum),res1.sum+res2.sum};
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		A[i]=a[i];
	}
	sort(A+1,A+1+n);
	int m=unique(A+1,A+1+n)-A-1;
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(A+1,A+1+m,a[i])-A;
		upd[a[i]].push_back(i);
	}
	build(root[1],1,n);
	for(int i=2;i<=m;i++)
	{
		root[i]=root[i-1];
		for(int x:upd[i-1])
		{
			update(root[i],x,1,n);
		}
	}
	cin>>Q;
	int x=0;
	while(Q--)
	{
		int a,b,c,d,q[4],l=1,r=m;
		cin>>q[0]>>q[1]>>q[2]>>q[3];
		q[0]=(q[0]+x)%n+1;
		q[1]=(q[1]+x)%n+1;
		q[2]=(q[2]+x)%n+1;
		q[3]=(q[3]+x)%n+1;
		sort(q,q+4);
		a=q[0];
		b=q[1];
		c=q[2];
		d=q[3];
		while(l<=r)
		{
			int mid=l+r>>1;
			if(query(root[mid],a,b,1,n).rsum+query(root[mid],b+1,c-1,1,n).sum+query(root[mid],c,d,1,n).lsum>=0)l=mid+1;
			else r=mid-1;
		}
		cout<<A[x=l-1]<<"\n";
	}
    return 0;
}