BZOJ 2653 middle

题目大意

给你一个序列，多次询问左端点在$[a,b]$，右端点在$[c,d]$的子序列的最大的中位数。

二分中位数，把大于等于中位数的看作1，小于的看作-1，于是问题转化成了求一段子序列的和大于等于0.

对于$[b,c]$这段区间可以直接求和，但是对于$[a,b]$,$[c,d]$却无从下手。

考虑用主席树维护，初始令所有数都为1，之后从小到大赋值为-1.维护一段区间包含左端点/右端点的最大区间和和整个区间的和，在查询的时候查询对应区间即可。

注意修改的时候是单点修改……线段树维护的是该区间而不是前缀和。

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
inline char nc()
{
	static char buf[100000],*p1,*p2;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int ri()
{
	int ret=0;char tmp=nc();
	while(!isdigit(tmp)) tmp=nc();
	while(isdigit(tmp)) ret=ret*10+(tmp-'0'),tmp=nc();
	return ret;
}
struct element{int id,vl;}e[20100];
bool cmp(const element &x,const element &y){return x.vl<y.vl;}
int n,m,q[4],la;
int sum[1000010],lsm[1000010],rsm[1000010],ls[1000010],rs[1000010],rt[1000010],pts;
int a[20010],b[20010],tot;
void pushup(int pos)
{
	sum[pos]=sum[ls[pos]]+sum[rs[pos]];
	lsm[pos]=max(lsm[ls[pos]],sum[ls[pos]]+lsm[rs[pos]]);
	rsm[pos]=max(rsm[rs[pos]],sum[rs[pos]]+rsm[ls[pos]]);
}
void build(int &pos,int l,int r)
{
	pos=++pts;
	if(l==r)
	{
		sum[pos]=lsm[pos]=rsm[pos]=1;
		return;
	}
	int mid=(l+r)>>1;
	build(ls[pos],l,mid),build(rs[pos],mid+1,r);
	pushup(pos);
}
void update(int lp,int &rp,int l,int r,int x)
{
	rp=++pts;
	if(l==r)
	{
		sum[rp]=lsm[rp]=rsm[rp]=-1;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) update(ls[lp],ls[rp],l,mid,x),rs[rp]=rs[lp];
	else update(rs[lp],rs[rp],mid+1,r,x),ls[rp]=ls[lp];
	pushup(rp);
}
void qyl(int pos,int l,int r,int x,int y)
{
	if(x<=l&&r<=y) {++tot,a[tot]=lsm[pos],b[tot]=sum[pos];return;}
	int mid=(l+r)>>1;
	if(x<=mid) qyl(ls[pos],l,mid,x,y);
	if(y>mid) qyl(rs[pos],mid+1,r,x,y);
}
void qyr(int pos,int l,int r,int x,int y)
{
	if(x<=l&&r<=y) {++tot,a[tot]=rsm[pos],b[tot]=sum[pos];return;}
	int mid=(l+r)>>1;
	if(y>mid) qyr(rs[pos],mid+1,r,x,y);
	if(x<=mid) qyr(ls[pos],l,mid,x,y);
}
int ql(int z,int x,int y)
{
	int i,ret=-0x3f3f3f3f;
	tot=0;
	qyl(rt[z],1,n,x,y);
	a[0]=b[0]=0;
	for(i=1;i<=tot;++i) ret=max(ret,b[i-1]+a[i]),b[i]+=b[i-1];
	return ret;
}
int qr(int z,int x,int y)
{
	int i,ret=-0x3f3f3f3f;
	tot=0;
	qyr(rt[z],1,n,x,y);
	a[0]=b[0]=0;
	for(i=1;i<=tot;++i) ret=max(ret,b[i-1]+a[i]),b[i]+=b[i-1];
	return ret;
}
int qs(int pos,int l,int r,int x,int y)
{
	if(x>y) return 0;
	if(x<=l&&r<=y) return sum[pos];
	int mid=(l+r)>>1,ret=0;
	if(x<=mid) ret+=qs(ls[pos],l,mid,x,y);
	if(y>mid) ret+=qs(rs[pos],mid+1,r,x,y);
	return ret;
}
int bisection(int a,int b,int c,int d)
{
	int l=0,r=n+1,mid;
	while(l<r)
	{
		mid=(l+r)>>1;
		if(qr(mid,a,b)+ql(mid,c,d)+qs(rt[mid],1,n,b+1,c-1)>=0) l=mid+1;
		else r=mid;
	}
	return e[l].vl;
}
int main()
{
	int i;
	n=ri();
	for(i=1;i<=n;++i) e[i].id=i,e[i].vl=ri();
	build(rt[0],1,n);
	sort(e+1,e+n+1,cmp);
	for(i=1;i<=n;++i) update(rt[i-1],rt[i],1,n,e[i].id);
	m=ri();
	while(m--)
	{
		q[0]=(ri()+la)%n,q[1]=(ri()+la)%n,q[2]=(ri()+la)%n,q[3]=(ri()+la)%n;
		sort(q,q+4);
		printf("%d\n",la=bisection(q[0]+1,q[1]+1,q[2]+1,q[3]+1));
	}
	return 0;
}