middle HYSBZ - 2653

https://www.lydsy.com/JudgeOnline/problem.php?id=2653

根據題目要求 左端點在[a,b]中 右端點在[c,d]中 那[b+1,c-1]中的數是必須都要選的 而[a,b]中需再選一個右連續段 [c,d]中選一個左連續段

将給定序列排序 然後建立主席樹 初始每個點都為1 第i棵線段樹在第i-1棵基礎上 把排序後的第i-1個數對應位置置為-1

這樣第i棵樹上的1就代表原序列對應位置的數大于等于目前數 -1代表原序列對應位置的數小于等于目前數 這樣二分枚舉一個中位數 看[a,b]的最大右連續段 [b+1,c-1]這一段 [c,d]的最大左連續段 三者之和若小于零 則說明所選中位數太大 小于等于它的數太多 反之亦然

#include <bits/stdc++.h>
using namespace std;

struct node1
{
	int id;
	int val;
};

struct node2
{
	int l;
	int r;
	int left;
	int right;
	int all;
};

node1 ary[20010];
node2 tree[400010];
int root[20010];
int n,q,num;

bool cmp(node1 n1,node1 n2)
{
	return n1.val<n2.val;
}

void pushup(int cur)
{
	tree[cur].left=max(tree[tree[cur].l].left,tree[tree[cur].l].all+tree[tree[cur].r].left);
	tree[cur].right=max(tree[tree[cur].r].right,tree[tree[cur].r].all+tree[tree[cur].l].right);
	tree[cur].all=tree[tree[cur].l].all+tree[tree[cur].r].all;
}

int build(int l,int r)
{
	int cur,m;
	cur=num++;
	tree[cur].l=0,tree[cur].r=0;
	if(l==r)
	{
		tree[cur].left=tree[cur].right=tree[cur].all=1;
		return cur;
	}
	m=(l+r)/2;
	tree[cur].l=build(l,m);
	tree[cur].r=build(m+1,r);
	pushup(cur);
	return cur;
}

int update(int rot,int tar,int l,int r)
{
	int cur,m;
	cur=num++;
	tree[cur]=tree[rot];
	if(l==r)
	{
		tree[cur].left=tree[cur].right=tree[cur].all=-1;
		return cur;
	}
	m=(l+r)/2;
	if(tar<=m) tree[cur].l=update(tree[rot].l,tar,l,m);
	else tree[cur].r=update(tree[rot].r,tar,m+1,r);
	pushup(cur);
	return cur;
}

void query(int rot,int pl,int pr,int &left,int &right,int &all,int l,int r)
{
	int m,lleft,lright,lall,rleft,rright,rall;
	if(pl<=l&&r<=pr)
	{
		left=tree[rot].left;
		right=tree[rot].right;
		all=tree[rot].all;
		return;
	}
	m=(l+r)/2;
	if(pr<=m) query(tree[rot].l,pl,pr,left,right,all,l,m);
	else if(pl>m) query(tree[rot].r,pl,pr,left,right,all,m+1,r);
	else
	{
		query(tree[rot].l,pl,m,lleft,lright,lall,l,m);
		query(tree[rot].r,m+1,pr,rleft,rright,rall,m+1,r);
		left=max(lleft,lall+rleft);
		right=max(rright,rall+lright);
		all=lall+rall;
	}
}

int main()
{
	int tmp[10];
	int i,ans,l,r,m,left,right,all,a,b,c;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		ary[i].id=i;
		scanf("%d",&ary[i].val);
	}
	sort(ary+1,ary+n+1,cmp);
	num=0;
	root[0]=build(1,n);
	root[1]=root[0];
	for(i=2;i<=n;i++)
	{
		root[i]=update(root[i-1],ary[i-1].id,1,n);
	}
	scanf("%d",&q);
	ans=0;
	while(q--)
	{
		for(i=1;i<=4;i++)
		{
			scanf("%d",&tmp[i]);
			tmp[i]=(tmp[i]+ans)%n+1;
		}
		sort(tmp+1,tmp+5);
		l=1,r=n;
		while(l<=r)
		{
			m=(l+r)/2;
			query(root[m],tmp[3],tmp[4],a,b,c,1,n);
			left=a;
			query(root[m],tmp[1],tmp[2],a,b,c,1,n);
			right=b;
			if(tmp[2]+1<=tmp[3]-1)
			{
				query(root[m],tmp[2]+1,tmp[3]-1,a,b,c,1,n);
				all=c;
			}
			else all=0;
			if(left+right+all>=0)
			{
				ans=m;
				l=m+1;
			}
			else
			{
				r=m-1;
			}
		}
		ans=ary[ans].val;
		printf("%d\n",ans);
	}
	return 0;
}