整体二分学习笔记
Tarantula
2021-08-23 14:40:04
[或许更好的阅读体验](https://www.cnblogs.com/ConanKID/p/15732611.html)
---
整体二分，数据结构题的一种非数据结构解法。
---
[来看题](https://www.luogu.com.cn/problem/P3834)
一道很经典的题目——区间静态第 $k$ 小，其解法也多种多样。
对于每个询问 $(l,r,k)$，考虑二分答案。设当前二分的值为 $mid$，我们求出区间 $[l,r]$ 内小于等于 $mid$ 的数的个数 $x$。如果 $x\ge k$，就证明答案小于等于 $mid$；否则，答案大于 $mid$。但这样做的总时间复杂度是 $O(nm\log SIZE)$，无法承受。（$SIZE$ 表示值域）
注意到对于每个询问，我们二分的 $mid$ 都是相同的，那么可不可以把所有询问放在一起二分呢？
具体来说，我们执行以下流程：
1. 把所有询问离线下来；
1. 二分答案 $mid$，把序列 $a$ 中所有小于等于 $mid$ 的数设为 $1$；
2. 利用树状数组，统计第 $i$ 个询问区间中小于等于 $mid$ 的数的数量，从而确定这个询问的答案与 $mid$ 的大小关系；
3. 递归求解所有答案小于等于 $mid$ 的询问；
4. 递归求解所有答案大于 $mid$ 的询问。（这样一来，原问题就被划分成了两个规模更小的子问题，可以继续递归）
为了方便，我们可以把序列中的第 $i$ 个数看成修改操作。如果修改的数，即 $a_i\le mid$，就把这个操作划到答案小于等于 $mid$ 的询问的集合里；否则，划到答案大于 $mid$ 的询问的集合里。
需要注意，树状数组清零不能用`memset`，要把所有修改操作逐一撤销掉，否则复杂度会爆炸。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n, m;
int a[200005];
struct node {int p, x, y, k, id;} q[400005], lq[400005], rq[400005];
int ans[200005];
int sum[200005];
inline int read() {
int x = 0, f = 1; char c = getchar();
while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
return f == 1 ? x : -x;
}
inline void update(int x, int val) {
for (; x <= n; x += x & -x)
sum[x] += val;
}
inline int query(int x) {
int res = 0;
for (; x; x -= x & -x)
res += sum[x];
return res;
}
inline void solve(int l, int r, int st, int ed) {//l,r表示答案的值域区间，st,ed表示询问的区间
if (st > ed) return;
if (l == r) {
for (int i = st; i <= ed; ++i)
if (q[i].p == 2) ans[q[i].id] = l;
return;
}
int mid = l + r >> 1, cnt1 = 0, cnt2 = 0;
//lq存储所有答案<=mid的询问，rq存储答案>mid的询问
for (int i = st; i <= ed; ++i) {
if (q[i].p == 1) {//修改操作
if (q[i].y <= mid) update(q[i].x, 1), lq[++cnt1] = q[i];
else rq[++cnt2] = q[i];
} else {//询问操作
int x = query(q[i].y) - query(q[i].x - 1);
if (x >= q[i].k) lq[++cnt1] = q[i];
else q[i].k -= x, rq[++cnt2] = q[i];
//如果一个询问的答案大于mid，那么划分后实际上是在找第k-x小数
}
}
for (int i = st; i <= ed; ++i)
if (q[i].p == 1 && q[i].y <= mid) update(q[i].x, -1);//撤销所有修改
for (int i = 1; i <= cnt1; ++i) q[i + st - 1] = lq[i];
for (int i = 1; i <= cnt2; ++i) q[i + st + cnt1 - 1] = rq[i];//把两组询问copy回原数组，防止空间爆炸
solve(l, mid, st, st + cnt1 - 1); solve(mid + 1, r, st + cnt1, ed);//递归求解
}
int main() {
n = read(); m = read();
for (int i = 1; i <= n; i++)
q[i] = (node){1, i, read(), 0, 0};
for (int i = 1; i <= m; i++)
q[i + n] = (node){2, read(), read(), read(), i};//把询问离线下来操作
solve(-1e9, 1e9, 1, n + m);
for (int i = 1; i <= m; i++)
printf("%d\n", ans[i]);
return 0;
}
```
来分析一波时间复杂度。每个询问会被递归 $\log SIZE$ 层，而一个操作每次递归都会在树状数组中被 $\log n$ 地更新一次，算上修改我们一共有 $n+m$ 个操作，因此总时间复杂度为 $O((n+m)\log n\log SIZE)$。
顺带提一嘴 $O(n\log n)$ 的神仙做法：把所有修改操作按 $a_i$ 排个序；把所有询问 $[l,r]$ 拆成 $[1,l-1]$ 和 $[1,r]$，再把拆出来的区间按照右端点排个序。于是我们求 $[l,r]$ 内有多少个数小于等于 $mid$ 时，就只需要一个指针扫过去就可以了。这样就做到了单个 $\log$。代码就不给了，更加详细的分析可以看[这篇 blog](https://www.luogu.com.cn/blog/203623/zheng-ti-er-fen-xie-jue-jing-tai-ou-jian-di-k-xiao-di-you-hua)。
---
[接下来是这个](https://www.luogu.com.cn/problem/P2617)
与上一题相比，只是从静态变为了动态。但是如果直接按照题意修改的话，我们将需要面临这个数原本是否大于 $mid$、修改后是否大于 $mid$ 等多种情况分类讨论，增加了码长还容易写挂。因此，我们需要把一次修改看成两次操作，即在位置 $x$ 上去掉了一个值为 $a_x$ 的数，又增加了一个值为 $y$ 的数。于是这样我们就不需要分情况讨论了。
P.S.：读入修改操作时，必须把 $a_x$ 赋值为 $y$，正确维护 $a$ 序列，否则只有 $5$ 分——这是血的教训！
```cpp
#include<bits/stdc++.h>
using namespace std;
int n, m;
int t, cnt;
int a[200005];
struct node {int p, x, y, k, id;} q[400005], lq[400005], rq[400005];
int ans[200005];
int sum[200005];
inline int read() {
int x = 0, f = 1; char c = getchar();
while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while (isdigit(c)) {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
return f == 1 ? x : -x;
}
inline void update(int x, int val) {
for (; x <= n; x += x & -x)
sum[x] += val;
}
inline int query(int x) {
int res = 0;
for (; x; x -= x & -x)
res += sum[x];
return res;
}
inline void solve(int l, int r, int st, int ed) {
if (st > ed) return;
if (l == r) {
for (int i = st; i <= ed; ++i)
if (q[i].p == 1) ans[q[i].id] = l;
return;
}
int mid = l + r >> 1, cnt1 = 0, cnt2 = 0;
for (int i = st; i <= ed; ++i) {
if (q[i].p == 0) {
if (q[i].y <= mid) update(q[i].x, q[i].k), lq[++cnt1] = q[i];
else rq[++cnt2] = q[i];
} else {
int x = query(q[i].y) - query(q[i].x - 1);
if (x >= q[i].k) lq[++cnt1] = q[i];
else q[i].k -= x, rq[++cnt2] = q[i];
}
}
for (int i = st; i <= ed; ++i)
if (q[i].p == 0 && q[i].y <= mid) update(q[i].x, -q[i].k);
for (int i = 1; i <= cnt1; ++i) q[i + st - 1] = lq[i];
for (int i = 1; i <= cnt2; ++i) q[i + st + cnt1 - 1] = rq[i];
solve(l, mid, st, st + cnt1 - 1); solve(mid + 1, r, st + cnt1, ed);
}//同样的方法求解
int main() {
n = read(); m = read();
for (int i = 1; i <= n; ++i) {
a[i] = read();
q[++t] = (node){0, i, a[i], 1, 0};
}
for (int i = 1; i <= m; ++i) {
char c; int x, y, k; cin >> c;
if (c == 'Q') {
x = read(); y = read(); k = read();
q[++t] = (node){1, x, y, k, ++cnt};
} else {
x = read(); y = read();
q[++t] = (node){0, x, a[x], -1, 0};
q[++t] = (node){0, x, y, 1, 0};//把修改分成两个操作
//结构体中的k表示这是删除还是添加
a[x] = y;//很重要的一行，我老是忘
}
}//必须要把所有操作按时间顺序存进数组
solve(-1e9, 1e9, 1, t);
for (int i = 1; i <= cnt; ++i)
printf("%d\n", ans[i]);
return 0;
}
```
与树套树相比，整体二分的理论复杂度从 $O((n+m)\log^2n)$ 变成了 $O((n+m)\log n\log SIZE)$，但看看实际效果：
| 算法 | 线段树套平衡树 | 整体二分 |
| :----------: | :----------: | :----------: |
| 时间 | $23.23s$ | $2.06s$ |
| 空间 | $88.13MB$ | $21.09MB$ |
| 码长 | $2.77KB$ | $1.90KB$ |
可以发现，整体二分无论是从哪个方面都吊打了树套树。树状数组套主席树我没写过，不过从其他人的提交记录来看应该也是跑不过整体二分的。
---
几道练习：
- [P1527 [国家集训队]矩阵乘法](https://www.luogu.com.cn/problem/P1527)
- [P3332 [ZJOI2013]K大数查询](https://www.luogu.com.cn/problem/P3332)
---
接下来是整体二分的综合运用，它不止能做区间 Kth 问题。
[这道题](https://www.luogu.com.cn/problem/P3527)开始变形了
我们依旧可以进行整体二分，看在第 $[l,mid]$ 场陨石雨过后，第 $i$ 个国家是否收集到了足够的陨石，从而确定答案与 $mid$ 的大小关系。
此题还需要判断无解。我们不需要多花精力去特判，可以人为地加上第 $k+1$ 场陨石雨。这样一来，无解的询问在二分时就会一直向右递归，答案就会变成 $k+1$，就很好判断了。
```cpp
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int n, m, k;
vector<int> o[300005];
struct option {int l, r, k;} a[300005];
struct node {int p, k;} q[300005], lq[300005], rq[300005];
int sum[300005], ans[300005];
int lowbit(int x) {return x & -x;}
void update(int x, int val) {
for (; x <= m; x += lowbit(x))
sum[x] += val;
}
int query(int x) {
int res = 0;
for (; x; x -= lowbit(x)) res += sum[x];
return res;
}
void solve(int l, int r, int st, int ed) {
if (st > ed) return;
if (l == r) {
for (int i = st; i <= ed; i++)
ans[q[i].p] = l;
return;
}
int mid = l + r >> 1, cnt1 = 0, cnt2 = 0;
for (int i = l; i <= mid; i++)
if (a[i].l <= a[i].r) update(a[i].l, a[i].k), update(a[i].r + 1, -a[i].k);
else update(a[i].l, a[i].k), update(1, a[i].k), update(a[i].r + 1, -a[i].k);
for (int i = st; i <= ed; i++) {
int s = 0;
for (int j = 0; j < o[q[i].p].size(); j++)
s += query(o[q[i].p][j]);
if (q[i].k <= s) lq[++cnt1] = q[i];
else q[i].k -= s, rq[++cnt2] = q[i];
}
for (int i = l; i <= mid; i++)
if (a[i].l <= a[i].r) update(a[i].l, -a[i].k), update(a[i].r + 1, a[i].k);
else update(a[i].l, -a[i].k), update(1, -a[i].k), update(a[i].r + 1, a[i].k);
for (int i = 1; i <= cnt1; i++) q[st + i - 1] = lq[i];
for (int i = 1; i <= cnt2; i++) q[st + cnt1 + i - 1] = rq[i];
solve(l, mid, st, st + cnt1 - 1); solve(mid + 1, r, st + cnt1, ed);
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x; cin >> x;
o[x].push_back(i);
}
for (int i = 1; i <= n; i++)
cin >> q[i].k, q[i].p = i;
cin >> k;
for (int i = 1; i <= k; i++)
cin >> a[i].l >> a[i].r >> a[i].k;
a[k + 1] = (option){1, m, 0};//为了判断无解，加上第k+1次陨石雨
solve(1, k + 1, 1, n);
for (int i = 1; i <= n; i++)
if (ans[i] == k + 1) cout << "NIE" << endl;
else cout << ans[i] << endl;
return 0;
}
```
---
几道习题：
- [P7424 [THUPC2017] 天天爱射击](https://www.luogu.com.cn/problem/P7424)
- [P4602 [CTSC2018]混合果汁](https://www.luogu.com.cn/problem/P4602)
- [P3242 [HNOI2015] 接水果](https://www.luogu.com.cn/problem/P3242)
---
最后套用一下许昊然大佬的论文吧。
> 可以使用整体二分解决的题目需要满足以下性质：
> 1. 询问的答案具有可二分性
> 2. 修改对判定答案的贡献互相独立，修改之间互不影响效果
> 3. 修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值
> 4. 贡献满足交换律，结合律，具有可加性
> 5. 题目允许使用离线算法
---
~~没有了~~