P2839 [国家集训队]middle

---

好妙的题啊，，，，

首先二分一个答案k，把数列里>=k的数置为1，<k的数置为0

这样数列最大和>=0就是k>=中位数，<0就是k<中位数

数列的最大和很好求哇

左边的最大后缀+中间+右边的最大前缀

主席树搞搞

完事了

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#define il inline

#define rg register

#define vd void

#define sta static

using namespace std;

il int gi(){

	rg int x=0,f=1;rg char ch=getchar();

	while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();

	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

	return x*f;

}

const int maxn=20010;

int a[maxn],b[maxn];

const int maxd=500001;

struct node{

	int tot,lmax,rmax;

	node operator+(const node&x)const{

		return (node){tot+x.tot,max(lmax,tot+x.lmax),max(x.rmax,rmax+x.tot)};

	}

}s[maxd];

int rt[maxn],ls[maxd],rs[maxd],id;

struct yyb{int p,a;}c[maxn];

il bool operator<(const yyb&a,const yyb&b){return a.a<b.a;}

#define mid ((l+r)>>1)

il vd build(int&x,int l,int r){

	x=++id;

	s[x]=(node){r-l+1,r-l+1,r-l+1};

	if(l==r)return;

	build(ls[x],l,mid),build(rs[x],mid+1,r);

}

il vd update(int&x,int l,int r,const int&p,const int&o){

	++id,ls[id]=ls[x],rs[id]=rs[x],s[id]=s[x];

	x=id;

	if(l==r){s[x]=(node){o,o,o};return;}

	if(p<=mid)update(ls[x],l,mid,p,o);

	else update(rs[x],mid+1,r,p,o);

	s[x]=s[ls[x]]+s[rs[x]];

}

il node query(const int&x,int l,int r,const int&L,const int&R){

	if(L>R)return(node){0,0,0};

	if(L<=l&&r<=R)return s[x];

	if(L<=mid)

		if(mid<R)return query(ls[x],l,mid,L,R)+query(rs[x],mid+1,r,L,R);

		else return query(ls[x],l,mid,L,R);

	else return query(rs[x],mid+1,r,L,R);

}

#undef mid

int main(){

	freopen("nt2012_middle.in","r",stdin);

	freopen("nt2012_middle.out","w",stdout);

	int n=gi(),m;

	for(rg int i=1;i<=n;++i)a[i]=b[i]=gi();

	sort(b+1,b+n+1);m=unique(b+1,b+n+1)-b-1;

	for(rg int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+m+1,a[i])-b;

	for(rg int i=1;i<=n;++i)c[i]=(yyb){i,a[i]+1};

	sort(c+1,c+n+1);

	build(rt[1],1,n);

	int p=1;

	for(rg int i=1;i<=n;++i){

		while(p<c[i].a)rt[p+1]=rt[p],++p;

		if(c[i].a<=m)update(rt[c[i].a],1,n,c[i].p,-1);

	}

	while(p<m)rt[p+1]=rt[p],++p;

	int l1,r1,l2,r2,l3,r3,l,r,mid,fafa[4],lst=0,sum;

	int q=gi();

	while(q--){

		for(rg int i=0;i<4;++i)fafa[i]=(gi()+lst)%n+1;

		sort(fafa,fafa+4);

		l1=fafa[0],r1=fafa[1],l2=fafa[1]+1,r2=fafa[2]-1,l3=fafa[2],r3=fafa[3];

		l=1,r=m;

		while(l<r){

			mid=((l+r)>>1)+1;

			sum=query(rt[mid],1,n,l1,r1).rmax+query(rt[mid],1,n,l2,r2).tot+query(rt[mid],1,n,l3,r3).lmax;

			(sum>=0)?l=mid:r=mid-1;

		}

		printf("%d\n",lst=b[l]);

	}

	return 0;

}