[国家集训队] middle

题目描述

一个长度为 \(n\) 的序列 \(a\)，设其排过序之后为 \(b\)，其中位数定义为 \(b_{n/2}\)，其中 \(a,b\) 从 \(0\) 开始标号，除法下取整。

给你一个长度为 \(n\) 的序列 \(s\)。

回答 \(Q\) 个这样的询问：\(s\) 的左端点在 \([a,b]\) 之间，右端点在 \([c,d]\) 之间的子区间中，最大的中位数。

其中 \(a<b<c<d\)。

位置也从 \(0\) 开始标号。

我会使用一些方式强制你在线。

输入格式

第一行序列长度 \(n\)。

接下来 \(n\) 行按顺序给出 \(a\) 中的数。

接下来一行 \(Q\)。

然后 \(Q\) 行每行 \(a,b,c,d\)，我们令上个询问的答案是 \(x\)（如果这是第一个询问则 \(x=0\)）。

令数组 \(q=\{(a+x)\bmod n,(b+x)\bmod n,(c+x)\bmod n,(d+x)\bmod n\}\)。

将 \(q\) 从小到大排序之后，令真正的要询问的 \(a=q_0\)，\(b=q_1\)，\(c=q_2\)，\(d=q_3\)。

输入保证满足条件。

输出格式

\(Q\) 行依次给出询问的答案。

样例 #1

样例输入 #1

样例输出 #1

271451044
271451044
969056313

提示

对于 \(5\%\) 的数据，\(n,Q \leq 100\)；

对于另 \(25\%\) 的数据，\(n \leq 2000\)；

对于 \(100\%\) 的数据，\(1\leq n \leq 20000\)，\(1\leq Q \leq 25000\)，\(1\leq a_i\leq 10 ^ 9\)。

解题思路

首先，看到中位数，我们可以考虑二分，将小于 \(mid\) 的值设为 \(-1\) ，将大于 \(mid\) 的值设为 \(1\) ，这样根据题中的定义，若一段区间的和大于等于 \(0\) ，说明这段区间的中位数是大于等于 \(mid\) 的。
但同时，它的区间的左右端点是不固定的，在 \(a,b\) 中选左端点，在 \(c,d\) 中选右端点，这样的话 \([b+1,c-1]\) 这部分是固定的，我们就需要解决一个类似找区间前缀和或后缀和最大的问题。
容易发现，这个可以用线段树解决。
我们可以据此 \(O(mnlog^2n)\) 的解决问题，连 \(mnlogn\) 都不如。
每次都重建线段树都太麻烦了，我们可以发现，离散化原序列后，它每次建的线段树最多就 \(n\) 中，这样的话，我们可以将这样的 \(n\) 种线段树处理出来，时间复杂度 \(O(n^2logn+mlog^2n)\) ，但空间复杂度到了 \(n^2\)。
从小到大的修改，它最多只会修改 \(n\) 次，每个数最多只修改 \(1\) 次，那我们可以尝试用可持久化线段树来解决了。
时间复杂度 \(O(nlogn+mlog^2n)\) 。

Code

#include<bits/stdc++.h>
using namespace std;
struct data
{
	long long x,y;
}b[200005];
struct datay
{
	long long v,lc,rc,ls,rs;
}a[1000005];
long long n,d[20005],root[20005],m,op[6],num,dd[20005];
set<long long> l;
map<long long,long long> p;
void up(long long x)
{
	a[x].v=a[a[x].lc].v+a[a[x].rc].v;
	a[x].ls=max(a[a[x].lc].ls,a[a[x].lc].v+a[a[x].rc].ls);
	a[x].rs=max(a[a[x].rc].rs,a[a[x].rc].v+a[a[x].lc].rs);
	return;
}
bool cmp(data q,data w)
{
	return q.x<w.x;
}
long long build(long long l,long long r)
{
	if(l==r)
	{
		a[++num].v=1;
		a[num].ls=a[num].rs=1;
		return num;
	}
	long long mid=(l+r)>>1,p=++num;
	a[p].lc=build(l,mid);
	a[p].rc=build(mid+1,r);
	up(p);
	return p;
}
long long dijah(long long x,long long l,long long r,long long k,long long v)
{
	if(l==r)
	{
		a[++num].v=v;
		a[num].ls=a[num].rs=v;
		return num;
	}
	long long mid=(l+r)>>1,p=++num;
	a[p]=a[x];
	if(k<=mid)a[p].lc=dijah(a[x].lc,l,mid,k,v);
	else a[p].rc=dijah(a[x].rc,mid+1,r,k,v);
	up(p);
	return p;
}
long long gaia_v(long long x,long long ql,long long qr,long long l,long long r)
{
	if(l>r)return 0;
	if(ql<=l&&r<=qr)return a[x].v;
	long long mid=(l+r)>>1,h=0;
	if(ql<=mid)h+=gaia_v(a[x].lc,ql,qr,l,mid);
	if(qr>mid)h+=gaia_v(a[x].rc,ql,qr,mid+1,r);
	return h;
}
datay gaia_s(long long x,long long ql,long long qr,long long l,long long r)
{
	if(ql<=l&&r<=qr)return a[x];
	long long mid=(l+r)>>1;
	if(qr<=mid)return gaia_s(a[x].lc,ql,qr,l,mid);
	if(mid<ql)return gaia_s(a[x].rc,ql,qr,mid+1,r);
	datay q=gaia_s(a[x].lc,ql,qr,l,mid),w=gaia_s(a[x].rc,ql,qr,mid+1,r);
	datay e;
	e.v=q.v+w.v;
	e.ls=max(q.ls,q.v+w.ls);
	e.rs=max(w.rs,w.v+q.rs);
	return e;
}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&b[i].x);
		l.insert(b[i].x);
	}
	long long g=0,xx,xy,yx,yy,ll,rr,mid;
	set<long long>::iterator q=l.begin();
	for(;q!=l.end();q++)
	{
		p[*q]=++g;
		d[g]=*q;
	}
	for(int i=1;i<=n;i++)b[i].x=p[b[i].x],b[i].y=i;
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++)dd[i]=d[b[i].x];
	root[0]=build(1,n);
	for(int i=1;i<=n;i++)
	{
		root[i]=dijah(root[i-1],1,n,b[i].y,-1);
	}
	long long s=0;
	scanf("%lld",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld%lld",&xx,&xy,&yx,&yy);
		op[1]=xx+s;
		op[2]=xy+s;
		op[3]=yx+s;
		op[4]=yy+s;
		op[1]%=n,op[2]%=n,op[3]%=n,op[4]%=n;
		sort(op+1,op+5);
		op[1]++,op[2]++,op[3]++,op[4]++;
		s=0;
		xx=op[1],xy=op[2],yx=op[3],yy=op[4];
		ll=1,rr=n;
		while(ll<=rr)
		{
			mid=(ll+rr)/2;
			if(gaia_s(root[mid-1],xx,xy,1,n).rs+gaia_v(root[mid-1],xy+1,yx-1,1,n)+gaia_s(root[mid-1],yx,yy,1,n).ls>=0)ll=mid+1,s=max(s,mid);
			else rr=mid-1;	
		}
		s=dd[s];
		printf("%lld\n",s);
	}








  return 0;
}