BZOJ.3110.[ZJOI2013]K大数查询(整体二分 树状数组/线段树)

时间：2023-03-10 05:54:25
BZOJ.3110.[ZJOI2013]K大数查询(整体二分 树状数组/线段树)

题目链接 BZOJ

洛谷

整体二分求的是第K小(利用树状数组)。求第K大可以转为求第\(n-K+1\)小，但是这样好像得求一个\(n\)。

注意到所有数的绝对值\(\leq N\)，将所有数的大小关系反过来 第\(K\)大就是第\(K\)小了。所有数\(A[i]\)改为\(n-A[i]\)，输出的时候也改为\(n-Ans[i]\)。

区间加入一个数\(C\)可以直接用线段树区间加，也可以树状数组维护常数会小很多。

\(n*m=2.5*1e9 > MAX\_INT\) 也是没谁了。。

现学了一波树状数组区间修改区间查询...->见这里。

洛谷Rank1在BZOJ上60多。。

树状数组：

//4976KB	1220MS

#include <cstdio>

#include <cctype>

#include <algorithm>

#define lb(x) (x&-x)

//#define gc() getchar()

#define MAXIN 50000

#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

typedef long long LL;

const int N=50005;

int n,m,A[N],Ans[N];

char IN[MAXIN],*SS=IN,*TT=IN;

struct Operation

{

	LL K; int l,r,pos;//K!=0:Query [l,r] K;	K=0:Add [l,r] pos.

	Operation() {}

	Operation(LL K,int l,int r,int p):K(K),l(l),r(r),pos(p) {}

}q[N],q1[N],q2[N];

inline int read()

{

	int now=0,f=1;register char c=gc();

	for(;!isdigit(c);c=='-'&&(f=-1),c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now*f;

}

inline LL readll()

{

	LL now=0,f=1;register char c=gc();

	for(;!isdigit(c);c=='-'&&(f=-1),c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now*f;

}

namespace T

{

	int n;

	LL sum1[N],sum2[N];

	inline void Modify(int p,int v)

	{

		for(int i=p; i<=n; i+=lb(i))

			sum1[i]+=v, sum2[i]+=p*v;

	}

	inline void Modify_Range(int l,int r,int v){

		Modify(l,v), Modify(r+1,-v);

	}

	inline LL Query(int p)

	{

		LL res1=0,res2=0;

		for(int i=p; i; i^=lb(i))

			res1+=sum1[i], res2+=sum2[i];

		return res1*(p+1)-res2;

	}

	inline LL Query_Range(int l,int r){

		return Query(r)-Query(l-1);

	}

}

void Solve(int l,int r,int h,int t)

{

	if(h>t) return;

	if(l==r){

		for(int i=h; i<=t; ++i) if(q[i].K) Ans[q[i].pos]=l;

		return;

	}

	bool goon=0;//无询问时直接return。

	for(int i=h; i<=t; ++i) if(q[i].K) {goon=1; break;}

	if(!goon) return;

	int mid=l+r>>1, t1=0, t2=0;

	for(int i=h; i<=t; ++i)

		if(q[i].K)

		{

			LL tmp=T::Query_Range(q[i].l,q[i].r);

			if(tmp>=q[i].K) q1[t1++]=q[i];

			else q[i].K-=tmp, q2[t2++]=q[i];

		}

		else

		{

			if(q[i].pos<=mid) T::Modify_Range(q[i].l,q[i].r,1), q1[t1++]=q[i];

			else q2[t2++]=q[i];

		}

	for(int i=0; i<t1; ++i) if(!q1[i].K) T::Modify_Range(q1[i].l,q1[i].r,-1);//q1→_→

	for(int i=0; i<t1; ++i) q[h+i]=q1[i];

	for(int i=0; i<t2; ++i) q[h+t1+i]=q2[i];

	Solve(l,mid,h,h+t1-1), Solve(mid+1,r,h+t1,t);

}

int main()

{

	T::n=n=read(), m=read(); int tot=0;

	for(int l,r,i=1; i<=m; ++i)

		if(read()==1) l=read(), r=read(), q[i]=Operation(0,l,r,n-read());

		else l=read(), r=read(), q[i]=Operation(readll(),l,r,++tot);

	Solve(-N,N,1,m);

	for(int i=1; i<=tot; ++i) printf("%d\n",n-Ans[i]);

	return 0;

}

线段树：（常数大的一匹）

//7320kb	6064ms

#include <cstdio>

#include <cctype>

#include <algorithm>

//#define gc() getchar()

#define MAXIN 50000

#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

typedef long long LL;

const int N=50005;

int n,m,A[N],Ans[N];

char IN[MAXIN],*SS=IN,*TT=IN;

struct Operation

{

	LL K; int l,r,pos;//K!=0:Query [l,r] K;	K=0:Add [l,r] pos.

	Operation() {}

	Operation(LL K,int l,int r,int p):K(K),l(l),r(r),pos(p) {}

}q[N],q1[N],q2[N];

inline int read()

{

	int now=0,f=1;register char c=gc();

	for(;!isdigit(c);c=='-'&&(f=-1),c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now*f;

}

inline LL readll()

{

	LL now=0,f=1;register char c=gc();

	for(;!isdigit(c);c=='-'&&(f=-1),c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now*f;

}

namespace T

{

	#define lson rt<<1

	#define rson rt<<1|1

	#define ToL l,m,rt<<1

	#define ToR m+1,r,rt<<1|1

	LL sum[N<<2],tag[N<<2];

	inline void Update(int rt){

		sum[rt]=sum[lson]+sum[rson];

	}

	inline void PushDown(int rt,LL m)//long long!

	{

		tag[lson]+=tag[rt], tag[rson]+=tag[rt];

		sum[lson]+=tag[rt]*(m-(m>>1)), sum[rson]+=tag[rt]*(m>>1);

		tag[rt]=0;

	}

	void Modify(int l,int r,int rt,int L,int R,int v)

	{

		if(L<=l && r<=R)

			tag[rt]+=v, sum[rt]+=1ll*(r-l+1)*v;

		else

		{

			if(tag[rt]) PushDown(rt,r-l+1);

			int m=l+r>>1;

			if(L<=m) Modify(ToL,L,R,v);

			if(m<R) Modify(ToR,L,R,v);

			Update(rt);

		}

	}

	LL Query(int l,int r,int rt,int L,int R)

	{

		if(L<=l && r<=R) return sum[rt];

		if(tag[rt]) PushDown(rt,r-l+1);

		int m=l+r>>1;

		if(L<=m)

			if(m<R) return Query(ToL,L,R)+Query(ToR,L,R);

			else return Query(ToL,L,R);

		return Query(ToR,L,R);

	}

}

void Solve(int l,int r,int h,int t)

{

	if(h>t) return;

	if(l==r){

		for(int i=h; i<=t; ++i) if(q[i].K) Ans[q[i].pos]=l;

		return;

	}

	bool goon=0;//无询问时直接return。

	for(int i=h; i<=t; ++i) if(q[i].K) {goon=1; break;}

	if(!goon) return;

	int mid=l+r>>1, t1=0, t2=0;

	for(int i=h; i<=t; ++i)

		if(q[i].K)

		{

			LL tmp=T::Query(1,n,1,q[i].l,q[i].r);

			if(tmp>=q[i].K) q1[t1++]=q[i];

			else q[i].K-=tmp, q2[t2++]=q[i];

		}

		else

		{

			if(q[i].pos<=mid) T::Modify(1,n,1,q[i].l,q[i].r,1), q1[t1++]=q[i];

			else q2[t2++]=q[i];

		}

	for(int i=0; i<t1; ++i) if(!q1[i].K) T::Modify(1,n,1,q1[i].l,q1[i].r,-1);//q1→_→

	for(int i=0; i<t1; ++i) q[h+i]=q1[i];

	for(int i=0; i<t2; ++i) q[h+t1+i]=q2[i];

	Solve(l,mid,h,h+t1-1), Solve(mid+1,r,h+t1,t);

}

int main()

{

	n=read(), m=read(); int tot=0;

	for(int l,r,i=1; i<=m; ++i)

		if(read()==1) l=read(), r=read(), q[i]=Operation(0,l,r,n-read());

		else l=read(), r=read(), q[i]=Operation(readll(),l,r,++tot);

	Solve(-N,N,1,m);

	for(int i=1; i<=tot; ++i) printf("%d\n",n-Ans[i]);

	return 0;

}

线段树 标记永久化：WA了，不知道该怎么着。。（应该没问题啊）

//标记永久化替代PushDown可以减小常数，但是怎么不对exm？

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

typedef long long LL;

const int N=50005;

int n,m,A[N],Ans[N];

struct Operation

{

	LL K; int l,r,pos;//K!=0:Query [l,r] K;	K=0:Add [l,r] pos.

	Operation() {}

	Operation(LL K,int l,int r,int p):K(K),l(l),r(r),pos(p) {}

}q[N],q1[N],q2[N];

inline int read()

{

	int now=0,f=1;register char c=gc();

	for(;!isdigit(c);c=='-'&&(f=-1),c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now*f;

}

inline LL readll()

{

	LL now=0,f=1;register char c=gc();

	for(;!isdigit(c);c=='-'&&(f=-1),c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now*f;

}

namespace T

{

	#define lson rt<<1

	#define rson rt<<1|1

	#define ToL l,m,rt<<1

	#define ToR m+1,r,rt<<1|1

	LL sum[N<<2],all[N<<2];

	void Modify(int l,int r,int rt,int L,int R,int v)

	{

		sum[rt]+=1ll*v*(R-L+1);

		if(L<=l && r<=R) all[rt]+=v;

		else

		{

			int m=l+r>>1;

			if(L<=m) Modify(ToL,L,m,v);

			if(m<R) Modify(ToR,m+1,R,v);

		}

	}

	LL Query(int l,int r,int rt,int L,int R)

	{

		if(L<=l && r<=R) return sum[rt];

		int m=l+r>>1;

		if(L<=m)

			if(m<R) return 1ll*all[rt]*(R-L+1)+Query(ToL,L,R)+Query(ToR,L,R);

			else return 1ll*all[rt]*(R-L+1)+Query(ToL,L,R);

		return 1ll*all[rt]*(R-L+1)+Query(ToR,L,R);

	}

}

void Solve(int l,int r,int h,int t)

{

	if(h>t) return;

	if(l==r){

		for(int i=h; i<=t; ++i) if(q[i].K) Ans[q[i].pos]=l;

		return;

	}

	bool goon=0;//无询问时直接return。

	for(int i=h; i<=t; ++i) if(q[i].K) {goon=1; break;}

	if(!goon) return;

	int mid=l+r>>1, t1=0, t2=0;

	for(int i=h; i<=t; ++i)

		if(q[i].K)

		{

			LL tmp=T::Query(1,n,1,q[i].l,q[i].r);

			if(tmp>=q[i].K) q1[t1++]=q[i];

			else q[i].K-=tmp, q2[t2++]=q[i];

		}

		else

		{

			if(q[i].pos<=mid) T::Modify(1,n,1,q[i].l,q[i].r,1), q1[t1++]=q[i];

			else q2[t2++]=q[i];

		}

	for(int i=0; i<t1; ++i) if(!q1[i].K) T::Modify(1,n,1,q1[i].l,q1[i].r,-1);//q1

	for(int i=0; i<t1; ++i) q[h+i]=q1[i];

	for(int i=0; i<t2; ++i) q[h+t1+i]=q2[i];

	Solve(l,mid,h,h+t1-1), Solve(mid+1,r,h+t1,t);

}

int main()

{

	n=read(), m=read(); int tot=0;

	for(int l,r,i=1; i<=m; ++i)

		if(read()==1) l=read(), r=read(), q[i]=Operation(0,l,r,n-read());

		else l=read(), r=read(), q[i]=Operation(readll(),l,r,++tot);

	Solve(-N,N,1,m);

	for(int i=1; i<=tot; ++i) printf("%d\n",n-Ans[i]);

	return 0;

}

相关文章