分治 | 二分 | 整体二分: 学习笔记

整体二分

在信息学竞赛中,有一部分题可以使用二分的办法来解决。但是当这种题目有多次询问且每次询问我们对每个查询都直接二分,可能会收获一个 TLE。这时候我们就会用到整体二分。整体二分的主体思路就是把多个查询一起解决,所以这是一个离线算法(摘自 OI Wiki)

适用性

可以使用整体二分法解决的问题具有如下性质:

  1. 询问的答案具有可二分性

  2. 修改对判定答案的贡献互相独立 ,修改之间互不影响效果

  3. 修改如果对判定答案有贡献,则贡献为一确定的与判定标准无关的值

  4. 贡献满足交换律,结合律,具有可加性

  5. 题目允许使用离线算法(显然)

思路或模板

一般的二分是对连续某次操作下(操作数为 $mid$ 的操作)进行判定,根据判定结果修改答案值域,值域不断缩小,逼近正确答案的过程,可以看出一般的二分仅对一个询问起作用

而整体二分可以处理一坨询问,自然需要一个存储询问结果的数组,由于一次猜的答案需要拿去同时与多个询问进行判定,整体二分的大致思路如下:

  1. 确定处理询问的区间:$[x,\;y]$(即处理第 $x$ 个到第 $y$ 个询问),确定答案值域:$[L,\;R]$ (二分的灵魂)
  2. 首先,若进行到 $L=R$ 的这一步,说明答案已经确定,将当前区间内询问的答案全部赋值为 $L$ ,当然这只是暂时的,一个询问的答案可能被赋值多次,然后直接 return
  3. 用猜的答案 $mid$ 同时与区间内的询问作比较,设置两个数组 $newL$ 和 $newR$,对于那些答案过大的询问,放入 $newL$ 中,答案过小的询问,放入 $newR$ 中
  4. 同时更新答案值域和询问区间,按照先后顺序将 $newL$ 到 $newR$ 中的询问覆盖掉原来区间内的询问
  5. 递归处理,若 $newL$ 中有 $xL$ 个询问,则递归处理的询问区间分别为:$[x,\; x+xL-1]$ 和 $[x+xL,\; y]$,答案值域为 $[L,\;mid]$ 和 $[mid+1,\;R]$

可以发现,整体二分和 CDQ 分治相似,第 4 步类似 CDQ 分治中的合并操作,这里可以理解成划分,将有二分价值的询问划分到一起,保证下一步二分时,对应区间内询问的答案一定在对应的答案值域内,如果没有这一步,那么很多询问的答案都无法精确

思路中第 3 步的比较或检验是决定时间复杂度的关键,通常这一步都会采用一些数据结构优化时间复杂度

下面根据这个思路看几道例题

洛谷P3834 【模板】可持久化线段树 1(主席树)

Description

给定N个整数构成的序列,将对于指定的闭区间查询其区间内的第K小值。

Input

第一行包含两个正整数N、M,分别表示序列的长度和查询的个数。

第二行包含N个整数,表示这个序列各项的数字。

接下来M行每行包含三个整数l,r,k , 表示查询区间[l,r]内的第k小值。

Output

输出包含k行,每行1个整数,依次表示每一次查询的结果

Sample Input

5 5
25957 6405 15770 26287 26465 
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

Sample Output

6405
15770
26287
25957
26287

Hint

20%的数据,$1\leq N,M \leq 10$

50%的数据,$1\leq N,M \leq 10^3$

80%的数据,$1\leq N,M \leq 10^5$

100%的数据,$1\leq N,M \leq 2\times 10^5$

数列中的数 $a_i$ 满足 $-10^9\leq a_i \leq 10^9$

分析

这个题以前曾是令人闻风丧胆的主席树的板子题,由于题目支持离线操作,现在我们也可以用整体二分解决,把所有询问存到数组里面,对所有询问,二分第 $k$ 小的数并检验,从而离线得出全部询问的答案并输出

具体的说,对于区间 $[x,\;y]$ 内的询问,二分一个 $mid$,然后对于每个询问,查询得到在区间内有 $C$ 个数 $mid$ 小, 个,通过比较 $C$ 和 $k$ 的大小划分这 $y-x+1$ 个询问到 $newL$ 和 $newR$ 中,然后覆盖掉原来的区间,递归处理询问,直到 $L=R$ 的时候,就直接把区间 $[x,\;y]$ 内的询问答案全部赋值为 $L$

划分时注意,若要将操作 $p$ 划分至 $newR$ 中,那么要将其对应的 $k$ 减去 $C$($C$ 为当前区间比 $mid$ 小的数的个数)

统计在区间内有多少个数比 $mid$ 小,这可以用树状数组实现(就像统计逆序对数那样),要注意树状数组要及时清空,以免对下一个区间的判定产生影响

Codes

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxn 200005
#define lowbit(x) (x&-x)
#define mid ((L+R)>>1)
using namespace std;
const int inf=(int)1e9+1; 
template<typename t>inline void fcin(t &x){
	int sign=1; x=0; char op=getchar();
	while(op<'0'||op>'9'){if(op=='-') sign=-1;op=getchar();}
	while(op>='0'&&op<='9'){x=x*10+(op-48);op=getchar();}
	x*=sign;
}
struct node{
	int pos,val;
	int id,l,r,k; int type;
	inline void get_asVal(int p,int v){pos=p;val=v;type=1;}
	inline void get_asAsk(int i,int a,int b,int c){id=i;l=a;r=b;k=c;type=2;}
}q[maxn<<1],q1[maxn<<1],q2[maxn<<1];
int n,m,ans[maxn],T[maxn],cnt;
inline void updata(int p,int d){
	for(int i=p;i<=n;i+=lowbit(i))
		T[i]+=d;
}
int res(int p){
	int ret=0;
	for(int i=p;i;i-=lowbit(i))
		ret+=T[i];
	return ret;
}
void solve(int L,int R,int x,int y){
	if(L==R){
		for(int i=x;i<=y;i++)
			if(q[i].type==2) ans[q[i].id]=L;
		return;
	} int qcnt1=0,qcnt2=0,t;
	for(int i=x;i<=y;i++){
		if(q[i].type==1){
			if(q[i].val<=mid) updata(q[i].pos,1),q1[++qcnt1]=q[i];
			else q2[++qcnt2]=q[i];
		}else{
			t=res(q[i].r)-res(q[i].l-1);
			if(q[i].k<=t) q1[++qcnt1]=q[i];
			else q[i].k-=t,q2[++qcnt2]=q[i];
		}
	} memset(T,0,sizeof(T));
	for(int i=1;i<=qcnt1;i++) q[x+i-1]=q1[i];
	for(int i=1;i<=qcnt2;i++) q[x+i-1+qcnt1]=q2[i];
	solve(L,mid,x,x+qcnt1-1);solve(mid+1,R,x+qcnt1,y);
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("testin.txt","r",stdin);
	freopen("testout.txt","w",stdout);
	#endif
	fcin(n);fcin(m);int A,B,C,mL=inf,mR=-inf;
	for(int i=1;i<=n;i++){
		fcin(A),q[++cnt].get_asVal(i,A);
		mL=min(mL,A);mR=max(mR,A);
	}
	for(int i=1;i<=m;i++){
		fcin(A);fcin(B);fcin(C);
		q[++cnt].get_asAsk(++ans[0],A,B,C);
	} solve(mL,mR,1,cnt);
	for(int i=1;i<=ans[0];i++) printf("%d\n",ans[i]);
	return 0;
}

洛谷P2617 Dynamic Rankings

Description

给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)

并且,你可以改变一些a[i]的值,改变后,程序还能针对改变后的a继续回答上面的问题。

你需要编一个这样的程序,从输入文件中读入序列a,然后读入一系列的指令,包括询问指令和修改指令。

Input

第一行有两个正整数n(1≤n≤100000),m(1≤m≤100000)。分别表示序列的长度和指令的个数。

第二行有n个数,表示a[1],a[2]……a[n],这些数都小于10^9。接下来的m行描述每条指令,每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t

  • Q i j k (i,j,k是数字,1≤i≤j≤n, 1≤k≤j-i+1)表示询问指令,询问a[i],a[i+1]……a[j]中第k小的数。
  • C i t (1≤i≤n,0≤t≤10^9)表示把a[i]改变成为t。

Output

对于每一次询问,你都需要输出他的答案,每一个输出占单独的一行。

Sample Input

5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

Sample Output

3
6

Hint

10%的数据中,m,n≤100;

20%的数据中,m,n≤1000;

50%的数据中,m,n≤10000。

对于所有数据,m,n≤100000

分析

本题是涉及修改操作的区间 K 小值,而像 CDQ 分治那样,我们同样可以将修改操作和询问操作合并到一个数组里面(上面的代码已经体现了这一点)

合并之后动态处理,如果是修改操作,就更新树状数组,同时将这个操作放在 $newL$ 中,这是因为修改操作能影响其后面的查询操作,因此需要优先处理,如果是查询操作,按照上一个题的处理方法即可

需要注意的是,修改操作有正向的(添加值)也有负向的(擦除值),体现在题目中就是一个元素的修改可以看做先擦除这个元素,再添加修改后的元素,一共 2 个修改操作,因此,为了不影响下一次区间的检验,处理完毕后需要对树状数组处理,即把当前区间 $[x,\;y]$ 内的修改操作全部反向执行(其实就是系数乘上 -1)

Codes

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxn 200005
#define lowbit(x) (x&-x)
#define mid ((L+R)>>1)
using namespace std;
const int inf=(int)1e9+1; 
template<typename t>inline void fcin(t &x){
	int sign=1; x=0; char op=getchar();
	while(op<'0'||op>'9'){if(op=='-') sign=-1;op=getchar();}
	while(op>='0'&&op<='9'){x=x*10+(op-48);op=getchar();}
	x*=sign;
}
struct node{
	int pos,val,alpha;
	int id,l,r,k; int type;
	inline void get_asVal(int p,int v,int al){pos=p;val=v;alpha=al;type=1;}
	inline void get_asAsk(int i,int a,int b,int c){id=i;l=a;r=b;k=c;type=2;}
}q[maxn<<2],q1[maxn<<2],q2[maxn<<2];
int n,m,ans[maxn],T[maxn],cnt;
inline void updata(int p,int d){
	for(int i=p;i<=n;i+=lowbit(i))
		T[i]+=d;
}
int res(int p){
	int ret=0;
	for(int i=p;i;i-=lowbit(i))
		ret+=T[i];
	return ret;
}
void solve(int L,int R,int x,int y){
	if(x>y) return; 
	if(L==R){
		for(int i=x;i<=y;i++)
			if(q[i].type==2) ans[q[i].id]=L;
		return;
	} int qcnt1=0,qcnt2=0,t;
	for(int i=x;i<=y;i++){
		if(q[i].type==1){
			if(q[i].val<=mid) 
				updata(q[i].pos,q[i].alpha),q1[++qcnt1]=q[i];
			else q2[++qcnt2]=q[i];
		}else{
			t=res(q[i].r)-res(q[i].l-1);
			if(q[i].k<=t) q1[++qcnt1]=q[i];
			else q[i].k-=t,q2[++qcnt2]=q[i];
		}
	} 
	for(int i=1;i<=qcnt1;i++)
		if(q1[i].type==1) updata(q1[i].pos,-q1[i].alpha);
	for(int i=1;i<=qcnt1;i++) q[x+i-1]=q1[i];
	for(int i=1;i<=qcnt2;i++) q[x+i-1+qcnt1]=q2[i];
	solve(L,mid,x,x+qcnt1-1);solve(mid+1,R,x+qcnt1,y);
}
int s[maxn];
int main(){
	#ifndef ONLINE_JUDGE
	freopen("testin.txt","r",stdin);
	freopen("testout.txt","w",stdout);
	#endif
	fcin(n);fcin(m);int A,B,C,mL=inf,mR=-inf;
	for(int i=1;i<=n;i++){
		fcin(A),q[++cnt].get_asVal(i,A,1);
		s[i]=A;
		mL=min(mL,A);mR=max(mR,A);
	} char op;
	for(int i=1;i<=m;i++){
		cin>>op;
		if(op=='Q'){
			fcin(A);fcin(B);fcin(C);
			q[++cnt].get_asAsk(++ans[0],A,B,C);
		}else{
			fcin(A);fcin(B);
			mL=min(mL,B);mR=max(mR,B);
			q[++cnt].get_asVal(A,s[A],-1);s[A]=B;
			q[++cnt].get_asVal(A,s[A],1);
		}
	} solve(mL,mR,1,cnt);
	for(int i=1;i<=ans[0];i++) printf("%d\n",ans[i]);
	return 0;
}

洛谷SP10264 METEORS - 流星

Description

Byteotian Interstellar Union有N个成员国。现在它发现了一颗新的星球,这颗星球的轨道被分为M份(第M份和第1份相邻),第i份上有第Ai个国家的太空站。 这个星球经常会下陨石雨。BIU已经预测了接下来K场陨石雨的情况。 BIU的第i个成员国希望能够收集Pi单位的陨石样本。你的任务是判断对于每个国家,它需要在第几次陨石雨之后,才能收集足够的陨石。

Input

第一行是两个数N,M。 第二行有M个数,第i个数Oi表示第i段轨道上有第Oi个国家的太空站。 第三行有N个数,第i个数Pi表示第i个国家希望收集的陨石数量。 第四行有一个数K,表示BIU预测了接下来的K场陨石雨。 接下来K行,每行有三个数Li,Ri,Ai,表示第K场陨石雨的发生地点在从Li顺时针到Ri的区间中(如果Li<=Ri,就是Li,Li+1,…,Ri,否则就是Ri,Ri+1,…,m-1,m,1,…,Li),向区间中的每个太空站提供Ai单位的陨石样本。

Output

N行。第i行的数Wi表示第i个国家在第Wi波陨石雨之后能够收集到足够的陨石样本。如果到第K波结束后仍然收集不到,输出NIE。

Sample Input

3 5
1 3 2 1 3
10 5 7
3
4 2 4
1 3 1
3 5 2

Sample Output

3
NIE
1

Hint

25%的数据中,$n,m,k \leq 1000$;

100%的数据中,$n,m,k \leq 3\times 10^5,1\leq O_i \leq n,1\leq P_i ,A_i \leq 10^9$;

分析

整体二分,当然就是二分第 $mid$ 场流星雨之后能不能满足每个国家采集样本的需求,根据能否满足将当前 $[x,\;y]$ 区间中的国家划分至 $newL$ 和 $newR$

统计第 $mid$ 场流星雨之后,$m$ 个空间站的情况,同样可采用树状数组,根据树状数组前缀和的性质进行区间更新

具体的说,给 $[L,\; R]$($L \leq R$) 的空间站增加 $k$ 个陨石样本,就是先 $updata(L,k)$ ,这样 $L$ 及其以后的空间站就会多出 $k$ 来,但是 $R$ 以后的空间站没有增加陨石,需要减去,也就是 $updata(R+1,-k)$,这里的 $k$ 并不一定为正,比如当前进行到 $x(x>mid)$ 场流星雨,我们需要将时间回退到第 $mid$ 场流星雨,此处的 $k$ 就应为负值

对于 $L>R$ 的情况,视作 $[1,\;R]$ 和 $[R,\;L]$ 的同时更新即可,剩下的部分就和上述的整体二分代码非常类似了

为了判断题目中 NIE 的情况,我们可以人为增加第 $k+1$ 场流星雨,使其给所有空间站带来极大数量的样本(简而言之就是一定可以满足所有空间站的需求),原本不能在 $k$ 场流星雨结束之后收集完的国家就会在 $k+1$ 结束之后收集完,根据这个判断是否 NIE 即可

Codes

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define lowbit(x) (x&-x)
#define mid ((L+R)>>1)
#define ve(X) vector<X>::iterator
#define maxn 300005
using namespace std;
typedef long long ll;
template<typename t>inline void fcin(t &x){
	int sign=1; x=0; char op=getchar();
	while(op<'0'||op>'9'){if(op=='-') sign=-1;op=getchar();}
	while(op>='0'&&op<='9'){x=x*10+(op-48);op=getchar();}
	x*=sign;
}
struct node{
	int l,r,t;
	inline void get(int a,int b,int c){l=a,r=b,t=c;}
}q[maxn]; ll T[maxn];int n,m,k;
int tar[maxn];vector<int> a[maxn];
int id[maxn],ans[maxn],cur,s[maxn];
bool filled[maxn];
inline void updata(int p,int d){
	for(int i=p;i<=m;i+=lowbit(i))	
		T[i]+=d;
}
ll res(int p){
	ll ret=0;
	for(int i=p;i;i-=lowbit(i))
		ret+=T[i];
	return ret;
}
inline void change(int pos,int alpha){
	#define delta q[pos].t
	if(q[pos].l<=q[pos].r)
		updata(q[pos].l,delta*alpha),updata(q[pos].r+1,delta*alpha*-1);
	else
		updata(1,delta*alpha),updata(q[pos].r+1,delta*alpha*-1),
		updata(q[pos].l,delta*alpha);
	#undef delta
}
void solve(int L,int R,int x,int y){
	if(x>y) return;
	if(L==R){
		for(int i=x;i<=y;i++) ans[id[i]]=L;
		return;
	} while(cur<=mid) change(++cur,1);
	while(cur>mid) change(cur--,-1);
	int cnt=0; ll sum=0;
	for(int i=x;i<=y;i++){
		sum=0;
		for(ve(int) iter=a[id[i]].begin();iter!=a[id[i]].end();iter++){
			sum+=res(*iter); if(sum>=tar[id[i]]) break; 
		} 
		if(sum>=tar[id[i]]) filled[id[i]]=true,cnt++;
		else filled[id[i]]=false;
	} int p1=x,p2=x+cnt;
	for(int i=x;i<=y;i++)
		if(filled[id[i]]) s[p1++]=id[i];
		else s[p2++]=id[i];
	for(int i=x;i<=y;i++) id[i]=s[i];
	solve(L,mid,x,p1-1);solve(mid+1,R,p1,p2-1);
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("testin.txt","r",stdin);
	freopen("testout.txt","w",stdout);
	#endif
	fcin(n);fcin(m);int x,y,z;
	for(int i=1;i<=m;i++) fcin(x),a[x].push_back(i);
	for(int i=1;i<=n;i++) fcin(tar[i]); fcin(k);
	for(int i=1;i<=k;i++){
		fcin(x);fcin(y);fcin(z);
		q[i].get(x,y,z);
	} q[++k].get(1,n,(int)1e9+1);
	for(int i=1;i<=n;i++) id[i]=i;
	solve(1,k,1,n);
	for(int i=1;i<=n;i++){
		if(ans[i]==k) printf("NIE\n");
		else printf("%d\n",ans[i]);
	}
	return 0;
}