跳转至

整體二分

引入

在信息學競賽中，有一部分題目可以使用二分的辦法來解決。但是當這種題目有多次詢問且我們每次查詢都直接二分可能導致 TLE 時，就會用到整體二分。整體二分的主體思路就是把多個查詢一起解決。（所以這是一個離線算法）

可以使用整體二分解決的題目需要滿足以下性質：

  1. 詢問的答案具有可二分性

  2. 修改對判定答案的貢獻互相獨立，修改之間互不影響效果

  3. 修改如果對判定答案有貢獻，則貢獻為一確定的與判定標準無關的值

  4. 貢獻滿足交換律，結合律，具有可加性

  5. 題目允許使用離線算法

    ——許昊然《淺談數據結構題幾個非經典解法》

解釋

記 \([l,r]\) 為答案的值域，\([L,R]\) 為答案的定義域。（也就是説求答案時僅考慮下標在區間 \([L,R]\) 內的操作和詢問，這其中詢問的答案在 \([l,r]\) 內）

  • 我們首先把所有操作 按時間順序 存入數組中，然後開始分治。
  • 在每一層分治中，利用數據結構（常見的是樹狀數組）統計當前查詢的答案和 \(mid\) 之間的關係。
  • 根據查詢出來的答案和 \(mid\) 間的關係（小於等於 \(mid\) 和大於 \(mid\)）將當前處理的操作序列分為 \(q1\) 和 \(q2\) 兩份，並分別遞歸處理。
  • 當 \(l=r\) 時，找到答案，記錄答案並返回即可。

需要注意的是，在整體二分過程中，若當前處理的值域為 \([l,r]\)，則此時最終答案範圍不在 \([l,r]\) 的詢問會在其他時候處理。

過程

注：

  1. 為可讀性，文中代碼或未採用實際競賽中的常見寫法。
  2. 若覺得某段代碼有難以理解之處，請先參考之前題目的解釋， 因為節省篇幅解釋過的內容不再贅述。

從普通二分説起：

查詢全局第 k 小

題 1 在一個數列中查詢第 \(k\) 小的數。

當然可以直接排序。如果用二分法呢？可以用數據結構記錄每個大小範圍內有多少個數，然後用二分法猜測，利用數據結構檢驗。

題 2 在一個數列中多次查詢第 \(k\) 小的數。

可以對於每個詢問進行一次二分；但是，也可以把所有的詢問放在一起二分。

先考慮二分的本質：假設要猜一個 \([l,r]\) 之間的數，猜測之後會知道是猜大了，猜小了還是剛好。當然可以從 \(l\) 枚舉到 \(r\)，但更優秀的方法是二分：猜測答案是 \(m = \lfloor\frac{l + r}{2}\rfloor\)，然後去驗證 \(m\) 的正確性，再調整邊界。這樣做每次詢問的複雜度為 \(O(\log n)\)，若詢問次數為 \(q\)，則時間複雜度為 \(O(q\log n)\)。

回過頭來，對於當前的所有詢問，可以去猜測所有詢問的答案都是 \(mid\)，然後去依次驗證每個詢問的答案應該是小於等於 \(mid\) 的還是大於 \(mid\) 的，並將詢問分為兩個部分（不大於/大於），對於每個部分繼續二分。注意：如果一個詢問的答案是大於 \(mid\) 的，則在將其劃至右側前需更新它的 \(k\)，即，如果當前數列中小於等於 \(mid\) 的數有 \(t\) 個，則將詢問劃分後實際是在右區間詢問第 \(k - t\) 小數。如果一個部分的 \(l = r\) 了，則結束這個部分的二分。利用線段樹的相關知識，我們每次將整個答案可能在的區間 \([1,maxans]\) 劃分成了若干個部分，這樣的劃分共進行了 \(O(\log maxans)\) 次，一次劃分會將整個操作序列操作一次。若對整個序列進行操作，並支持對應的查詢的時間複雜度為 \(O(T)\)，則整體二分的時間複雜度為 \(O(T\log n)\)。

試試完成以下代碼：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
struct Query {
  int id, k;  // 這個詢問的編號, 這個詢問的k
};

int ans[N];        // ans[i] 表示編號為i的詢問的答案
int check(int x);  // 返回原數列中小於等於x的數的個數

void solve(int l, int r, vector<Query> q)
// 請補全這個函數
{
  int m = (l + r) / 2;
  vector<Query> q1, q2;  // 將被劃到左側的詢問和右側的詢問
  if (l == r) {
    // ...
    return;
  }
  // ...
  solve(l, m, q1), solve(m + 1, r, q2);
  return;
}

參考代碼如下

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void solve(int l, int r, vector<Query> q) {
  int m = (l + r) / 2;
  if (l == r) {
    for (unsigned i = 0; i < q.size(); i++) ans[q[i].id] = l;
    return;
  }
  vector<int> q1, q2;
  for (unsigned i = 0; i < q.size(); i++)
    if (q[i].k <= check(m))
      q1.push_back(q[i]);
    else
      q[i].k -= check(m), q2.push_back(q[i]);
  solve(l, m, q1), solve(m + 1, r, q2);
  return;
}

查詢區間第 k 小

題 3 在一個數列中多次查詢區間第 \(k\) 小的數。

涉及到給定區間的查詢，再按之前的方法進行二分就會導致 check 函數的時間複雜度爆炸。仍然考慮詢問與值域中點 \(m\) 的關係：若詢問區間內小於等於 \(m\) 的數有 \(t\) 個，詢問的是區間內的 \(k\) 小數，則當 \(k \leq t\) 時，答案應小於等於 \(m\)；否則，答案應大於 \(m\)。（注意邊界問題）此處需記錄一個區間小於等於指定數的數的數量，即單點加，求區間和，可用樹狀數組快速處理。為提高效率，只對數列中值在值域區間 \([l,r]\) 的數進行統計，即，在進一步遞歸之前，不僅將詢問劃分，將當前處理的數按值域範圍劃為兩半。

參考代碼（關鍵部分）

實現 
 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
struct Num {
  int p, x;
};  // 位於數列中第 p 項的數的值為 x

struct Query {
  int l, r, k, id;
};  // 一個編號為 id, 詢問 [l,r] 中第 k 小數的詢問

int ans[N];
void add(int p, int x);  // 樹狀數組, 在 p 位置加上 x
int query(int p);        // 樹狀數組, 求 [1,p] 的和
void clear();            // 樹狀數組, 清空

void solve(int l, int r, vector<Num> a, vector<Query> q)
// a中為給定數列中值在值域區間 [l,r] 中的數
{
  int m = (l + r) / 2;
  if (l == r) {
    for (unsigned i = 0; i < q.size(); i++) ans[q[i].id] = l;
    return;
  }
  vector<Num> a1, a2;
  vector<Query> q1, q2;
  for (unsigned i = 0; i < a.size(); i++)
    if (a[i].x <= m)
      a1.push_back(a[i]), add(a[i].p, 1);
    else
      a2.push_back(a[i]);
  for (unsigned i = 0; i < q.size(); i++) {
    int t = query(q[i].r) - query(q[i].l - 1);
    if (q[i].k <= t)
      q1.push_back(q[i]);
    else
      q[i].k -= t, q2.push_back(q[i]);
  }
  clear();
  solve(l, m, a1, q1), solve(m + 1, r, a2, q2);
  return;
}

下面提供 【模板】可持久化線段樹 2 一題使用整體二分的，偏向競賽風格的寫法。

參考代碼 
 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
#include <bits/stdc++.h>
using namespace std;
const int N = 200020;
const int INF = 1e9;
int n, m;
int ans[N];
// BIT begin
int t[N];
int a[N];

int sum(int p) {
  int ans = 0;
  while (p) {
    ans += t[p];
    p -= p & (-p);
  }
  return ans;
}

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

// BIT end
int tot = 0;

struct Query {
  int l, r, k, id, type;  // set values to -1 when they are not used!
} q[N * 2], q1[N * 2], q2[N * 2];

void solve(int l, int r, int ql, int qr) {
  if (ql > qr) return;
  if (l == r) {
    for (int i = ql; i <= qr; i++)
      if (q[i].type == 2) ans[q[i].id] = l;
    return;
  }
  int mid = (l + r) / 2, cnt1 = 0, cnt2 = 0;
  for (int i = ql; i <= qr; i++) {
    if (q[i].type == 1) {
      if (q[i].l <= mid) {
        add(q[i].id, 1);
        q1[++cnt1] = q[i];
      } else
        q2[++cnt2] = q[i];
    } else {
      int x = sum(q[i].r) - sum(q[i].l - 1);
      if (q[i].k <= x)
        q1[++cnt1] = q[i];
      else {
        q[i].k -= x;
        q2[++cnt2] = q[i];
      }
    }
  }
  // rollback changes
  for (int i = 1; i <= cnt1; i++)
    if (q1[i].type == 1) add(q1[i].id, -1);
  // move them to the main array
  for (int i = 1; i <= cnt1; i++) q[i + ql - 1] = q1[i];
  for (int i = 1; i <= cnt2; i++) q[i + cnt1 + ql - 1] = q2[i];
  solve(l, mid, ql, cnt1 + ql - 1);
  solve(mid + 1, r, cnt1 + ql, qr);
}

pair<int, int> b[N];
int toRaw[N];

int main() {
  scanf("%d%d", &n, &m);
  // read and discrete input data
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    b[i].first = x;
    b[i].second = i;
  }
  sort(b + 1, b + n + 1);
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    if (b[i].first != b[i - 1].first) cnt++;
    a[b[i].second] = cnt;
    toRaw[cnt] = b[i].first;
  }
  for (int i = 1; i <= n; i++) {
    q[++tot] = {a[i], -1, -1, i, 1};
  }
  for (int i = 1; i <= m; i++) {
    int l, r, k;
    scanf("%d%d%d", &l, &r, &k);
    q[++tot] = {l, r, k, i, 2};
  }
  solve(0, cnt + 1, 1, tot);
  for (int i = 1; i <= m; i++) printf("%d\n", toRaw[ans[i]]);
}

帶修區間第 k 小

題 4 Dynamic Rankings 給定一個數列，要支持單點修改，區間查第 \(k\) 小。

修改操作可以直接理解為從原數列中刪去一個數再添加一個數，為方便起見，將詢問和修改統稱為「操作」。因後面的操作會依附於之前的操作，不能如題 3 一樣將統計和處理詢問分開，故可將所有操作存於一個數組，用標識區分類型，依次處理每個操作。為便於處理樹狀數組，修改操作可分拆為擦除操作和插入操作。

優化

  1. 注意到每次對於操作進行分類時，只會更改操作順序，故可直接在原數組上操作。具體實現，在二分時將記錄操作的 \(q, a\) 數組換為一個大的全局數組，二分時記錄信息變為 \(L, R\)，即當前處理的操作是全局數組上的哪個區間。利用臨時數組記錄當前的分類情況，進一步遞歸前將臨時數組信息寫回原數組。
  2. 樹狀數組每次清空會導致時間複雜度爆炸，可採用每次使用樹狀數組時記錄當前修改位置（這已由 1 中提到的臨時數組實現），本次操作結束後在原位置加 \(-1\) 的方法快速清零。
  3. 一開始對於數列的初始化操作可簡化為插入操作。

參考代碼（關鍵部分）

實現 
 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
struct Opt {
  int x, y, k, type, id;
  // 對於詢問, type = 1, x, y 表示區間左右邊界, k 表示詢問第 k 小
  // 對於修改, type = 0, x 表示修改位置, y 表示修改後的值,
  // k 表示當前操作是插入(1)還是擦除(-1), 更新樹狀數組時使用.
  // id 記錄每個操作原先的編號, 因二分過程中操作順序會被打散
};

Opt q[N], q1[N], q2[N];
// q 為所有操作,
// 二分過程中, 分到左邊的操作存到 q1 中, 分到右邊的操作存到 q2 中.
int ans[N];
void add(int p, int x);
int query(int p);  // 樹狀數組函數, 含義見題3

void solve(int l, int r, int L, int R)
// 當前的值域範圍為 [l,r], 處理的操作的區間為 [L,R]
{
  if (l > r || L > R) return;
  int cnt1 = 0, cnt2 = 0, m = (l + r) / 2;
  // cnt1, cnt2 分別為分到左邊, 分到右邊的操作數
  if (l == r) {
    for (int i = L; i <= R; i++)
      if (q[i].type == 1) ans[q[i].id] = l;
    return;
  }
  for (int i = L; i <= R; i++)
    if (q[i].type == 1) {  // 是詢問: 進行分類
      int t = query(q[i].y) - query(q[i].x - 1);
      if (q[i].k <= t)
        q1[++cnt1] = q[i];
      else
        q[i].k -= t, q2[++cnt2] = q[i];
    } else
      // 是修改: 更新樹狀數組 & 分類
      if (q[i].y <= m)
        add(q[i].x, q[i].k), q1[++cnt1] = q[i];
      else
        q2[++cnt2] = q[i];
  for (int i = 1; i <= cnt1; i++)
    if (q1[i].type == 0) add(q1[i].x, -q1[i].k);  // 清空樹狀數組
  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, m, L, L + cnt1 - 1), solve(m + 1, r, L + cnt1, R);
  return;
}

針對靜態序列的優化

題 5 【模板】可持久化線段樹 2 給定一個序列，區間查詢第 \(k\) 小。

樹套樹和整體二分實現帶修區間第 \(k\) 小問題的複雜度都為 \(O(n \log^2 n)\)，但靜態區間第 \(k\) 小問題可以使用可持久化線段樹在 \(O(n \log n)\) 時間複雜度內解決，而幾乎所有整體二分實現的靜態區間第 \(k\) 小問題代碼時間複雜度都是 \(O(n \log^2 n)\)，面對大數據範圍時存在 TLE 的風險。（這裏默認值域與序列長度同階，值域與序列長不同階的情況可以通過離散化轉化為同階情況）

優化

  1. 對於每一輪劃分，如果當前數列中小於等於 \(mid\) 的數有 \(t\) 個，則將詢問劃分後實際是在右區間詢問第 \(k - t\) 小數，因此對劃分到右區間的詢問做出了修改。如果答案的原始值域為 \([L,R]\)，某次劃分的答案值域為 \([l,r]\)，那麼對於參與此次劃分的詢問，\([L,l)\) 中所有數值對它們的影響已經在之前被消除了。
  2. 由於需要使每輪劃分都僅和當前答案值域 \([l,r]\) 有關，樹狀數組需要多次載入和清空。

如果劃分不僅僅和當前答案值域有關呢？

由此可以得到一個與全局序列有關的優化方法：維護一個指針 \(pos\) 追蹤每輪劃分的 \(mid\)（分治中心），將所有 \(\leq pos\) 的元素對應的下標在樹狀數組中置為 \(1\)，樹狀數組的其餘位置置為 \(0\)。每次劃分之前移動 \(pos\) 並更新樹狀數組。指針 \(pos\) 移動的次數與 \(n \log n\) 同階。劃分時對每一個詢問查詢樹狀數組中對應區間的值，滿足則劃分至左區間，否則劃分至右區間，不需要對詢問做出修改。

由於要追蹤分治中心，需要讓 \(pos\) 準確地更新樹狀數組。在整體二分之前將序列按元素大小排序並記錄元素對應下標，指針移動時在樹狀數組中對下標進行相應修改。對於絕大多數 可以用整體二分解決並且不帶修改的問題，都可以應用此種優化以大幅降低數據結構的使用次數。

由於減少了很多樹狀數組的載入和清空操作，應用這種優化通常情況下會明顯提升整體二分的效率（即使只是常數優化），對於靜態區間第 \(k\) 小值問題而言效率完全不差於時間複雜度更優的可持久化線段樹。值得注意的是，對於靜態區間第 \(k\) 小值問題也存在時間複雜度 \(O(n \log n)\) 的整體二分實現。

參考代碼（關鍵部分）

實現 
 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
struct Query {
  int i, l, r, k;
};  // 第 i 次詢問查詢區間 [l,r] 的第 k 小值

Query s[200005], t1[200005], t2[200005];
int n, m, cnt, pos, p[200005], ans[200005];
pair<int, int> a[200005];

void add(int x, int y);  // 樹狀數組 位置 x 加 y
int sum(int x);          // 樹狀數組 [1,x] 前綴和

// 當前處理的詢問為 [l,r],答案值域為 [ql,qr]
void overall_binary(int l, int r, int ql, int qr) {
  if (l > r) return;
  if (ql == qr) {
    for (int i = l; i <= r; i++) ans[s[i].i] = ql;
    return;
  }
  int cnt1 = 0, cnt2 = 0, mid = (ql + qr) >> 1;
  // 追蹤分治中心,認為 [1,pos] 的值已經載入樹狀數組
  while (pos <= n - 1 && a[pos + 1].first <= mid)
    add(a[pos + 1].second, 1), ++pos;
  while (pos >= 1 && a[pos].first > mid) add(a[pos].second, -1), --pos;

  for (int i = l; i <= r; i++) {
    int now = sum(s[i].r) - sum(s[i].l - 1);
    if (s[i].k <= now)
      t1[++cnt1] = s[i];
    else
      t2[++cnt2] = s[i];  // 注意 不應修改詢問信息
  }
  for (int i = 1; i <= cnt1; i++) s[l + i - 1] = t1[i];
  for (int i = 1; i <= cnt2; i++) s[l + cnt1 + i - 1] = t2[i];

  overall_binary(l, l + cnt1 - 1, ql, mid);
  overall_binary(l + cnt1, r, mid + 1, qr);
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i].first);
    a[i].second = i;
    p[++cnt] = a[i].first;
  }
  sort(a + 1, a + n + 1);  // 對序列排序 離散化
  sort(p + 1, p + n + 1);
  cnt = unique(p + 1, p + n + 1) - p - 1;
  for (int i = 1; i <= n; i++)
    a[i].first = lower_bound(p + 1, p + cnt + 1, a[i].first) - p;
  // 省略讀入詢問
  overall_binary(1, m, 1, cnt);
  for (int i = 1; i <= n; i++) printf("%d\n", p[ans[i]]);
  return 0;
}

區間前驅後繼

題 6 在一個數列中多次查詢 \(k\) 在區間中的前驅（嚴格小於 \(k\)，且最大的數）或後繼（嚴格大於 \(k\)，且最小的數），保證存在這樣的數。

以前驅為例，使用數據結構解決此種問題的方法一般是先查詢區間內有多少嚴格小於 \(k\) 的數（設它們的數量為 \(x\)），再查詢區間第 \(x\) 小的數。後繼則是查詢區間內有多少不大於 \(k\) 的數（數量為 \(x\)），然後查詢區間第 \(x+1\) 小的數。

考慮使用整體二分解決這個問題：整體二分是一種高效求解區間第 \(k\) 小的離線算法，而 CDQ 分治 可以離線高效求解區間內的排名。先跑一遍 CDQ 分治求出排名就可以使用整體二分得到區間內部的前驅和後繼了。

此問題還可以用 CDQ 分治套線段樹離線一遍解決，但效率遠低於跑兩遍的 CDQ 分治 + 整體二分。

構造單調性序列

題 7 Sequence 給定一個序列，每次操作可以把某個數 \(+1\) 或 \(−1\)。要求把序列變成單調不降的，並且修改後的數列只能出現修改前的數，輸出最小操作次數。

此類題目也可以使用動態規劃或反悔貪心解決。

在滿足操作次數最小化的前提下，一定存在一種方案使得最後序列中的每個數都是序列修改前存在的，這個結論可以使用數學歸納法證明。由於題目並不需要最終序列的信息，問題轉化為求出最小操作次數。

由於要求最終的序列單調不降，可以使用整體二分。每輪整體二分判定最終序列區間 \([l,r]\) 的值域，此時答案的值域為 \([ql,qr]\)。令 \(mid=\lfloor\frac{ql + qr}{2}\rfloor\)，每輪二分開始時默認將所有數劃分至 \([mid+1,qr]\)（要劃分到 \([ql,mid]\) 的數設為 \(0\) 個），初始代價設為將序列區間 \([l,r]\) 全部置為 \(mid+1\) 的操作次數。依次枚舉區間 \([l,r]\) 中的數 \(i\) 並且計算將 \([l,i]\) 置為 \(mid\)、將 \([i+1,r]\) 置為 \(mid+1\) 的操作次數之和，如果優於之前的操作次數則更新最少操作次數和要劃分到 \([ql,mid]\) 的數的個數。

劃分時已經保證了最終序列的單調性不被破壞，同時因為每次都取最小操作次數，最終被劃分至左區間的數取 \(mid\) 一定比取 \(mid+1\) 更優，故整體二分得到的序列一定是單調不降且操作次數最小的。計算操作次數輸出即可。

參考代碼（關鍵部分）

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
int a[500005], ans[500005];  // a:原序列 ans:構造的序列

void overall_binary(int l, int r, int ql, int qr) {
  if (l > r) return;
  if (ql == qr) {
    for (int i = l; i <= r; i++) ans[i] = ql;
    return;
  }
  int cnt = 0,
      mid = ql + ((qr - ql) >> 1);  // 默認開始都填 mid+1 全部劃分到右區間
  long long res = 0ll, sum = 0ll;
  for (int i = l; i <= r; i++) sum += abs(a[i] - (mid + 1));
  res = sum;
  for (int i = l; i <= r;
       i++) {  // 嘗試把 [l,i] 從 mid+1 換成 mid 並且劃分到左區間
    sum -= abs(a[i] - (mid + 1));
    sum += abs(a[i] - mid);
    if (sum < res) cnt = i - l + 1, res = sum;  // 發現 [l,i] 取 mid 更優,更新
  }
  overall_binary(l, l + cnt - 1, ql, mid);
  overall_binary(l + cnt, r, mid + 1, qr);
}

參考習題

「國家集訓隊」矩陣乘法

「POI2011 R3 Day2」流星 Meteors

二逼平衡樹

[BalticOI 2004] Sequence 數字序列

參考資料

  • 許昊然《淺談數據結構題幾個非經典解法》
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用