跳转至

CDQ 分治

本頁面將介紹 CDQ 分治。

簡介

CDQ 分治是一種思想而不是具體的算法，與 動態規劃 類似。目前這個思想的拓展十分廣泛，依原理與寫法的不同，大致分為三類：

  • 解決和點對有關的問題。
  • 1D 動態規劃的優化與轉移。
  • 通過 CDQ 分治，將一些動態問題轉化為靜態問題。

CDQ 分治的思想最早由 IOI2008 金牌得主陳丹琦在高中時整理並總結，它也因此得名。1

解決和點對有關的問題

這類問題多數類似於「給定一個長度為 n 的序列，統計有一些特性的點對 \((i,j)\) 的數量/找到一對點 \((i,j)\) 使得一些函數的值最大」。

CDQ 分治解決這類問題的算法流程如下：

  1. 找到這個序列的中點 \(mid\)；

  2. 將所有點對 \((i,j)\) 劃分為 3 類：

    1. \(1 \leq i \leq mid,1 \leq j \leq mid\) 的點對；
    2. \(1 \leq i \leq mid ,mid+1 \leq j \leq n\) 的點對；
    3. \(mid+1 \leq i \leq n,mid+1 \leq j \leq n\) 的點對。

  3. 將 \((1,n)\) 這個序列拆成兩個序列 \((1,mid)\) 和 \((mid+1,n)\)。此時第一類點對和第三類點對都在這兩個序列之中；

  4. 遞歸地處理這兩類點對；

  5. 設法處理第二類點對。

可以看到 CDQ 分治的思想就是不斷地把點對通過遞歸的方式分給左右兩個區間。

在實際應用時，我們通常使用一個函數 solve(l,r) 處理 \(l \leq i \leq r,l \leq j \leq r\) 的點對。上述算法流程中的遞歸部分便是通過 solve(l,mid) 與 solve(mid,r) 來實現的。剩下的第二類點對則需要額外設計算法解決。

例題

三維偏序

給定一個序列，每個點有 \(a_i,b_i,c_i\) 三個屬性，試求：這個序列裏有多少對點對 \((i,j)\) 滿足 \(a_j \leq a_i\) 且 \(b_j \leq b_i\) 且 \(c_j \leq c_i\) 且 \(j \ne i\)。

解題思路

三維偏序是 CDQ 分治的經典問題。

題目要求統計序列裏點對的個數，那試一下用 CDQ 分治。

首先將序列按 \(a\) 排序。

假設我們現在寫好了 solve(l,r)，並且通過遞歸搞定了 solve(l,mid) 和 solve(mid+1,r)。現在我們要做的，就是統計滿足 \(l \leq i \leq mid\),\(mid+1 \leq j \leq r\) 的點對 \((i,j)\) 中，有多個點對還滿足 \(a_{i}<a_{j}\),\(b_{i}<b_{j}\),\(c_{i}<c_{j}\) 的限制條件。

稍微思考一下就會發現，那個 \(a_{i}<a_{j}\) 的限制條件沒啥用了：已經將序列按 \(a\) 排序，則 \(a_{i} < a_{j}\) 可轉化為 \(i < j\)。既然 \(i\) 比 \(mid\) 小，\(j\) 比 \(mid\) 大，那 \(i\) 肯定比 \(j\) 要小。現在還剩下兩個限制條件：\(b_{i}<b_{j}\) 與 \(c_{i}<c_{j}\), 根據這個限制條件我們就可以枚舉 \(j\), 求出有多少個滿足條件的 \(i\)。

為了方便枚舉，我們把 \((l,mid)\) 和 \((mid+1,r)\) 中的點全部按照 \(b\) 的值從小到大排個序。之後我們依次枚舉每一個 \(j\), 把所有 \(b_{i}<b_{j}\) 的點 \(i\) 全部插入到某種數據結構裏（這裏我們選擇 樹狀數組）。此時只要查詢樹狀數組裏有多少個點的 \(c\) 值是小於 \(c_{j}\) 的，我們就求出了對於這個點 \(j\)，有多少個 \(i\) 可以合法匹配它了。

當我們插入一個 \(c\) 值等於 \(x\) 的點時，我們就令樹狀數組的 \(x\) 這個位置單點 + 1，而查詢樹狀數組裏有多少個點小於 \(x\) 的操作實際上就是在求 前綴和，只要我們事先對於所有的 \(c\) 值做了 離散化，我們的複雜度就是對的。

對於每一個 \(j\)，我們都需要將所有 \(b_{i}<b_{j}\) 的點 \(i\) 插入樹狀數組中。由於所有的 \(i\) 和 \(j\) 都已事先按照 \(b\) 值排好序，這樣的話只要以雙指針的方式在樹狀數組裏插入點，則對樹狀數組的插入操作就能從 \(O(n^2)\) 次降到 \(O(n)\) 次。

通過這樣一個算法流程，我們就用 \(O(n\log n)\) 的時間處理完了關於第二類點對的信息了。此時算法的時間複雜度是 \(T(n)=T(\lfloor \frac{n}{2} \rfloor)+T(\lceil \frac{n}{2} \rceil)+O(n\log n)=O(n\log^2n)\)。

示例代碼 
  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
#include <algorithm>
#include <cstdio>

const int maxN = 1e5 + 10;
const int maxK = 2e5 + 10;

int n, k;

struct Element {
  int a, b, c;
  int cnt;
  int res;

  bool operator!=(Element other) {
    if (a != other.a) return true;
    if (b != other.b) return true;
    if (c != other.c) return true;
    return false;
  }
};

Element e[maxN];
Element ue[maxN];
int m, t;
int res[maxN];

struct BinaryIndexedTree {
  int node[maxK];

  int lowbit(int x) { return x & -x; }

  void Add(int pos, int val) {
    while (pos <= k) {
      node[pos] += val;
      pos += lowbit(pos);
    }
    return;
  }

  int Ask(int pos) {
    int res = 0;
    while (pos) {
      res += node[pos];
      pos -= lowbit(pos);
    }
    return res;
  }
} BIT;

bool cmpA(Element x, Element y) {
  if (x.a != y.a) return x.a < y.a;
  if (x.b != y.b) return x.b < y.b;
  return x.c < y.c;
}

bool cmpB(Element x, Element y) {
  if (x.b != y.b) return x.b < y.b;
  return x.c < y.c;
}

void CDQ(int l, int r) {
  if (l == r) return;
  int mid = (l + r) / 2;
  CDQ(l, mid);
  CDQ(mid + 1, r);
  std::sort(ue + l, ue + mid + 1, cmpB);
  std::sort(ue + mid + 1, ue + r + 1, cmpB);
  int i = l;
  int j = mid + 1;
  while (j <= r) {
    while (i <= mid && ue[i].b <= ue[j].b) {
      BIT.Add(ue[i].c, ue[i].cnt);
      i++;
    }
    ue[j].res += BIT.Ask(ue[j].c);
    j++;
  }
  for (int k = l; k < i; k++) BIT.Add(ue[k].c, -ue[k].cnt);
  return;
}

int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
  std::sort(e + 1, e + n + 1, cmpA);
  for (int i = 1; i <= n; i++) {
    t++;
    if (e[i] != e[i + 1]) {
      m++;
      ue[m].a = e[i].a;
      ue[m].b = e[i].b;
      ue[m].c = e[i].c;
      ue[m].cnt = t;
      t = 0;
    }
  }
  CDQ(1, m);
  for (int i = 1; i <= m; i++) res[ue[i].res + ue[i].cnt - 1] += ue[i].cnt;
  for (int i = 0; i < n; i++) printf("%d\n", res[i]);
  return 0;
}
CQOI2011 動態逆序對

對於序列 \(a\)，它的逆序對數定義為集合 \(\{(i,j)| i<j \wedge a_i > a_j \}\) 中的元素個數。

現在給出 \(1\sim n\) 的一個排列，按照某種順序依次刪除 \(m\) 個元素，你的任務是在每次刪除一個元素之前統計整個序列的逆序對數。

示例代碼 
  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 <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;
int n;
int m;

struct treearray {
  int ta[200010];

  void ub(int& x) { x += x & (-x); }

  void db(int& x) { x -= x & (-x); }

  void c(int x, int t) {
    for (; x <= n + 1; ub(x)) ta[x] += t;
  }

  int sum(int x) {
    int r = 0;
    for (; x > 0; db(x)) r += ta[x];
    return r;
  }
} ta;

struct data_ {
  int val;
  int del;
  int ans;
} a[100010];

int rv[100010];
ll res;

bool cmp1(const data_& a, const data_& b) {
  return a.val < b.val;
}  // 重写两个比较

bool cmp2(const data_& a, const data_& b) { return a.del < b.del; }

void solve(int l, int r) {  // 底下是具体的式子，套用
  if (r - l == 1) {
    return;
  }
  int mid = (l + r) / 2;
  solve(l, mid);
  solve(mid, r);
  int i = l + 1;
  int j = mid + 1;
  while (i <= mid) {
    while (a[i].val > a[j].val && j <= r) {
      ta.c(a[j].del, 1);
      j++;
    }
    a[i].ans += ta.sum(m + 1) - ta.sum(a[i].del);
    i++;
  }
  i = l + 1;
  j = mid + 1;
  while (i <= mid) {
    while (a[i].val > a[j].val && j <= r) {
      ta.c(a[j].del, -1);
      j++;
    }
    i++;
  }
  i = mid;
  j = r;
  while (j > mid) {
    while (a[j].val < a[i].val && i > l) {
      ta.c(a[i].del, 1);
      i--;
    }
    a[j].ans += ta.sum(m + 1) - ta.sum(a[j].del);
    j--;
  }
  i = mid;
  j = r;
  while (j > mid) {
    while (a[j].val < a[i].val && i > l) {
      ta.c(a[i].del, -1);
      i--;
    }
    j--;
  }
  sort(a + l + 1, a + r + 1, cmp1);
  return;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i].val);
    rv[a[i].val] = i;
  }
  for (int i = 1; i <= m; i++) {
    int p;
    scanf("%d", &p);
    a[rv[p]].del = i;
  }
  for (int i = 1; i <= n; i++) {
    if (a[i].del == 0) a[i].del = m + 1;
  }
  for (int i = 1; i <= n; i++) {
    res += ta.sum(n + 1) - ta.sum(a[i].val);
    ta.c(a[i].val, 1);
  }
  for (int i = 1; i <= n; i++) {
    ta.c(a[i].val, -1);
  }
  solve(0, n);
  sort(a + 1, a + n + 1, cmp2);
  for (int i = 1; i <= m; i++) {
    printf("%lld\n", res);
    res -= a[i].ans;
  }
  return 0;
}

CDQ 分治優化 1D/1D 動態規劃的轉移

1D/1D 動態規劃指的是一類特定的 DP 問題，該類題目的特徵是 DP 數組是一維的，轉移是 \(O(n)\) 的。如果條件良好的話，有時可以通過 CDQ 分治來把它們的時間複雜度由 \(O(n^2)\) 降至 \(O(n\log^2n)\)。

例如，給定一個序列，每個元素有兩個屬性 \(a\)，\(b\)。我們希望計算一個 DP 式子的值，它的轉移方程如下：

\(dp_{i}=1+ \max_{j=1}^{i-1}dp_{j}[a_{j}<a_{i}][b_{j}<b_{i}]\)

這是一個二維最長上升子序列的 DP 方程，即只有 \(j<i,a_{j}<a_{i}\),\(b_{j}<b_{i}\) 的點 \(j\) 可以更新點 \(i\) 的 DP 值。

直接轉移顯然是 \(O(n^2)\) 的。以下是使用 CDQ 分治優化轉移過程的講解。

我們發現 \(dp_{j}\) 轉移到 \(dp_{i}\) 這種轉移關係也是一種點對間的關係，所以我們用類似 CDQ 分治處理點對關係的方式來處理它。

這個轉移過程相對來講比較套路。假設現在正在處理的區間是 \((l,r)\)，算法流程大致如下：

  1. 如果 \(l=r\)，説明 \(dp_{r}\) 值已經被計算好了。直接令 \(dp_{r}++\) 然後返回即可；
  2. 遞歸使用 solve(l,mid)；
  3. 處理所有 \(l \leq j \leq mid\)，\(mid+1 \leq i \leq r\) 的轉移關係；
  4. 遞歸使用 solve(mid+1,r)。

第三步的做法與 CDQ 分治求三維偏序差不多。處理 \(l \leq j \leq mid\)，\(mid+1 \leq i \leq r\) 的轉移關係的時候，我們會發現已經不用管 \(j<i\) 這個限制條件了。因此，我們依然先將所有的點 \(i\) 和點 \(j\) 按 \(a\) 值進行排序處理，然後用雙指針的方式將 \(j\) 點插入到樹狀數組裏，最後查一下前綴最大值更新一下 \(dp_{i}\) 就可以了。

轉移過程的正確性證明

該 CDQ 寫法和處理點對間關係的 CDQ 寫法最大的不同就是處理 \(l \leq j \leq mid\)，\(mid+1 \leq i \leq r\) 的點對這一部分。處理點對間關係的 CDQ 寫法中，這一部分放到哪裏都是可以的。但是，在用 CDQ 分治優化 DP 的時候，這個流程卻必須夾在 \(solve(l,mid)\),\(solve(mid+1,r)\) 的中間。原因是 DP 的轉移是 有序的，它必須滿足兩個條件，否則就是不對的：

  1. 用來計算 \(dp_{i}\) 的所有 \(dp_{j}\) 值都必須是已經計算完畢的，不能存在「半成品」；

  2. 用來計算 \(dp_{i}\) 的所有 \(dp_{j}\) 值都必須能更新到 \(dp_{i}\)，不能存在沒有更新到的 \(dp_{j}\) 值。

上述兩個條件可能在 \(O(n^2)\) 暴力的時候是相當容易滿足的，但是使用 CDQ 分治後，轉移順序很顯然已經亂掉了，所以有必要考察轉移的正確性。

CDQ 分治的遞歸樹如下所示。

CDQ 分治的遞歸樹

執行剛才的算法流程的話，以 \(8\) 這個點為例，它的 DP 值是在 solve(1,8)、solve(5,8)、solve(7,8) 這 3 個函數中更新完成的，而三次用來更新它的點分別是 \((1,4)\)、\((5,6)\)、\((7,7)\) 這三個不相交的區間；又以 \(5\) 這個點為例，它的 DP 值是在 solve(1,4) 函數中解決的，更新它的區間是 \((1,4)\)。仔細觀察就會發現，一個 \(i\) 點的 DP 值被更新了 \(\log\) 次，而且，更新它的區間剛好是 \((1,i)\) 在線段樹上被拆分出來的 \(\log\) 個區間。因此，我們的確保證了所有合法的 \(j\) 都更新過點 \(i\)，滿足第 2 個條件。

接着分析我們算法的執行流程：

  1. 第一個結束的函數是 solve(1,1)。此時我們發現 \(dp_{1}\) 的值已經計算完畢了；
  2. 第一個執行轉移過程的函數是 solve(1,2)。此時我們發現 \(dp_{2}\) 的值已經被轉移好了；
  3. 第二個結束的函數是 solve(2,2)。此時我們發現 \(dp_{2}\) 的值已經計算完畢了；
  4. 接下來 solve(1,2) 結束，\((1,2)\) 這段區間的 \(dp\) 值均被計算好；
  5. 下一個執行轉移流程的函數是 solve(1,4)。這次轉移結束之後我們發現 \(dp_{3}\) 的值已經被轉移好了；
  6. 接下來結束的函數是 solve(3,3)。我們會發現 \(dp_{3}\) 的 dp 值被計算好了；
  7. 接下來執行的轉移是 solve(2,4)。此時 \(dp_{4}\) 在 solve(1,4) 中被 \((1,2)\) 轉移了一次，這次又被 \((3,3)\) 轉移了，因此 \(dp_{4}\) 的值也被轉移好了；
  8. solve(4,4) 結束，\(dp_{4}\) 的值計算完畢；
  9. solve(3,4) 結束，\((3,4)\) 的值計算完畢；
  10. solve(1,4) 結束，\((1,4)\) 的值計算完畢。
  11. ……

通過模擬函數流程，我們發現一件事：每次 solve(l,r) 結束的時候，\((l,r)\) 區間的 DP 值會被全部計算好。由於我們每一次執行轉移函數的時候，solve(l,mid) 已經結束，因此我們每一次執行的轉移過程都是合法的，滿足第 1 個條件。

在剛才的過程我們發現，如果將 CDQ 分治的遞歸樹看成一顆線段樹，那麼 CDQ 分治就是這個線段樹的 中序遍歷函數，因此我們相當於按順序處理了所有的 DP 值，只是轉移順序被拆開了而已，所以算法是正確的。

例題

SDOI2011 攔截導彈

某國為了防禦敵國的導彈襲擊，發展出一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度、並且能夠攔截任意速度的導彈，但是以後每一發炮彈都不能高於前一發的高度，其攔截的導彈的飛行速度也不能大於前一發。某天，雷達捕捉到敵國的導彈來襲。由於該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈。

在不能攔截所有的導彈的情況下，我們當然要選擇使國家損失最小、也就是攔截導彈的數量最多的方案。但是攔截導彈數量的最多的方案有可能有多個，如果有多個最優方案，那麼我們會隨機選取一個作為最終的攔截導彈行動藍圖。

我方間諜已經獲取了所有敵軍導彈的高度和速度，你的任務是計算出在執行上述決策時，每枚導彈被攔截掉的概率。

參考代碼 
  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
160
161
162
163
164
// 一道二维最长上升子序列的题
// 为了确定某一个元素是否在最长上升子序列中可以正反跑两遍 CDQ
#include <algorithm>
#include <cstdio>
using namespace std;
typedef double db;
const int N = 1e6 + 10;

struct data_ {
  int h;
  int v;
  int p;
  int ma;
  db ca;
} a[2][N];

int n;
bool tr;

// 底下是重写比较
bool cmp1(const data_& a, const data_& b) {
  if (tr)
    return a.h > b.h;
  else
    return a.h < b.h;
}

bool cmp2(const data_& a, const data_& b) {
  if (tr)
    return a.v > b.v;
  else
    return a.v < b.v;
}

bool cmp3(const data_& a, const data_& b) {
  if (tr)
    return a.p < b.p;
  else
    return a.p > b.p;
}

bool cmp4(const data_& a, const data_& b) { return a.v == b.v; }

struct treearray {
  int ma[2 * N];
  db ca[2 * N];

  void c(int x, int t, db c) {
    for (; x <= n; x += x & (-x)) {
      if (ma[x] == t) {
        ca[x] += c;
      } else if (ma[x] < t) {
        ca[x] = c;
        ma[x] = t;
      }
    }
  }

  void d(int x) {
    for (; x <= n; x += x & (-x)) {
      ma[x] = 0;
      ca[x] = 0;
    }
  }

  void q(int x, int& m, db& c) {
    for (; x > 0; x -= x & (-x)) {
      if (ma[x] == m) {
        c += ca[x];
      } else if (m < ma[x]) {
        c = ca[x];
        m = ma[x];
      }
    }
  }
} ta;

int rk[2][N];

void solve(int l, int r, int t) {  // 递归跑
  if (r - l == 1) {
    return;
  }
  int mid = (l + r) / 2;
  solve(l, mid, t);
  sort(a[t] + mid + 1, a[t] + r + 1, cmp1);
  int p = l + 1;
  for (int i = mid + 1; i <= r; i++) {
    for (; (cmp1(a[t][p], a[t][i]) || a[t][p].h == a[t][i].h) && p <= mid;
         p++) {
      ta.c(a[t][p].v, a[t][p].ma, a[t][p].ca);
    }
    db c = 0;
    int m = 0;
    ta.q(a[t][i].v, m, c);
    if (a[t][i].ma < m + 1) {
      a[t][i].ma = m + 1;
      a[t][i].ca = c;
    } else if (a[t][i].ma == m + 1) {
      a[t][i].ca += c;
    }
  }
  for (int i = l + 1; i <= mid; i++) {
    ta.d(a[t][i].v);
  }
  sort(a[t] + mid, a[t] + r + 1, cmp3);
  solve(mid, r, t);
  sort(a[t] + l + 1, a[t] + r + 1, cmp1);
}

void ih(int t) {
  sort(a[t] + 1, a[t] + n + 1, cmp2);
  rk[t][1] = 1;
  for (int i = 2; i <= n; i++) {
    rk[t][i] = (cmp4(a[t][i], a[t][i - 1])) ? rk[t][i - 1] : i;
  }
  for (int i = 1; i <= n; i++) {
    a[t][i].v = rk[t][i];
  }
  sort(a[t] + 1, a[t] + n + 1, cmp3);
  for (int i = 1; i <= n; i++) {
    a[t][i].ma = 1;
    a[t][i].ca = 1;
  }
}

int len;
db ans;

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &a[0][i].h, &a[0][i].v);
    a[0][i].p = i;
    a[1][i].h = a[0][i].h;
    a[1][i].v = a[0][i].v;
    a[1][i].p = i;
  }
  ih(0);
  solve(0, n, 0);
  tr = 1;
  ih(1);
  solve(0, n, 1);
  tr = 1;
  sort(a[0] + 1, a[0] + n + 1, cmp3);
  sort(a[1] + 1, a[1] + n + 1, cmp3);
  for (int i = 1; i <= n; i++) {
    len = max(len, a[0][i].ma);
  }
  printf("%d\n", len);
  for (int i = 1; i <= n; i++) {
    if (a[0][i].ma == len) {
      ans += a[0][i].ca;
    }
  }
  for (int i = 1; i <= n; i++) {
    if (a[0][i].ma + a[1][i].ma - 1 == len) {
      printf("%.5lf ", (a[0][i].ca * a[1][i].ca) / ans);
    } else {
      printf("0.00000 ");
    }
  }
  return 0;
}

將動態問題轉化為靜態問題

前兩種情況使用 CDQ 分治的目的是將序列折半之後遞歸處理點對間的關係，來獲得良好的複雜度。不過在本節中，折半的不是一般的序列，而是時間序列。

它適用於一些「需要支持做 xxx 修改然後做 xxx 詢問」的數據結構題。該類題目有兩個特點：

  • 如果把詢問 離線，所有操作會按照時間自然地排成一個序列。
  • 每一個修改均與之後的詢問操作息息相關。而這樣的「修改 - 詢問」關係一共會有 \(O(n^2)\) 對。

我們可以使用 CDQ 分治對於這個操作序列進行分治，處理修改和詢問之間的關係。

與處理點對關係的 CDQ 分治類似，假設正在分治的序列是 \((l,r)\), 我們先遞歸地處理 \((l,mid)\) 和 \((mid,r)\) 之間的修改 - 詢問關係，再處理所有 \(l \leq i \leq mid\)，\(mid+1 \leq j \leq r\) 的修改 - 詢問關係，其中 \(i\) 是一個修改，\(j\) 是一個詢問。

注意，如果各個修改之間是 獨立 的話，我們無需處理 \(l \leq i \leq mid\) 和 \(mid+1 \leq j \leq r\)，以及 solve(l,mid) 和 solve(mid+1,r) 之間的時序關係（比如普通的加減法問題）。但是如果各個修改之間並不獨立（比如説賦值操作），做完這個修改後，序列長什麼樣可能依賴於之前的序列。此時處理所有跨越 mid 的修改 - 詢問關係的步驟就必須放在 solve(l,mid) 和 solve(mid+1,r) 之間。理由和 CDQ 分治優化 1D/1D 動態規劃的原因是一樣的：按照中序遍歷序進行分治才能保證每一個修改都是嚴格按照時間順序執行的。

例題

矩形加矩形求和

維護一個二維平面，然後支持在一個矩形區域內加一個數字，每次詢問一個矩形區域的和。

解題思路

對於這個問題的靜態版本，即「二維平面裏有一堆矩形，我們希望詢問一個矩形區域的和」，有一個經典做法叫線段樹 + 掃描線。具體的做法是先將每個矩形拆成插入和刪除兩個操作，接着將每個詢問拆成兩個前綴和相減的形式，最後離線。然而，原題目是動態的，不能直接使用這種做法。

嘗試對其使用 CDQ 分治。我們將所有的詢問和修改操作全部離線。這些操作形成了一個序列，並且有 \(O(N^2)\) 對修改 - 詢問的關係。依然使用 CDQ 分治的一般流程，將所有的關係分成三類，在這一層分治過程當中只處理跨越 \(mid\) 的修改 - 詢問關係，剩下的修改 - 詢問關係通過遞歸的的方式來解決。

我們發現，所有的修改在詢問之前就已完成。這時，原問題等價於「平面上有靜態的一堆矩形，不停地詢問一個矩形區域的和」。

使用一個掃描線在 \(O(n\log n)\) 的時間內處理好所有跨越 \(mid\) 的修改 - 詢問關係，剩下的事情就是遞歸地分治左右兩側的修改 - 詢問關係了。

在這樣實現的 CDQ 分治中，同一個詢問被處理了 \(O(\log n)\) 次。不過沒有關係，因為每次貢獻這個詢問的修改是互不相交的。全套流程的時間複雜度為 \(T(n)=T(\lfloor \frac{n}{2} \rfloor)+T(\lceil \frac{n}{2} \rceil)+ O(n\log n)=O(n\log^2n)\)。

觀察上述的算法流程，我們發現一開始我們只能解決靜態的矩形加矩形求和問題，但只是簡單地使用 CDQ 分治後，我們就可以離線地解決一個動態的矩形加矩形求和問題了。將動態問題轉化為靜態問題的精髓就在於 CDQ 分治每次僅僅處理跨越某一個點的修改和詢問關係，這樣的話我們就只需要考慮「所有詢問都在修改之後」這個簡單的問題了。也正是因為這一點，CDQ 分治被稱為「動態問題轉化為靜態問題的工具」。

[Ynoi2016] 鏡中的昆蟲

維護一個長為 \(n\) 的序列 \(a_i\)，有 \(m\) 次操作。

  1. 將區間 \([l,r]\) 的值修改為 \(x\)；
  2. 詢問區間 \([l,r]\) 出現了多少種不同的數，也就是説同一個數出現多次只算一個。
解題思路

一句話題意：區間賦值區間數顏色。

維護一下每個位置左側第一個同色點的位置，記為 \(pre_{i}\)，此時區間數顏色就被轉化為了一個經典的二維數點問題。

通過將連續的一段顏色看成一個點的方式，可以證明 \(pre\) 的變化量是 \(O(n+m)\) 的，即單次操作僅僅引起 \(O(1)\) 的 \(pre\) 值變化，那麼我們可以用 CDQ 分治來解決動態的單點加矩形求和問題。

\(pre\) 數組的具體變化可以使用 std::set 來進行處理。這個用 set 維護連續的區間的技巧也被稱之為 old driver tree。

參考代碼 
  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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
#include <algorithm>
#include <cstdio>
#include <map>
#include <set>
#define SNI set<nod>::iterator
#define SDI set<data>::iterator
using namespace std;
const int N = 1e5 + 10;
int n;
int m;
int pre[N];
int npre[N];
int a[N];
int tp[N];
int lf[N];
int rt[N];
int co[N];

struct modi {
  int t;
  int pos;
  int pre;
  int va;

  friend bool operator<(modi a, modi b) { return a.pre < b.pre; }
} md[10 * N];

int tp1;

struct qry {
  int t;
  int l;
  int r;
  int ans;

  friend bool operator<(qry a, qry b) { return a.l < b.l; }
} qr[N];

int tp2;
int cnt;

bool cmp(const qry& a, const qry& b) { return a.t < b.t; }

void modify(int pos, int co)  // 修改函数
{
  if (npre[pos] == co) return;
  md[++tp1] = (modi){++cnt, pos, npre[pos], -1};
  md[++tp1] = (modi){++cnt, pos, npre[pos] = co, 1};
}

namespace prew {
int lst[2 * N];
map<int, int> mp;  // 提前离散化

void prew() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), mp[a[i]] = 1;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &tp[i], &lf[i], &rt[i]);
    if (tp[i] == 1) scanf("%d", &co[i]), mp[co[i]] = 1;
  }
  map<int, int>::iterator it, it1;
  for (it = mp.begin(), it1 = it, ++it1; it1 != mp.end(); ++it, ++it1)
    it1->second += it->second;
  for (int i = 1; i <= n; i++) a[i] = mp[a[i]];
  for (int i = 1; i <= n; i++)
    if (tp[i] == 1) co[i] = mp[co[i]];
  for (int i = 1; i <= n; i++) pre[i] = lst[a[i]], lst[a[i]] = i;
  for (int i = 1; i <= n; i++) npre[i] = pre[i];
}
}  // namespace prew

namespace colist {
struct data {
  int l;
  int r;
  int x;

  friend bool operator<(data a, data b) { return a.r < b.r; }
};

set<data> s;

struct nod {
  int l;
  int r;

  friend bool operator<(nod a, nod b) { return a.r < b.r; }
};

set<nod> c[2 * N];
set<int> bd;

void split(int mid) {  // 将一个节点拆成两个节点
  SDI it = s.lower_bound((data){0, mid, 0});
  data p = *it;
  if (mid == p.r) return;
  s.erase(p);
  s.insert((data){p.l, mid, p.x});
  s.insert((data){mid + 1, p.r, p.x});
  c[p.x].erase((nod){p.l, p.r});
  c[p.x].insert((nod){p.l, mid});
  c[p.x].insert((nod){mid + 1, p.r});
}

void del(set<data>::iterator it) {  // 删除一个迭代器
  bd.insert(it->l);
  SNI it1, it2;
  it1 = it2 = c[it->x].find((nod){it->l, it->r});
  ++it2;
  if (it2 != c[it->x].end()) bd.insert(it2->l);
  c[it->x].erase(it1);
  s.erase(it);
}

void ins(data p) {  // 插入一个节点
  s.insert(p);
  SNI it = c[p.x].insert((nod){p.l, p.r}).first;
  ++it;
  if (it != c[p.x].end()) {
    bd.insert(it->l);
  }
}

void stv(int l, int r, int x) {  // 区间赋值
  if (l != 1) split(l - 1);
  split(r);
  int p = l;  // split两下之后删掉所有区间
  while (p != r + 1) {
    SDI it = s.lower_bound((data){0, p, 0});
    p = it->r + 1;
    del(it);
  }
  ins((data){l, r, x});  // 扫一遍set处理所有变化的pre值
  for (set<int>::iterator it = bd.begin(); it != bd.end(); ++it) {
    SDI it1 = s.lower_bound((data){0, *it, 0});
    if (*it != it1->l)
      modify(*it, *it - 1);
    else {
      SNI it2 = c[it1->x].lower_bound((nod){0, *it});
      if (it2 != c[it1->x].begin())
        --it2, modify(*it, it2->r);
      else
        modify(*it, 0);
    }
  }
  bd.clear();
}

void ih() {
  int nc = a[1];
  int ccnt = 1;  // 将连续的一段插入到set中
  for (int i = 2; i <= n; i++)
    if (nc != a[i]) {
      s.insert((data){i - ccnt, i - 1, nc}),
          c[nc].insert((nod){i - ccnt, i - 1});
      nc = a[i];
      ccnt = 1;
    } else {
      ccnt++;
    }
  s.insert((data){n - ccnt + 1, n, a[n]}),
      c[a[n]].insert((nod){n - ccnt + 1, n});
}
}  // namespace colist

namespace CDQ {
struct treearray  // 树状数组
{
  int ta[N];

  void c(int x, int t) {
    for (; x <= n; x += x & (-x)) ta[x] += t;
  }

  void d(int x) {
    for (; x <= n; x += x & (-x)) ta[x] = 0;
  }

  int q(int x) {
    int r = 0;
    for (; x; x -= x & (-x)) r += ta[x];
    return r;
  }

  void clear() {
    for (int i = 1; i <= n; i++) ta[i] = 0;
  }
} ta;

int srt[N];

bool cmp1(const int& a, const int& b) { return pre[a] < pre[b]; }

void solve(int l1, int r1, int l2, int r2, int L, int R) {  // CDQ
  if (l1 == r1 || l2 == r2) return;
  int mid = (L + R) / 2;
  int mid1 = l1;
  while (mid1 != r1 && md[mid1 + 1].t <= mid) mid1++;
  int mid2 = l2;
  while (mid2 != r2 && qr[mid2 + 1].t <= mid) mid2++;
  solve(l1, mid1, l2, mid2, L, mid);
  solve(mid1, r1, mid2, r2, mid, R);
  if (l1 != mid1 && mid2 != r2) {
    sort(md + l1 + 1, md + mid1 + 1);
    sort(qr + mid2 + 1, qr + r2 + 1);
    for (int i = mid2 + 1, j = l1 + 1; i <= r2; i++) {  // 考虑左侧对右侧贡献
      while (j <= mid1 && md[j].pre < qr[i].l) ta.c(md[j].pos, md[j].va), j++;
      qr[i].ans += ta.q(qr[i].r) - ta.q(qr[i].l - 1);
    }
    for (int i = l1 + 1; i <= mid1; i++) ta.d(md[i].pos);
  }
}

void mainsolve() {
  colist::ih();
  for (int i = 1; i <= m; i++)
    if (tp[i] == 1)
      colist::stv(lf[i], rt[i], co[i]);
    else
      qr[++tp2] = (qry){++cnt, lf[i], rt[i], 0};
  sort(qr + 1, qr + tp2 + 1);
  for (int i = 1; i <= n; i++) srt[i] = i;
  sort(srt + 1, srt + n + 1, cmp1);
  for (int i = 1, j = 1; i <= tp2; i++) {  // 初始化一下每个询问的值
    while (j <= n && pre[srt[j]] < qr[i].l) ta.c(srt[j], 1), j++;
    qr[i].ans += ta.q(qr[i].r) - ta.q(qr[i].l - 1);
  }
  ta.clear();
  sort(qr + 1, qr + tp2 + 1, cmp);
  solve(0, tp1, 0, tp2, 0, cnt);
  sort(qr + 1, qr + tp2 + 1, cmp);
  for (int i = 1; i <= tp2; i++) printf("%d\n", qr[i].ans);
}
}  // namespace CDQ

int main() {
  prew::prew();
  CDQ::mainsolve();
  return 0;
}
[HNOI2010] 城市建設

PS 國是一個擁有諸多城市的大國。國王 Louis 為城市的交通建設可謂絞盡腦汁。Louis 可以在某些城市之間修建道路，在不同的城市之間修建道路需要不同的花費。

Louis 希望建造最少的道路使得國內所有的城市連通。但是由於某些因素，城市之間修建道路需要的花費會隨着時間而改變。Louis 會不斷得到某道路的修建代價改變的消息。他希望每得到一條消息後能立即知道使城市連通的最小花費總和。Louis 決定求助於你來完成這個任務。

解題思路

一句話題意：給定一張圖支持動態的修改邊權，要求在每次修改邊權之後輸出這張圖的最小生成樹的最小代價和。

事實上，有一個線段樹分治套 lct 的做法可以解決這個問題，但是這個實現方式的常數過大，可能需要精妙的卡常技巧才可以通過本題，因此不妨考慮 CDQ 分治來解決這個問題。

和一般的 CDQ 分治解決的問題不同，此時使用 CDQ 分治的時候並沒有修改和詢問的關係來讓我們進行分治，因為無法單獨考慮「修改一個邊對整張圖的最小生成樹有什麼貢獻」。傳統的 CDQ 分治思路似乎不是很好使。

通過剛才的例題可以發現，一般的 CDQ 分治和線段樹有着特殊的聯繫：我們在 CDQ 分治的過程中其實隱式地建了一棵線段樹出來（因為 CDQ 分治的遞歸樹就是一顆線段樹）。通常的 CDQ 是考慮線段樹左右兒子之間的聯繫。而對於這道題，我們需要考慮的是父親和孩子之間的關係；換句話來講，我們在 $solve(l,r)$ 這段區間的時候，如果可以想辦法使圖的規模變成和區間長度相關的一個變量的話，就可以解決這個問題了。

那麼具體來講如何設計算法呢？

假設我們正在構造 \((l,r)\) 這段區間的最小生成樹邊集，並且我們已知它父親最小生成樹的邊集。我們將在 \((l,r)\) 這段區間中發生變化的邊分別賦與 \(+ \infty\) 和 \(-\infty\) 的邊權，並各跑一邊 kruskal，求出在最小生成樹裏的那些邊。

對於一條邊來講：

  • 如果最小生成樹裏所有被修改的邊權都被賦成了 \(+\infty\)，而它未出現在樹中，則證明它不可能出現在 \((l,r)\) 這些詢問的最小生成樹當中。所以我們僅僅在 \((l,r)\) 的邊集中加入最小生成樹的樹邊。
  • 如果最小生成樹裏所有被修改的邊權都被賦成了 \(-\infty\)，而它未出現在樹中，則證明它一定會出現 \((l,r)\) 這段的區間的最小生成樹當中。這樣的話我們就可以使用並查集將這些邊對應的點縮起來，並且將答案加上這些邊的邊權。

這樣我們就將 \((l,r)\) 這段區間的邊集構造出來了。用這些邊求出來的最小生成樹和直接求原圖的最小生成樹等價。

那麼為什麼我們的複雜度是對的呢？

首先，修改過的邊一定會加進我們的邊集，這些邊的數目是 \(O(len)\) 級別的。

接下來我們需要證明邊集當中不會有過多的未被修改的邊。我們只會加入所有邊權取 \(+\infty\) 最小生成樹的樹邊，因此我們加入的邊數目不會超過當前圖的點數。

現在我們只需證明每遞歸一層圖的點數是 \(O(len)\) 級別的，就可以説明圖的邊數是 \(O(len)\) 級別的了。

證明點數是 \(O(len)\) 幾倍就變得十分簡單了。我們每次向下遞歸的時侯縮掉的邊是在 \(-\infty\) 生成樹中出現的未被修改邊，反過來想就是，我們割掉了出現在 \(-\infty\) 生成樹當中的所有的被修改邊。顯然我們最多割掉 \(len\) 條邊，整張圖最多分裂成 \(O(len)\) 個連通塊，這樣的話新圖點數就是 \(O(len)\) 級別的了。所以我們就證明了每次我們用來跑 kruskal 的圖都是 \(O(len)\) 級別的了，從而每一層的時間複雜度都是 \(O(n\log n)\) 了。

時間複雜度是 \(T(n)=T(\lfloor \frac{n}{2} \rfloor)+T(\lceil \frac{n}{2} \rceil)+ O(n\log n)=O(n\log^2n)\)。

代碼實現上可能會有一些難度。需要注意的是並查集不能使用路徑壓縮，否則就不支持回退操作了。執行縮點操作的時候也沒有必要真的執行，而是每一層的 kruskal 都在上一層的並查集裏直接做就可以了。

示例代碼 
  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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
#include <algorithm>
#include <cstdio>
#include <stack>
#include <vector>
using namespace std;
typedef long long ll;
int n;
int m;
int ask;

struct bcj {
  int fa[20010];
  int size[20010];

  struct opt {
    int u;
    int v;
  };

  stack<opt> st;

  void ih() {
    for (int i = 1; i <= n; i++) fa[i] = i, size[i] = 1;
  }

  int f(int x) { return (fa[x] == x) ? x : f(fa[x]); }

  void u(int x, int y) {  // 带撤回
    int u = f(x);
    int v = f(y);
    if (u == v) return;
    if (size[u] < size[v]) swap(u, v);
    size[u] += size[v];
    fa[v] = u;
    opt o;
    o.u = u;
    o.v = v;
    st.push(o);
  }

  void undo() {
    opt o = st.top();
    st.pop();
    fa[o.v] = o.v;
    size[o.u] -= size[o.v];
  }

  void clear(int tim) {
    while (st.size() > tim) {
      undo();
    }
  }
} s, s1;

struct edge  // 静态边
{
  int u;
  int v;
  ll val;
  int mrk;

  friend bool operator<(edge a, edge b) { return a.val < b.val; }
} e[50010];

struct moved {
  int u;
  int v;
};  // 动态边

struct query {
  int num;
  ll val;
  ll ans;
} q[50010];

bool book[50010];  // 询问
vector<edge> ve[30];
vector<moved> vq;
vector<edge> tr;
ll res[30];
int tim[30];

void pushdown(int dep)  // 缩边
{
  tr.clear();  // 这里要复制一份，以免无法回撤操作
  for (int i = 0; i < ve[dep].size(); i++) {
    tr.push_back(ve[dep][i]);
  }
  sort(tr.begin(), tr.end());
  for (int i = 0; i < tr.size(); i++) {  // 无用边
    if (s1.f(tr[i].u) == s1.f(tr[i].v)) {
      tr[i].mrk = -1;
      continue;
    }
    s1.u(tr[i].u, tr[i].v);
  }
  s1.clear(0);
  res[dep + 1] = res[dep];
  for (int i = 0; i < vq.size(); i++) {
    s1.u(vq[i].u, vq[i].v);
  }
  vq.clear();
  for (int i = 0; i < tr.size(); i++) {  // 必须边
    if (tr[i].mrk == -1 || s1.f(tr[i].u) == s1.f(tr[i].v)) continue;
    tr[i].mrk = 1;
    s1.u(tr[i].u, tr[i].v);
    s.u(tr[i].u, tr[i].v);
    res[dep + 1] += tr[i].val;
  }
  s1.clear(0);
  ve[dep + 1].clear();
  for (int i = 0; i < tr.size(); i++) {  // 缩边
    if (tr[i].mrk != 0) continue;
    edge p;
    p.u = s.f(tr[i].u);
    p.v = s.f(tr[i].v);
    if (p.u == p.v) continue;
    p.val = tr[i].val;
    p.mrk = 0;
    ve[dep + 1].push_back(p);
  }
  return;
}

void solve(int l, int r, int dep) {
  tim[dep] = s.st.size();
  int mid = (l + r) / 2;
  if (r - l == 1) {  // 终止条件
    edge p;
    p.u = s.f(e[q[r].num].u);
    p.v = s.f(e[q[r].num].v);
    p.val = q[r].val;
    e[q[r].num].val = q[r].val;
    p.mrk = 0;
    ve[dep].push_back(p);
    pushdown(dep);
    q[r].ans = res[dep + 1];
    s.clear(tim[dep - 1]);
    return;
  }
  for (int i = l + 1; i <= mid; i++) {
    book[q[i].num] = true;
  }
  for (int i = mid + 1; i <= r; i++) {  // 动转静
    if (book[q[i].num]) continue;
    edge p;
    p.u = s.f(e[q[i].num].u);
    p.v = s.f(e[q[i].num].v);
    p.val = e[q[i].num].val;
    p.mrk = 0;
    ve[dep].push_back(p);
  }
  for (int i = l + 1; i <= mid; i++) {  // 询问转动态
    moved p;
    p.u = s.f(e[q[i].num].u);
    p.v = s.f(e[q[i].num].v);
    vq.push_back(p);
  }
  pushdown(dep);  // 下面的是回撤
  for (int i = mid + 1; i <= r; i++) {
    if (book[q[i].num]) continue;
    ve[dep].pop_back();
  }
  for (int i = l + 1; i <= mid; i++) {
    book[q[i].num] = false;
  }
  solve(l, mid, dep + 1);
  for (int i = 0; i < ve[dep].size(); i++) {
    ve[dep][i].mrk = 0;
  }
  for (int i = mid + 1; i <= r; i++) {
    book[q[i].num] = true;
  }
  for (int i = l + 1; i <= mid; i++) {  // 动转静
    if (book[q[i].num]) continue;
    edge p;
    p.u = s.f(e[q[i].num].u);
    p.v = s.f(e[q[i].num].v);
    p.val = e[q[i].num].val;
    p.mrk = 0;
    ve[dep].push_back(p);
  }
  for (int i = mid + 1; i <= r; i++) {  // 询问转动
    book[q[i].num] = false;
    moved p;
    p.u = s.f(e[q[i].num].u);
    p.v = s.f(e[q[i].num].v);
    vq.push_back(p);
  }
  pushdown(dep);
  solve(mid, r, dep + 1);
  s.clear(tim[dep - 1]);
  return;  // 时间倒流至上一层
}

int main() {
  scanf("%d%d%d", &n, &m, &ask);
  s.ih();
  s1.ih();
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%lld", &e[i].u, &e[i].v, &e[i].val);
  }
  for (int i = 1; i <= ask; i++) {
    scanf("%d%lld", &q[i].num, &q[i].val);
  }
  for (int i = 1; i <= ask; i++) {  // 初始动态边
    book[q[i].num] = true;
    moved p;
    p.u = e[q[i].num].u;
    p.v = e[q[i].num].v;
    vq.push_back(p);
  }
  for (int i = 1; i <= m; i++) {
    if (book[i]) continue;
    ve[1].push_back(e[i]);
  }  // 初始静态
  for (int i = 1; i <= ask; i++) {
    book[q[i].num] = false;
  }
  solve(0, ask, 1);
  for (int i = 1; i <= ask; i++) {
    printf("%lld\n", q[i].ans);
  }
  return 0;
}

參考資料與註釋

  1. 從《Cash》談一類分治算法的應用 ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用