[洛谷2839/国家集训队]middle

Description

一个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号,除法取下整。给你一个长度为n的序列s。回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。

其中a<b<c<d。位置也从0开始标号。我会使用一些方式强制你在线。

Input

第一行序列长度n。接下来n行按顺序给出a中的数。

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

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

将q从小到大排序之后，令真正的要询问的a=q[0],b=q[1],c=q[2],d=q[3]。　　

输入保证满足条件。

第一行所谓“排过序”指的是从小到大排序！

n<=20000,Q<=25000

Output

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

Sample Input

5

170337785

271451044

22430280

969056313

206452321

3

3 1 0 2

2 3 1 4

3 1 4 0

Sample Output

271451044

271451044

969056313

首先这题是肯定具有可二分性的，那么我们按照权值大小顺序建立n棵主席树，对于每个权值下的主席树，其叶子节点表示位置l上的数是否小于自己，如果小于自己，则位置l的叶子节点点值为-1，大于等于则为1

这样子我们就可以在主席树的每个节点上记录前缀最大值和后缀最大值，每次二分答案的时候，判断[a,b]的后缀最大值+(b,c)的权值和+[c,d]的后缀最大值是否\(\geqslant 0\)

如果是，则l上移，否则r下移

/*program from Wolfycz*/

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 0x7f7f7f7f

using namespace std;

typedef long long ll;

typedef unsigned int ui;

typedef unsigned long long ull;

inline char gc(){

	static char buf[1000000],*p1=buf,*p2=buf;

	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;

}

inline int frd(){

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

	for (;ch<'0'||ch>'9';ch=gc())	if (ch=='-')	f=-1;

	for (;ch>='0'&&ch<='9';ch=gc())	x=(x<<3)+(x<<1)+ch-'0';

	return x*f;

}

inline int read(){

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

	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')	f=-1;

	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<3)+(x<<1)+ch-'0';

	return x*f;

}

inline void print(int x){

	if (x<0)	putchar('-'),x=-x;

	if (x>9)	print(x/10);

	putchar(x%10+'0');

}

const int N=2e4,M=5e5;

int list[N+10],root[N+10],pos[N+10],n,T;

struct S1{

	int v,ID;

	void insert(int i){v=read(),ID=i;}

	bool operator <(const S1 &tis)const{return v<tis.v;}

}val[N+10];

struct S2{

	struct node{

		int sum,Lf,Rg;

		node(){sum=0,Lf=Rg=-inf;}

		void insert(int x){sum=Lf=Rg=x;}

	}tree[M+10];

	int ls[M+10],rs[M+10],tot;

	friend node operator +(const node &x,const node &y){

		node z;

		z.Lf=max(x.Lf,x.sum+y.Lf);

		z.Rg=max(y.Rg,y.sum+x.Rg);

		z.sum=x.sum+y.sum;

		return z;

	}

	void build(int &p,int l,int r,int x){

		p=++tot;

		if (l==r){

			tree[p].insert(l==x?1:-1);

			return;

		}

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

		build(ls[p],l,mid,x);

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

		tree[p]=tree[ls[p]]+tree[rs[p]];

	}

	void insert(int &p,int k,int l,int r,int x){

		tree[p=++tot]=tree[k];

		ls[p]=ls[k],rs[p]=rs[k];

		if (l==r){

			tree[p].insert(1);

			return;

		}

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

		if (x<=mid)	insert(ls[p],ls[k],l,mid,x);

		else	insert(rs[p],rs[k],mid+1,r,x);

		tree[p]=tree[ls[p]]+tree[rs[p]];

	}

	node Query(int p,int l,int r,int x,int y){

		if (x<=l&&r<=y)	return tree[p];

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

		if (y<=mid)	return Query(ls[p],l,mid,x,y);

		if (x>mid)	return Query(rs[p],mid+1,r,x,y);

		return Query(ls[p],l,mid,x,y)+Query(rs[p],mid+1,r,x,y);

	}

}CT;//Chairman Tree

int Q[5];

bool check(int limit){

	int res=0;

	if (Q[1]+1<=Q[2]-1)	res+=CT.Query(root[limit],1,n,Q[1]+1,Q[2]-1).sum;

	res+=CT.Query(root[limit],1,n,Q[0],Q[1]).Rg;

	res+=CT.Query(root[limit],1,n,Q[2],Q[3]).Lf;

	return res>=0;

}

int Binary_Search(){

	int l=1,r=T;

	while (l<=r){

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

		if (check(mid))	l=mid+1;

		else	r=mid-1;

	}

	return r;

}

void init(int x){

	Q[0]=(read()+x)%n,Q[1]=(read()+x)%n,Q[2]=(read()+x)%n,Q[3]=(read()+x)%n;

	for (int i=0;i<4;i++)	Q[i]++;

	sort(Q,Q+4);

}

int main(){

	n=read();

	for (int i=1;i<=n;i++)	val[i].insert(i);

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

	for (int i=1;i<=n;i++)	list[i]=val[i].v;

	T=unique(list+1,list+1+n)-list-1;

	for (int i=1;i<=n;i++)	val[i].v=lower_bound(list+1,list+1+T,val[i].v)-list;

	CT.build(root[val[n].v],1,n,val[n].ID);

	for (int i=n-1;i;i--)	CT.insert(root[val[i].v],root[val[i+1].v],1,n,val[i].ID);

	int m=read(),lastans=0;

	for (int i=1;i<=m;i++){

		init(lastans);

		printf("%d\n",lastans=list[Binary_Search()]);

	}

	return 0;

}

巴特西

[洛谷2839/国家集训队]middle

最新文章

热门文章