整体二分学习笔记

整体二分，就是把查询放到一起二分，从而降低代码复杂度的一种离线算法。所以想要使用整体二分需要保证查询的答案具有单调性和操作可以离线。

首先看一道例题：

有一个空的可重集和 $m$ 个操作，每个操作有类型 $tpe_i$ 和一个参数 $x_i$。$tpe_i=1$ 的操作表示往可重集里添加 $x_i$，$tpe=_i2$ 的操作表示询问可重集内第 $x_i$ 小的数。

$1\le m\le 10^5$

显然这道题可以用平衡树做，但是它太难写了。观察到答案具有单调性，所以可以二分答案，用一个数据结构维护当前可重集内小于 $mid$ 的数的个数即可。这样的时间复杂度是 $O(m\log m)$ 的，但是仍然很难写。

考虑降低代码复杂度。我们可以先把所有操作离线下来，然后对于所有操作一起二分。“一起二分”就是将答案在 $[l,r]$ 区间内的询问和对这些询问的答案有影响的修改操作一起处理，设 $cur$ 表示 $[l,r]$ 内的操作序列，那么显然若 $l=r$，那么我们就已经找到答案了。

考虑 $l\not=r$ 的情况。设 $mid=\left\lfloor\dfrac{l+r}{2}\right\rfloor$，那么我们需要把 $cur$ 分为两个操作序列 $lft$ 和 $rig$，其中 $lft$ 的答案在 $[l,mid]$ 内，$rig$ 的答案在 $[mid+1,r]$ 内，这样我们递归下去就可以求出答案了。

考虑怎么分组。对于修改操作 $i$，显然若 $x_i \le mid$ 那么这个操作会对 $lft$ 和 $rig$ 造成影响，但为了保证时间复杂度，我们只将它放入 $lft$ 中；否则只会对 $rig$ 造成影响，放入 $rig$ 中。

而对于询问操作 $i$，我们可以计算出操作序列执行到 $i$ 时可重集内比 $mid$ 小的数的个数 $k$。若 $k\ge x_i$，那么说明当前 $mid$ 大了或者对了，这个询问操作需要分到 $lft$ 里；否则说明当前 $mid$ 小了，这个询问操作需要分到 $rig$ 里。 但是注意，$k<x_i$ 即 $i$ 被分到 $rig$ 时，需要将 $x_i$ 减去 $k$。因为我们加入修改操作时把所有对两个操作序列都有影响的操作放进了 $lft$ 而没有加入 $rig$，所以我们需要额外计算上这些修改的贡献。

容易发现，计算操作序列执行到 $i$ 时可重集内比 $mid$ 小的数的个数 $k$ 可以用一个变量 $cnt$ 简单统计。然后递归的层数是 $\log m$，每一层会遍历一次所有操作，所以时间复杂度为 $O(m\log m)$。

考虑如何求第 $k$ 大值。显然可以只有分组部分有变化：

对于修改操作 $i$，显然若 $x_i > mid$ 那么这个操作会对 $lft$ 和 $rig$ 造成影响，但为了保证时间复杂度，我们只将它放入 $rig$ 中；否则只会对 $lft$ 造成影响，放入 $lft$ 中。

而对于询问操作 $i$，我们可以计算出操作序列执行到 $i$ 时可重集内比 $mid$ 大的数的个数 $k$。若 $k>=x_i$，那么说明当前 $mid$ 小了，这个询问操作需要分到 $rig$ 里；否则说明当前 $mid$ 大了或者对了，这个询问操作需要分到 $lft$ 里。但是注意，$k<x_i$ 即 $i$ 被分到 $lft$ 时，需要将 $x_i$ 减去 $k$。因为我们加入修改操作时把所有对两个操作序列都有影响的操作放进了 $rig$ 而没有加入 $lft$，所以我们需要额外计算上这些修改的贡献。

那么现在来看道例题吧：

P3332 [ZJOI2013]K大数查询

显然还是分组过程变了。发现变动的地方只是单点修改，整段查询变成了区间修改，区间查询。所以用线段树维护 $[l,r]$ 内可重集的并内比 $mid$ 大的数的个数 $k$ 即可。

代码如下：

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const long long MS=50005;

struct node
{
	int tpe,l,r,id;
	long long val;
};

int n,m,quecnt;
int ans[MS];
long long sum[MS<<2],lazy[MS<<2];

inline void updata(int u)
{
	sum[u]=sum[u<<1]+sum[u<<1|1];
}

inline void lazydown(int u,int l,int r)
{
	if(lazy[u]==0)
	{
		return;
	}
	int mid=l+r>>1;
	lazy[u<<1]+=lazy[u];
	lazy[u<<1|1]+=lazy[u];
	sum[u<<1]+=lazy[u]*(mid-l+1);
	sum[u<<1|1]+=lazy[u]*(r-mid);
	lazy[u]=0;
}

void upd(int u,int l,int r,int L,int R,long long k)
{
	if(r<L||l>R)
	{
		return;
	}
	if(l>=L&&r<=R)
	{
		lazy[u]+=k;
		sum[u]+=k*(r-l+1);
		return;
	}
	lazydown(u,l,r);
	int mid=l+r>>1;
	if(L<=mid)
	{
		upd(u<<1,l,mid,L,R,k);
	}
	if(R>=mid+1)
	{
		upd(u<<1|1,mid+1,r,L,R,k);
	}
	updata(u); 
}

long long que(int u,int l,int r,int L,int R)
{
	if(r<L||l>R)
	{
		return 0;
	}
	if(l>=L&&r<=R)
	{
		return sum[u];
	}
	lazydown(u,l,r);
	int mid=l+r>>1;
	long long res=0;
	if(L<=mid)
	{
		res+=que(u<<1,l,mid,L,R);
	}
	if(R>=mid+1)
	{
		res+=que(u<<1|1,mid+1,r,L,R);
	}
	return res;
}

void slove(int l,int r,vector<node> &cur)
{
	if(l==r)
	{
		for(node x:cur)
		{
			if(x.tpe==2)
			{
				ans[x.id]=l;
			}
		}
		return;
	}
	int mid=l+r>>1;
	vector<node> lft,rig;
	for(node x:cur)
	{
		if(x.tpe==1)
		{
			if(x.val<=mid)
			{
				lft.push_back(x);
			}
			else
			{
				rig.push_back(x);
				upd(1,1,n,x.l,x.r,1);
			}
		}
		else
		{
			long long vl=que(1,1,n,x.l,x.r);
			if(vl>=x.val)
			{
				rig.push_back(x);
			}
			else
			{
				x.val-=vl;
				lft.push_back(x);
			}
		}
	}
	for(node x:rig)
	{
		if(x.tpe==1)
		{
			upd(1,1,n,x.l,x.r,-1);
		}
	}
	if(lft.size()>0)
	{
		slove(l,mid,lft);
	}
	if(rig.size()>0)
	{
		slove(mid+1,r,rig);
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	vector<node> a;
	for(int i=1;i<=m;i++)
	{
		node x;
		scanf("%d%d%d%lld",&x.tpe,&x.l,&x.r,&x.val);
		if(x.tpe==2)
		{
			x.id=++quecnt;
		}
		a.push_back(x);
	}
	slove(-n,n,a);
	for(int i=1;i<=quecnt;i++)
	{
		printf("%d\n",ans[i]);
	}
	return 0;
}

练习题目

• P3527 [POI2011]MET-Meteors