题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2653

题目分类：可持久化数据结构

题意：

给出一个长度为n的序列。

每次询问左端点在一个区间内，右端点在一个另区间内的所有子串中中位数最大的子串的中位数。

强制在线。

题解：

可以先二分答案，然后判断给定条件下的子串中拥有最多的比该数小的数的值判断是否合法。

使用可持久化线段树维护数值在1-i区间中每一段的最大子串和。

程序：

#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
	int lson,rson,lmax,rmax,mmax,summ;
	inline void one()
	{
		lmax=1;
		summ=1;
		rmax=1;
		mmax=1;
	}
	inline void minusone()
	{
		lmax=-1;
		rmax=-1;
		mmax=-1;
		summ=-1;
	}
}a[2100000],zero;
int siz;
int rot[21000],m,x1,x2,x3,x4;
inline node join(node a,node b,int ls,int rs)
{
	node x;
	x.lson=ls;
	x.rson=rs;
	x.summ=a.summ+b.summ;
	x.lmax=max(a.lmax,b.lmax+a.summ);
	x.rmax=max(b.rmax,a.rmax+b.summ);
	x.mmax=max(max(a.mmax,b.mmax),max(x.lmax,max(x.rmax,a.rmax+b.lmax)));
	return x;
}
int n,b[21000];
int p[21000];
inline void build(int x,int le,int ri)
{
//	printf("%d %d %d\n",x,le,ri);
	if(le==ri)
	{
		a[x].one();
		return;
	}
	siz++;
	a[x].lson=siz;
	siz++;
	a[x].rson=siz;
	build(a[x].lson,le,(le+ri)/2);
	build(a[x].rson,(le+ri)/2+1,ri);
	a[x]=join(a[a[x].lson],a[a[x].rson],a[x].lson,a[x].rson);
}
inline void insert(int x,int las,int le,int ri,int po)
{
//	printf("%d %d %d %d %d\n",x,las,le,ri,po);
	if(le==ri)
	{
		a[x].minusone();
		return;
	}
	if(po<=(le+ri)/2)
	{
		siz++;
		a[x].lson=siz;
		a[x].rson=a[las].rson;
		insert(a[x].lson,a[las].lson,le,(le+ri)/2,po);
	}
	else
	{
		siz++;
		a[x].rson=siz;
		a[x].lson=a[las].lson;
		insert(a[x].rson,a[las].rson,(le+ri)/2+1,ri,po);
	}
	a[x]=join(a[a[x].lson],a[a[x].rson],a[x].lson,a[x].rson);
}
inline void insert(int x,int le)
{
	siz++;
	rot[x]=siz;//printf(" %d %d %d %d\n",x,x-1,rot[x],rot[x-1]);
	insert(rot[x],rot[x-1],1,n,le);
}
inline node query(int x,int le,int ri,int lec,int ric)
{
	if(lec>ric)return zero;
	if(lec<=le&&ric>=ri)return a[x];
	if(lec<=(le+ri)/2&&ric>(le+ri)/2)
	{
		return join(query(a[x].lson,le,(le+ri)/2,lec,ric),query(a[x].rson,(le+ri)/2+1,ri,lec,ric),0,0);
	}
	else if(lec<=(le+ri)/2)
	{
		return query(a[x].lson,le,(le+ri)/2,lec,ric);
	}
	else
	{
		return query(a[x].rson,(le+ri)/2+1,ri,lec,ric);
	}
}
inline bool cmp(int x,int y)
{
	return b[x]<b[y];
}
inline int query2(int x,int l1,int l2,int r2,int r1)
{
	return query(rot[x],1,n,l2,r2).summ+max(0,query(rot[x],1,n,r2+1,r1).lmax)+max(0,query(rot[x],1,n,l1,l2-1).rmax);
}
int lastans,q[5];
int main()
{
	scanf("%d",&n);
	siz++;
	rot[0]=siz;
	build(siz,1,n);
	for (int i=1;i<=n;i++)
	{
		p[i]=i;
		scanf("%d",&b[i]);
	}
	sort(p+1,p+n+1,cmp);
	for (int i=1;i<=n;i++)
	{
		insert(i,p[i]);
	}
	scanf("%d",&m);
	while (m--)
	{
		scanf("%d %d %d %d",&x1,&x2,&x3,&x4);
		q[1]=(x1+lastans)%n;
		q[2]=(x2+lastans)%n;
		q[3]=(x3+lastans)%n;
		q[4]=(x4+lastans)%n;
		sort(q+1,q+5);
		x1=q[1]+1;
		x2=q[2]+1;
		x3=q[3]+1;
		x4=q[4]+1;
		int le=1,ri=n,mi;
		while (le<ri)
		{
			mi=(le+ri)/2;
	//		printf("%d %d %d %d %d %d\n",mi,x1,x2,x3,x4,query2(mi,x1,x2,x3,x4));
			if(query2(mi,x1,x2,x3,x4)>=0)
			{
				le=mi+1;
			}
			else
			{
				ri=mi;
			}
		}printf("%d\n",b[p[ri]]);
		lastans=b[p[ri]];
	}
	return 0;
}