BZOJ3110：[ZJOI2013]K大数查询(整体二分版)

浅谈离线分治算法：https://www.cnblogs.com/AKMer/p/10415556.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=3110

同BZOJ1901，不过是把单点修改区间询问改成区间修改区间询问罢了。

我怕会\(TLE\)，就用了区间修改区间询问的树状数组。如果还不会这个的，可以去看看这篇博客。

时间复杂度：\(O(mlog^2n)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

using namespace std;

typedef long long ll;

#define low(i) ((i)&(-(i)))

const int maxn=5e4+5;

bool bo[maxn];

int ans[maxn];

int n,m,ans_cnt;

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*10+ch-'0';

	return x*f;

}

struct Oper {

	int opt,l,r,k,id;

}p[maxn],tmp[maxn];

struct tree_array {

	ll c[maxn];

	void add(int pos,int v) {

		if(!pos)return;

		for(int i=pos;i<=n;i+=low(i))

			c[i]+=v;

	}

	ll query(int pos) {

		ll res=0;

		for(int i=pos;i;i-=low(i))

			res+=c[i];

		return res;

	}

}T1,T2;

ll ask(int pos) {

	return 1ll*(pos+1)*T1.query(pos)-T2.query(pos);

}

void solve(int l,int r,int st,int ed) {

	if(ed<st)return;

	if(l==r) {

		for(int i=st;i<=ed;i++)

			if(p[i].id)ans[p[i].id]=l;

		return;

	}

	int mid=(l+r)>>1,cnt=0;

	for(int i=st;i<=ed;i++)

		if(p[i].opt==1) {

			if(p[i].k>mid) {

				bo[i]=0;

				T1.add(p[i].l,1),T1.add(p[i].r+1,-1);

				T2.add(p[i].l,p[i].l),T2.add(p[i].r+1,-1-p[i].r);

			}

			else bo[i]=1,cnt++;

		}

		else {

			ll res=ask(p[i].r)-ask(p[i].l-1);

			if(res>=p[i].k)bo[i]=0;

			else bo[i]=1,p[i].k-=res,cnt++;

		}

	for(int i=st;i<=ed;i++)

		if(p[i].opt==1&&p[i].k>mid) {

			T1.add(p[i].l,-1),T1.add(p[i].r+1,1);

			T2.add(p[i].l,-p[i].l),T2.add(p[i].r+1,p[i].r+1);

		}

	int ED=st,ST=st+cnt;

	for(int i=st;i<=ed;i++)

		if(bo[i])tmp[ED++]=p[i];

		else tmp[ST++]=p[i];

	for(int i=st;i<=ed;i++)

		p[i]=tmp[i];

	solve(l,mid,st,ED-1),solve(mid+1,r,ED,ed);

}

int main() {

	n=read(),m=read();

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

		p[i].opt=read(),p[i].l=read(),p[i].r=read(),p[i].k=read();

		if(p[i].opt==2)p[i].id=++ans_cnt;

	}

	solve(1,n,1,m);

	for(int i=1;i<=ans_cnt;i++)

		printf("%d\n",ans[i]);

	return 0;

}

巴特西

BZOJ3110：[ZJOI2013]K大数查询(整体二分版)

最新文章

热门文章