封面是阿罗桑！

越来越怀疑本博客的实际意义并非记录学习笔记（x

算法概述

笔者最近迷上了分治算法。分而治之作为一个经典的算法思想，在各个领域遍地开花。今天的主角整体二分便是一个分治思想非常巧妙的应用实例。

整体二分的名字其实并不直观，笔者认为从其英文（Parallel Binary Search，并行二分）更能直观体会其思想。它通过在同一个状态一次统一处理一批询问，将询问分成满足条件和不满足条件的两组，同时把答案值域也分成两半，递归进行处理，直到答案值域变成一个点为止。一批询问共享同一个修改后的数据状态，避免了重复劳动，这个过程就可以降低时间复杂度。分析其时间复杂度，满足$T(n)=2T(n/2)+f(n)$，对于很多问题$f(n)=O(n)$或$f(n)=O(n\log{n})$，那么根据主定理和平滑准则，一般只会多一个log，以这点代价统一处理了所有的询问，十分高效。

还是老样子，整体二分的算法思想非常朴素，几句就讲完了。具体细节还是用例题来细细体会吧。

例题

P3834 【模板】可持久化线段树 2

一提起整体二分的模板题，最先想到的就是区间第k小问题。这个问题的常规做法想必读者都十分熟悉，静态版本简单的建主席树，询问的时候差分获得这个区间的权值线段树，再在线段树上二分。带修版本则需要树套树，常见做法是树状数组套权值线段树，具体细节非常多，且常数巨大。现代竞赛题目已经很少强制在线了，整体二分这种离线做法相比树套树，码量小且常数优秀，成为了很多选手的香饽饽。当然，对于静态版本询问第k大，整体二分的方法其实有种杀鸡焉用牛刀的感觉，平白无故多了一只log，不过不妨碍作为例题。

对于静态问题，整体二分一般有两种常见写法，其思想一致，只是细节略有不同，一般分析信息的性质，来决定用哪种写法。

第一种，适用于询问的信息满足可贡献性的情况。具体这道题而言，我们对于每个答案值域区间，统一处理一批询问。我们使用权值树状数组，对于答案值域$[vl,vr]$，我们取其中点$mid=(vl+vr)/2$，查询区间$[vl,mid]$的和，记为$x$，如果$x>=k$，说明该询问的答案区间在$[vl,mid]$中，将其分入左组；如果$x<k$，说明目前条件不满足前k大，做$k-=x$，再将询问放入右组。我们每次查询的区间越来越小，直至区间收缩至一个点。注意到，这个区间第k大/小，就可以按照若干值域区间将贡献拆开，所以信息满足可贡献性。

第二种，询问的信息不满足可贡献性，因此我们对于一个状态只能查询对应的前缀信息，即对于区间$[vl,vr]$，取其中点$mid=(vl+vr)/2$，我们每次查询的区间都是$[1,mid]$。那么相对应地，询问的指标，这里是第k大/小，也不需要改动，只需要按照是否满足将其放入左右组即可。

两种写法没有本质区别，不过分析下来第二种写法要通用一点，按喜好选择吧。

有点trivial所以没代码。相信读者都可理解。

P2617 Dynamic Rankings

带修查询区间第k小。对于带修问题，整体二分的写法是，将修改和询问全部看成操作，按照时间顺序依次处理，这样即使分成左右组还是满足时间的先后性，因此答案的正确性可以得到保证，可以确定对于询问操作，查询的对应状态就是正确修改后的状态。那么最开始的值初始化也可以抽象成修改操作统一处理。

这种写法可以无痛迁移到静态问题上，笔者认为某种意义上可以称作整体二分的第三种写法。不过本质上还是第一二种写法的拓展。

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

struct query {
    int l, r, k, op, id;
} q[N * 3], q1[N * 3], q2[N * 3];

int n, m;
int ans[N], a[N], c[N];

void add(int x, int v) {
    while (x <= n) {
        c[x] += v;
        x += x & -x;
    }
}

int query(int x) {
    int res = 0;
    while (x) {
        res += c[x];
        x -= x & -x;
    }
    return res;
}

void solve(int l, int r, int L, int R) {
    if (L > R) return;
    if (l == r) {
        for (int i = L; i <= R; ++i) if (q[i].op == 2) ans[q[i].id] = l;
        return;
    }
    int mid = l + r >> 1, cnt1 = 0, cnt2 = 0;
    for (int i = L; i <= R; ++i) {
        if (q[i].op == 1) {
            if (q[i].l <= mid) q1[++cnt1] = q[i], add(q[i].id, q[i].r);
            else q2[++cnt2] = q[i];
        } else {
            int x = query(q[i].r) - query(q[i].l - 1);
            if (q[i].k <= x) q1[++cnt1] = q[i];
            else q[i].k -= x, q2[++cnt2] = q[i];
        }
    }
    for (int i = 1; i <= cnt1; ++i) if (q1[i].op == 1) add(q1[i].id, -q1[i].r);
    for (int i = 1; i <= cnt1; ++i) q[L + i - 1] = q1[i];
    for (int i = 1; i <= cnt2; ++i) q[L + cnt1 + i - 1] = q2[i];
    solve(l, mid, L, L + cnt1 - 1);
    solve(mid + 1, r, L + cnt1, R);
}

void solve() {
    cin >> n >> m;
    int tot = 0, cnt = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        q[++tot] = {a[i], 1, 114514, 1, i};
    }
    for (int i = 1; i <= m; ++i) {
        char c;
        int l, r, k;
        cin >> c;
        if (c == 'Q') {
            cin >> l >> r >> k;
            q[++tot] = {l, r, k, 2, ++cnt};
        } else {
            cin >> l >> r;
            q[++tot] = {a[l], -1, 1919810, 1, l};
            q[++tot] = {a[l] = r, 1, 114514, 1, l};
        }
    }
    solve(-inf, inf, 1, tot);
    for (int i = 1; i <= cnt; ++i) cout << ans[i] << "\n";
}

signed main() {
    
    FIO;
    solve();

    return 0;
}

P1527 [国家集训队] 矩阵乘法

二维矩形范围静态询问第k小。

换汤不换药，把一维变成了二维，对应的把一维的树状数组变成二维树状数组即可。

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 510;
constexpr int Q = 6e4 + 10;
constexpr int MOD = 998244353;

struct query {
    int a, b, c, d, k, id;
} q[Q], q1[Q], q2[Q];
int tree[N][N];
int ans[Q];
array<int, 3> a[N * N];
int n, m;

void add(int x, int y, int v) {
    for (int i = x; i <= n; i += i & -i) {
        for (int j = y; j <= n; j += j & -j) {
            tree[i][j] += v;
        }
    }
}

int query(int x, int y) {
    int res = 0;
    for (int i = x; i; i -= i & -i) {
        for (int j = y; j; j -= j & -j) {
            res += tree[i][j];
        }
    }
    return res;
}

int query(int a, int b, int c, int d) {
    return query(c, d) - query(a - 1, d) - query(c, b - 1) + query(a - 1, b - 1);
}

void solve(int ql, int qr, int vl, int vr) {
    if (ql > qr) {
        return;
    }
    if (vl == vr) {
        for (int i = ql; i <= qr; ++i) {
            ans[q[i].id] = a[vl][2];
        }
        return;
    }
    int mid = vl + vr >> 1;
    int cnt1 = 0, cnt2 = 0;
    for (int i = vl; i <= mid; ++i) {
        auto [x, y, _] = a[i];
        add(x, y, 1);
    }
    for (int i = ql; i <= qr; ++i) {
        auto& [a, b, c, d, k, id] = q[i];
        int x = query(a, b, c, d);
        if (k <= x) q1[++cnt1] = q[i];
        else {
            k -= x;
            q2[++cnt2] = q[i];
        }
    }
    for (int i = 1; i <= cnt1; ++i) {
        q[ql + i - 1] = q1[i];
    }
    for (int i = 1; i <= cnt2; ++i) {
        q[ql + cnt1 + i - 1] = q2[i];
    }
    for (int i = vl; i <= mid; ++i) {
        auto [x, y, _] = a[i];
        add(x, y, -1);
    }
    solve(ql, ql + cnt1 - 1, vl, mid);
    solve(ql + cnt1, qr, mid + 1, vr);
}

void solve() {
    // cin >> n >> m;
    read(n, m);
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int x;
            // cin >> x;
            read(x);
            a[++cnt] = {i, j, x};
        }
    }
    sort(a + 1, a + n * n + 1, [&](auto x, auto y) {
        return x[2] < y[2];
    });
    for (int i = 1; i <= m; ++i) {
        // cin >> q[i].a >> q[i].b >> q[i].c >> q[i].d >> q[i].k;
        // q[i].id = i;
        auto& [a, b, c, d, k, id] = q[i];
        read(a, b, c, d, k);
        id = i;
    }
    solve(1, m, 1, n * n);
    for (int i = 1; i <= m; ++i) {
        cout << ans[i] << "\n";
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P3527 [POI 2011] MET-Meteors

不板，但是是整体二分的经典练习题。

n个国家，m个行星组成环，一个行星属于一个国家。有k场流星雨，一场雨会在行星环上的某个区间给每个行星加a颗陨石，每个国家有一个陨石需求量，对每个国家询问最少需要几场雨才能满足需求量。

显然把每个国家当成询问，下雨量当成答案进行整体二分。两种写法均可，这里使用第一种拆贡献。

一个小细节是极端数据会爆long long，所以需要加一句剪枝。（其实改成u64也行）

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 3e5 + 10;
constexpr int MOD = 998244353;

int t[N];
vector<int> e[N];
int ans[N];
int n, m;
struct rain {
    int l, r, a;
} w[N];
struct {
    int p, id;
} q[N], q1[N], q2[N];

void add(int x, int v) {
    while (x <= m) {
        t[x] += v;
        x += x & -x;
    }
}

void add(int l, int r, int v) {
    add(l, v);
    if (r < m) add(r + 1, -v);
}

void process(int l, int r, int v) {
    if (l <= r) {
        add(l, r, v);
    } else {
        add(l, m, v);
        add(1, r, v);
    }
}

int query(int x) {
    int res = 0;
    while (x) {
        res += t[x];
        x -= x & -x;
    }
    return res;
}

void solve(int ql, int qr, int vl, int vr) {
    if (ql > qr) {
        return;
    }
    if (vl == vr) {
        for (int i = ql; i <= qr; ++i) {
            ans[q[i].id] = vl;
        }
        return;
    }
    int mid = vl + vr >> 1;
    int cnt1 = 0, cnt2 = 0;
    for (int i = vl; i <= mid; ++i) {
        auto [l, r, a] = w[i];
        process(l, r, a);
    }
    for (int i = ql; i <= qr; ++i) {
        auto& [p, id] = q[i];
        int x = 0;
        for (auto u : e[q[i].id]) {
            x += query(u);
            // 剪枝
            if (x >= p) break;
        }
        if (x >= p) q1[++cnt1] = q[i];
        else {
            p -= x;
            q2[++cnt2] = q[i];
        }
    }
    for (int i = vl; i <= mid; ++i) {
        auto [l, r, a] = w[i];
        process(l, r, -a);
    }
    for (int i = 1; i <= cnt1; ++i) {
        q[ql + i - 1] = q1[i];
    }
    for (int i = 1; i <= cnt2; ++i) {
        q[ql + cnt1 + i - 1] = q2[i];
    }
    solve(ql, ql + cnt1 - 1, vl, mid);
    solve(ql + cnt1, qr, mid + 1, vr);
}

void solve() {
    cin >> n >> m;
    for (int i = 1, x; i <= m; ++i) {
        cin >> x;
        e[x].push_back(i);
    }
    for (int i = 1; i <= n; ++i) {
        auto& [p, id] = q[i];
        cin >> p;
        id = i;
    }
    int k;
    cin >> k;
    for (int i = 1; i <= k; ++i) {
        auto& [l, r, a] = w[i];
        cin >> l >> r >> a;
    }
    solve(1, n, 1, k + 1);
    for (int i = 1; i <= n; ++i) {
        if (ans[i] == k + 1) cout << "NIE\n";
        else cout << ans[i] << "\n";
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P4602 [CTSC2018] 混合果汁

不用树状数组改用线段树，别的区别不大。线段树维护每个单价区间的最大可提供饮料总量和对应花费，方便快速查询获得L升果汁的最少花费，具体查询在这个单价线段树上二分即可。那么我们把所有饮料按照美味度降序排序，对于一个答案值域$[vl,vr]$，取其中点$mid=(vl+vr)/2$，可以用的饮料下标属于区间$[1,mid]$，获得的美味度就是$mid$号饮料对应的美味度。很明显这满足我们的第二种写法，拿捏。

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 1e5 + 10;
constexpr int MOD = 998244353;

#define lc u<<1
#define rc u<<1|1
int sum[N << 2], cost[N << 2];
array<int, 3> a[N];
struct query {
    int g, L, id;
} q[N], q1[N], q2[N];
int ans[N];
int used;
int n, m;
int maxp;

void push_up(int u) {
    sum[u] = sum[lc] + sum[rc];
    cost[u] = cost[lc] + cost[rc];
}

void modify(int u, int l, int r, int p, int s) {
    if (l == r) {
        sum[u] += s;
        cost[u] += l * s;
        return;
    }
    int mid = l + r >> 1;
    if (p <= mid) modify(lc, l, mid, p, s);
    else modify(rc, mid + 1, r, p, s);
    push_up(u);
}

int query(int u, int l, int r, int v) {
    if (l == r) {
        return v * l;
    }
    int mid = l + r >> 1;
    if (sum[lc] >= v) return query(lc, l, mid, v);
    return cost[lc] + query(rc, mid + 1, r, v - sum[lc]);
}

void solve(int ql, int qr, int vl, int vr) {
    if (ql > qr) {
        return;
    }
    if (vl == vr) {
        for (int i = ql; i <= qr; ++i) {
            ans[q[i].id] = a[vl][0];
        }
        return;
    }
    int mid = vl + vr >> 1;
    int cnt1 = 0, cnt2 = 0;
    while (used < mid) {
        used++;
        modify(1, 1, maxp, a[used][1], a[used][2]);
    }
    while (used > mid) {
        modify(1, 1, maxp, a[used][1], -a[used][2]);
        used--;
    }
    for (int i = ql; i <= qr; ++i) {
        if (q[i].L > sum[1]) {
            q2[++cnt2] = q[i];
            continue;
        }
        int x = query(1, 1, maxp, q[i].L);
        if (x <= q[i].g) q1[++cnt1] = q[i];
        else q2[++cnt2] = q[i];
    }
    for (int i = 1; i <= cnt1; ++i) {
        q[ql + i - 1] = q1[i];
    }
    for (int i = 1; i <= cnt2; ++i) {
        q[ql + cnt1 + i - 1] = q2[i];
    }
    solve(ql, ql + cnt1 - 1, vl, mid);
    solve(ql + cnt1, qr, mid + 1, vr);
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        auto& [d, p, l] = a[i];
        cin >> d >> p >> l;
        maxp = max(maxp, p);
    }
    sort(a + 1, a + 1 + n, [&](auto x, auto y) {
        return x[0] > y[0];
    });
    a[n + 1][0] = 114514;
    for (int i = 1; i <= m; ++i) {
        auto& [g, L, id] = q[i];
        cin >> g >> L;
        id = i;
    }
    solve(1, m, 1, n + 1);
    for (int i = 1; i <= m; ++i) {
        if (ans[i] == 114514) ans[i] = -1;
        cout << ans[i] << "\n";
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

结语

整体二分作为一种比较小清新的离线算法，在一些银牌区以上题目偶有遇到。很多情况下整体二分不是唯一解，但这种解法能够扩展选手的思路，十分值得学习。

说实话感觉离线算法都很妙啊，离线就代表着摆脱了原问题的桎梏，在一个更高，或者更广阔的视野看待问题，往往会有不一样的思路。

整体二分其实在今年4月就学过一遍，不过当时只贺了一遍区间第k小的板子题做法，细节并没有完全理解，这次算是弥补了之前的漏洞吧。