整体二分

在信息学竞赛中，有一部分题可以使用二分的办法来解决。但是当这种题目有多次询问且每次询问我们对每个查询都直接二分，可能会收获一个 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

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

Sample Output

1
2
3
4
5
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#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

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

Sample Output

1
2
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#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

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

Sample Output

1
2
3
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#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;
}