Skip to content

CDQ Divide and Conquer

This page introduces CDQ divide and conquer.

Overview

CDQ divide and conquer is an idea rather than a specific algorithm, much like dynamic programming. The idea has by now been extended very widely. Depending on the principle and on how the code is written, its uses fall roughly into three classes:

  • Solving problems about pairs of points.
  • Optimizing and computing the transitions of 1D dynamic programming.
  • Using CDQ divide and conquer to turn certain dynamic problems into static ones.

The idea was first written up and summarized by Danqi Chen, an IOI 2008 gold medalist, while she was in high school, and it is named after her.1

Problems about pairs of points

Most problems of this kind look like "given a sequence of length \(n\), count the pairs \((i,j)\) that have some property" or "given a sequence of length \(n\), find a pair \((i,j)\) that maximizes some function".

CDQ divide and conquer solves such problems as follows:

  1. Find the midpoint \(mid\) of the sequence.

  2. Partition all pairs \((i,j)\) into three classes:

    1. pairs with \(1 \leq i \leq mid,1 \leq j \leq mid\);
    2. pairs with \(1 \leq i \leq mid ,mid+1 \leq j \leq n\);
    3. pairs with \(mid+1 \leq i \leq n,mid+1 \leq j \leq n\).
  3. Split the sequence \((1,n)\) into the two sequences \((1,mid)\) and \((mid+1,n)\). Every pair of the first or third class now lies inside one of these two sequences.

  4. Handle these two classes of pairs recursively.

  5. Find a way to handle the pairs of the second class.

The idea of CDQ divide and conquer, then, is to keep handing pairs down to the left and right ranges by recursion.

In practice we usually write a function solve(l,r) that handles the pairs with \(l \leq i \leq r,l \leq j \leq r\). The recursive part of the procedure above is then just the calls solve(l,mid) and solve(mid+1,r). The remaining pairs, those of the second class, need an algorithm designed separately.

Example problems

3D Partial Order

Given a sequence in which every point has three attributes \(a_i,b_i,c_i\), count the pairs \((i,j)\) in the sequence with \(a_j \leq a_i\), \(b_j \leq b_i\), \(c_j \leq c_i\) and \(j \ne i\).

Approach

3D partial order is the classic problem for CDQ divide and conquer.

The problem asks us to count pairs in a sequence, so let us try CDQ divide and conquer.

First sort the sequence by \(a\).

Suppose we are writing solve(l,r) and the recursive calls solve(l,mid) and solve(mid+1,r) have done their part. What remains is to count, among the pairs \((i,j)\) with \(l \leq i \leq mid\) and \(mid+1 \leq j \leq r\), those that also satisfy the constraints \(a_{i} \leq a_{j}\), \(b_{i} \leq b_{j}\) and \(c_{i} \leq c_{j}\).

A moment's thought shows that the constraint \(a_{i} \leq a_{j}\) no longer matters: \(i\) is at most \(mid\) and \(j\) is greater than \(mid\), so \(i\) is certainly less than \(j\), and since the sequence is sorted by \(a\) we must have \(a_{i} \leq a_{j}\). Two constraints remain: \(b_{i} \leq b_{j}\) and \(c_{i} \leq c_{j}\). Using them, we can enumerate \(j\) and count the \(i\) that satisfy both.

To make the enumeration easy, sort the points in \((l,mid)\) and the points in \((mid+1,r)\) by \(b\) in increasing order. Then enumerate the \(j\) one by one, inserting every point \(i\) with \(b_{i} \leq b_{j}\) into some data structure (here we choose a Fenwick tree). Now ask the Fenwick tree how many of its points have a \(c\) value less than or equal to \(c_{j}\): that is the number of \(i\) that form a valid pair with this point \(j\).

To insert a point whose \(c\) value equals \(x\), add one at position \(x\) of the Fenwick tree. Asking how many points in the Fenwick tree are less than or equal to \(x\) is then just a prefix sum query. As long as we apply coordinate compression to all the \(c\) values beforehand, the complexity is right.

For every \(j\) we have to insert all points \(i\) with \(b_{i} \leq b_{j}\) into the Fenwick tree. All the \(i\) and all the \(j\) are already sorted by \(b\), so if we insert the points with two pointers, the number of insertions into the Fenwick tree drops from \(O(n^2)\) to \(O(n)\).

This procedure handles the pairs of the second class in \(O(n\log n)\) time. The running time of the algorithm is then \(T(n)=T(\lfloor \frac{n}{2} \rfloor)+T(\lceil \frac{n}{2} \rceil)+O(n\log n)=O(n\log^2n)\).

Example code
  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
#include <algorithm>
#include <iostream>

constexpr int MAXN = 1e5 + 10;
constexpr int MAXK = 2e5 + 10;

int n, k;

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

  bool operator!=(Element other) const {
    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;
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> 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++) cout << res[i] << '\n';
  return 0;
}
CQOI2011 Dynamic Inversions

The number of inversions of a sequence \(a\) is defined as the number of elements of the set \(\{(i,j)| i < j \wedge a_i > a_j \}\).

You are given a permutation of \(1\sim n\), from which \(m\) elements are deleted one after another in a given order. Your task is to count the inversions of the whole sequence before each deletion.

Example code
  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
// Work it out carefully and you get almost the same formulas as 3D partial order; this is basically a 3D partial order template
#include <algorithm>
#include <iostream>
using namespace std;
using ll = long long;
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;

// two custom comparators
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) {  // the concrete formulas are below, applied as they are
  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() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].val;
    rv[a[i].val] = i;
  }
  for (int i = 1; i <= m; i++) {
    int p;
    cin >> 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++) {
    cout << res << '\n';
    res -= a[i].ans;
  }
  return 0;
}

Optimizing 1D/1D DP transitions with CDQ divide and conquer

Related content: optimizing DP with CDQ divide and conquer

1D/1D dynamic programming is a particular class of DP problems in which the DP array is one-dimensional and a transition takes \(O(n)\). When conditions are favorable, CDQ divide and conquer can sometimes bring their running time down from \(O(n^2)\) to \(O(n\log^2n)\).

For example, take a sequence in which every element has two attributes, \(a\) and \(b\). We want to evaluate a DP with the following recurrence:

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

This is the recurrence for a 2D longest increasing subsequence: only the points \(j\) with \(j < i,a_{j} < a_{i},b_{j} < b_{i}\) can update the DP value of point \(i\).

Computing the transitions directly clearly takes \(O(n^2)\). Here is how CDQ divide and conquer speeds them up.

A transition from \(dp_{j}\) to \(dp_{i}\) is also a relation between a pair of points, so we treat it much as CDQ divide and conquer treats pairs of points.

The procedure is fairly routine. Suppose the range being processed is \((l,r)\). The algorithm goes roughly as follows:

  1. If \(l=r\), the \(\max\) part of \(dp_{r}\) has already been computed: set \(dp_{r} \gets dp_{r} + 1\) and return.
  2. Call solve(l,mid) recursively.
  3. Handle all transitions with \(l \leq j \leq mid\) and \(mid+1 \leq i \leq r\).
  4. Call solve(mid+1,r) recursively.

Step 3 works much like solving 3D partial order with CDQ divide and conquer. For the transitions with \(l \leq j \leq mid\) and \(mid+1 \leq i \leq r\), the constraint \(j < i\) no longer needs any attention. So, as before, we sort all the points \(i\) and all the points \(j\) by \(a\), insert the points \(j\) into a Fenwick tree with two pointers, and query the prefix maximum to update \(dp_{i}\).

Proof of correctness of the transitions

The biggest difference between this way of writing CDQ and the one for relations between pairs of points lies in the step that handles the pairs with \(l \leq j \leq mid\) and \(mid+1 \leq i \leq r\). In the version for pairs of points, this step can go anywhere. When CDQ divide and conquer optimizes a DP, however, it has to sit between \(solve(l,mid)\) and \(solve(mid+1,r)\). The reason is that the transitions of a DP are ordered. They must satisfy two conditions, or the result is wrong:

  1. Every \(dp_{j}\) used to compute \(dp_{i}\) must already be fully computed; no half-finished value is allowed.

  2. Every \(dp_{j}\) that is meant to be used in computing \(dp_{i}\) must actually update \(dp_{i}\); none may be left out.

The \(O(n^2)\) brute force satisfies both conditions easily. With CDQ divide and conquer, though, the order of the transitions is clearly scrambled, so their correctness has to be examined.

The recursion tree of CDQ divide and conquer is shown below.

The recursion tree of CDQ divide and conquer

Run the algorithm above and take point \(8\) as an example. Its DP value is updated in three calls, solve(1,8), solve(5,8) and solve(7,8), and the points that update it in these three calls form the three disjoint ranges \((1,4)\), \((5,6)\) and \((7,7)\). Now take point \(5\): its DP value is settled in the call solve(1,8), and the range that updates it is \((1,4)\). Look closely and you will see that the DP value of a point \(i\) is updated \(\log\) times, and that the ranges updating it are exactly the \(\log\) ranges into which a segment tree splits \((1,i-1)\). So every valid \(j\) really does update point \(i\), and condition 2 holds.

Next, trace how the algorithm executes:

  1. The first call to finish is solve(1,1). At this point \(dp_{1}\) is fully computed.
  2. The first call to perform its transitions is solve(1,2). At this point \(dp_{2}\) has received all its transitions.
  3. The second call to finish is solve(2,2). At this point \(dp_{2}\) is fully computed.
  4. Then solve(1,2) finishes, and all the \(dp\) values in the range \((1,2)\) are computed.
  5. The next call to perform its transitions is solve(1,4). Once they are done, \(dp_{3}\) has received all its transitions.
  6. The next call to finish is solve(3,3), and \(dp_{3}\) is now fully computed.
  7. The next transitions are those of solve(3,4). \(dp_{4}\) was updated once from \((1,2)\) in solve(1,4) and is now updated from \((3,3)\), so it too has received all its transitions.
  8. solve(4,4) finishes, and \(dp_{4}\) is fully computed.
  9. solve(3,4) finishes, and the values in \((3,4)\) are fully computed.
  10. solve(1,4) finishes, and the values in \((1,4)\) are fully computed.
  11. ...

Simulating the calls shows one thing: whenever solve(l,r) finishes, all DP values in the range \((l,r)\) are fully computed. Whenever we perform the transitions, solve(l,mid) has already finished, so every transition we perform is valid, and condition 1 holds.

The trace also shows that if we view the recursion tree of CDQ divide and conquer as a segment tree, then CDQ divide and conquer is an inorder traversal of that segment tree. In effect we process all the DP values in order, and only the transitions are split up. So the algorithm is correct.

Example problems

SDOI2011 Missile Interception

To defend itself against missile attacks from an enemy country, a country has developed a missile interception system. The system has a flaw, however: its first shell can reach any height and intercept a missile of any speed, but every later shell can go no higher than the one before it, and the missile it intercepts can fly no faster than the one intercepted before. One day the radar picks up incoming enemy missiles. The system is still in its trial phase, so there is only one of it, and it may not be able to intercept all the missiles.

When not all the missiles can be intercepted, we of course choose a plan that minimizes the country's losses, that is, one that intercepts as many missiles as possible. There may be more than one such plan. If there are several optimal plans, we pick one of them at random as the final blueprint for the interception.

Our spies have obtained the heights and speeds of all the enemy missiles. Your task is to compute, for each missile, the probability that it is intercepted when the decision above is carried out.

Example code
  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
// a 2D longest increasing subsequence problem
// to decide whether an element lies on a longest increasing subsequence, run CDQ twice, forward and backward
#include <algorithm>
#include <iomanip>
#include <iostream>
using namespace std;
using db = double;
constexpr int N = 1e6 + 10;

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

int n;
bool tr;

// custom comparators below
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) {  // run recursively
  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() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> 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 = true;
  ih(1);
  solve(0, n, 1);
  tr = true;
  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);
  }
  cout << len << '\n';
  for (int i = 1; i <= n; i++) {
    if (a[0][i].ma == len) {
      ans += a[0][i].ca;
    }
  }
  cout << fixed << setprecision(5);
  for (int i = 1; i <= n; i++) {
    if (a[0][i].ma + a[1][i].ma - 1 == len) {
      cout << (a[0][i].ca * a[1][i].ca) / ans << ' ';
    } else {
      cout << "0.00000 ";
    }
  }
  return 0;
}

Turning dynamic problems into static ones

In the first two settings, CDQ divide and conquer halves a sequence and handles the relations between pairs of points recursively in order to get a good complexity. In this section, what gets halved is not an ordinary sequence but the timeline.

This applies to data structure problems of the form "support such-and-such updates and then answer such-and-such queries". Problems of this kind have two features:

  • If the queries are taken offline, all the operations naturally line up in a sequence ordered by time.
  • Every update is closely tied to the queries that come after it, and there are \(O(n^2)\) such update-query pairs in total.

We can run CDQ divide and conquer on this sequence of operations to handle the relations between updates and queries.

As in CDQ divide and conquer on pairs of points, suppose the sequence being divided is \((l,r)\). We first recursively handle the update-query pairs within \((l,mid)\) and within \((mid+1,r)\), and then all the update-query pairs with \(l \leq i \leq mid\) and \(mid+1 \leq j \leq r\), where \(i\) is an update and \(j\) is a query.

Note that if the updates are independent of one another (ordinary addition and subtraction, for example), it does not matter in which order we run the three steps: solve(l,mid), solve(mid+1,r), and the handling of the pairs with \(l \leq i \leq mid\) and \(mid+1 \leq j \leq r\). If the updates are not independent (assignments, say), what the sequence looks like after an update may depend on what it looked like before. The step that handles all the update-query pairs crossing mid must then go between solve(l,mid) and solve(mid+1,r). The reason is the same as for optimizing 1D/1D dynamic programming with CDQ divide and conquer: only by dividing in inorder traversal order can we guarantee that every update is applied strictly in chronological order.

Example problems

Rectangle addition, rectangle sum

Maintain a 2D array that supports adding a number to every cell of a rectangular region and querying the sum over a rectangular region.

Approach

The version of this problem without updates, "given a 2D array, answer many queries for the sum over a rectangular region", has a classic solution that combines a sweep line with a segment tree. Split each rectangle into two operations, an insertion and a deletion, then write each query as a difference of 2D prefix sums, and finally process everything offline. The original problem has updates, though, so this solution cannot be used directly.

Let us try CDQ divide and conquer on it. Take all the queries and updates offline. These operations form a sequence, and there are \(O(N^2)\) update-query pairs. Follow the general procedure of CDQ divide and conquer again: partition all the pairs into three classes, handle only the update-query pairs that cross \(mid\) at this level of the divide and conquer, and leave the remaining ones to the recursion.

Now all the updates are finished before the queries begin. The original problem is then equivalent to "there are some static rectangles in the plane; answer query after query for the sum over a rectangular region".

A sweep line handles all the update-query pairs that cross \(mid\) in \(O(n\log n)\) time. All that is left is to recurse on the update-query pairs of the left side and of the right side.

In CDQ divide and conquer implemented this way, the same query is processed \(O(\log n)\) times. That does not matter, because the sets of updates that contribute to the query each time are disjoint. The whole procedure runs in \(T(n)=T(\lfloor \frac{n}{2} \rfloor)+T(\lceil \frac{n}{2} \rceil)+ O(n\log n)=O(n\log^2n)\).

Look back at this procedure. At the start we could solve only the static rectangle addition, rectangle sum problem, yet simply by applying CDQ divide and conquer we can solve the dynamic one offline. The essence of turning a dynamic problem into a static one is that CDQ divide and conquer handles, each time, only the update-query pairs that cross one particular point, so the only problem we have to think about is the simple one in which every query comes after every update. This is exactly why CDQ divide and conquer is called "a tool for turning dynamic problems into static problems".

[Ynoi2016] Insects in the Mirror

Maintain a sequence \(a_i\) of length \(n\) under \(m\) operations.

  1. Set the values in the range \([l,r]\) to \(x\).
  2. Query how many distinct numbers occur in the range \([l,r]\); a number that occurs several times is counted only once.

The problem in one sentence: range assignment, range count of distinct colors.

Approach

For every position, maintain the position of the first point to its left that has the same color, and call it \(pre_{i}\). Counting the colors in a range then becomes a classic 2D point counting problem.

By treating a contiguous stretch of one color as a single point, one can prove that \(pre\) changes \(O(n+m)\) times in total, that is, a single operation causes only \(O(1)\) changes to the values of \(pre\). So we can use CDQ divide and conquer to solve a dynamic problem with point addition and rectangle sum queries.

The actual changes to the \(pre\) array can be worked out with std::set. This trick of maintaining contiguous ranges in a set is also known as the old driver tree.

Example code
  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
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#define SNI set<nod>::iterator
#define SDI set<data>::iterator
using namespace std;
constexpr 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)  // update function
{
  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;  // coordinate compression in advance

void prew() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i], mp[a[i]] = 1;
  for (int i = 1; i <= m; i++) {
    cin >> tp[i] >> lf[i] >> rt[i];
    if (tp[i] == 1) cin >> 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) {  // split one node into two nodes
  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) {  // delete the node at an iterator
  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) {  // insert a node
  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) {  // range assignment
  if (l != 1) split(l - 1);
  split(r);
  int p = l;  // after the two splits, delete all the ranges
  while (p != r + 1) {
    SDI it = s.lower_bound(data{0, p, 0});
    p = it->r + 1;
    del(it);
  }
  ins(data{l, r, x});  // scan the set and handle every pre value that changed
  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;  // insert each contiguous stretch into the 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  // Fenwick tree
{
  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++) {  // contribution of the left side to the right side
      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++) {  // initialize the value of every query
    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++) cout << qr[i].ans << '\n';
}
}  // namespace CDQ

int main() {
  prew::prew();
  CDQ::mainsolve();
  return 0;
}
[HNOI2010] City Construction

PS is a large country with a great many cities. Its king, Louis, has been racking his brains over the cities' transport network. Louis can build roads between certain pairs of cities, and roads between different pairs of cities cost different amounts to build.

Louis wants to build as few roads as possible so that all the cities in the country are connected. For various reasons, however, the cost of building a road between cities changes over time, and Louis keeps receiving news that the construction cost of some road has changed. After each piece of news he wants to know at once the minimum total cost of connecting the cities. Louis has decided to ask you for help with this task.

The problem in one sentence: given a graph whose edge weights are updated dynamically, output the minimum total cost of its minimum spanning tree after every update.

Approach

This problem can in fact be solved by segment tree divide and conquer combined with a Link Cut Tree, but that implementation has too large a constant factor and may need some clever constant-factor optimization to pass. So let us consider CDQ divide and conquer instead.

Unlike the problems that CDQ divide and conquer usually solves, this one offers no update-query relation to divide on, because we cannot consider in isolation "what updating one edge contributes to the minimum spanning tree of the whole graph". The traditional CDQ divide and conquer approach does not seem to work very well.

The earlier example problems show that ordinary CDQ divide and conquer has a special connection with the segment tree: during CDQ divide and conquer we implicitly build a segment tree (because the recursion tree of CDQ divide and conquer is a segment tree). Ordinary CDQ looks at the relation between the left and right children of a segment tree node. In this problem, what we need to look at is the relation between a parent and its children. In other words, if we can find a way to make the size of the graph in solve(l,r) depend on the length of the range, the problem is solved.

So how, concretely, do we design the algorithm?

Suppose we are constructing the edge set for the minimum spanning tree of the range \((l,r)\), and we know the edge set of its parent's minimum spanning tree. Give the edges that change within the range \((l,r)\) weight \(+ \infty\), then weight \(-\infty\), and run Kruskal's algorithm once for each to find the edges that are in the minimum spanning tree.

For a given edge:

  • If it does not appear in the minimum spanning tree in which all the updated edge weights are set to \(+\infty\), it cannot appear in the minimum spanning tree of any of the queries in \((l,r)\). So the only edges we add to the edge set of \((l,r)\) are the tree edges of that minimum spanning tree.
  • If it appears in the minimum spanning tree in which all the updated edge weights are set to \(-\infty\), it is certain to appear in the minimum spanning tree throughout the range \((l,r)\). We can then use a disjoint set union to contract the vertices these edges join, and add the weights of these edges to the answer.

This constructs the edge set of the range \((l,r)\). The minimum spanning tree computed from these edges is equivalent to the one computed directly on the original graph.

Why, then, is our complexity right?

First, the updated edges always go into our edge set, and there are \(O(len)\) of them.

Next we have to show that the edge set does not contain too many edges that were not updated. The only ones we add are the tree edges of the minimum spanning tree with all the updated weights set to \(+\infty\), so we add no more edges than the current graph has vertices.

Now it is enough to show that the graph has \(O(len)\) vertices at every level of the recursion; it then follows that it has \(O(len)\) edges.

Showing that the number of vertices is \(O(len)\) is now very easy. Each time we recurse downward, the edges we contract are the edges of the \(-\infty\) spanning tree that were not updated. Seen the other way round, we cut every updated edge that appears in the \(-\infty\) spanning tree. Clearly we cut at most \(len\) edges, so the whole graph splits into at most \(O(len)\) connected components, and the new graph has \(O(len)\) vertices. This proves that every graph we run Kruskal's algorithm on has size \(O(len)\), and hence that each level takes \(O(n\log n)\) time.

The time complexity is \(T(n)=T(\lfloor \frac{n}{2} \rfloor)+T(\lceil \frac{n}{2} \rceil)+ O(n\log n)=O(n\log^2n)\).

The implementation can be a little tricky. Note that the disjoint set union must not use path compression, or it will no longer support rollback. There is also no need to actually carry out the contraction: the Kruskal run at each level can simply work in the disjoint set union of the level above.

Example code
  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
#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
using ll = long long;
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) {  // with rollback
    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  // static 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;
};  // dynamic edge

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

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

void pushdown(int dep)  // contract edges
{
  tr.clear();  // make a copy here, or the operations cannot be rolled back
  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++) {  // useless edges
    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++) {  // mandatory edges
    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++) {  // contract edges
    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) {  // base case
    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++) {  // dynamic to static
    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++) {  // queries to dynamic
    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);  // what follows is the rollback
  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++) {  // dynamic to static
    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++) {  // queries to dynamic
    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;  // turn time back to the level above
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m >> ask;
  s.ih();
  s1.ih();
  for (int i = 1; i <= m; i++) {
    cin >> e[i].u >> e[i].v >> e[i].val;
  }
  for (int i = 1; i <= ask; i++) {
    cin >> q[i].num >> q[i].val;
  }
  for (int i = 1; i <= ask; i++) {  // initial dynamic edges
    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++) {  // initial static edges
    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++) {
    cout << q[i].ans << '\n';
  }
  return 0;
}

References and notes