Part 1: CDQ Divide and Conquer

CDQ divide and conquer is primarily used to solve 3D partial order problems, where we need to count valid pairs of elements satisfying three specified attribute constraints. For example, given elements with attributes (a_i, b_i, c_i), we might calculate how many j satisfy a_j ≤ a_i, b_j ≤ b_i, and c_j ≤ c_i for each i.

3D Partial Order Template (Blooming Flowers)

This classic problem asks for f(i), the number of j≠i where a_j ≤ a_i, b_j ≤ b_i, c_j ≤ c_i, and counts how many time each f(i) occurs.

Key Steps:

1. Sort by a: Fix the first dimension.
2. CDQ Recursion: Split the aray into left and right halves, solve each recursively.
3. Merge and Count: For the left half contributing to the right half:
   • Sort both halves by b.
   • Use a Fenwick tree (BIT) to count valid c values efficient.

Code Template

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
struct Node {
    int a, b, c, count, ans;
} arr[N], temp[N];
int bit[N], ans[N];
int n, k;

int lowbit(int x) { return x & -x; }
void update(int idx, int val) {
    while (idx <= k) {
        bit[idx] += val;
        idx += lowbit(idx);
    }
}
int query(int idx) {
    int res = 0;
    while (idx > 0) {
        res += bit[idx];
        idx -= lowbit(idx);
    }
    return res;
}

bool compareA(const Node& x, const Node& 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 compareB(const Node& x, const Node& 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);
    sort(arr + l, arr + mid + 1, compareB);
    sort(arr + mid + 1, arr + r + 1, compareB);
    int i = l, j = mid + 1;
    while (j <= r) {
        while (i <= mid && arr[i].b <= arr[j].b) {
            update(arr[i].c, arr[i].count);
            i++;
        }
        arr[j].ans += query(arr[j].c);
        j++;
    }
    for (int x = l; x < i; x++) update(arr[x].c, -arr[x].count);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> temp[i].a >> temp[i].b >> temp[i].c;
    }
    sort(temp + 1, temp + n + 1, compareA);
    int m = 0;
    for (int i = 1; i <= n; i++) {
        int cnt = 1;
        while (i + 1 <= n && temp[i].a == temp[i + 1].a && temp[i].b == temp[i + 1].b && temp[i].c == temp[i + 1].c) {
            cnt++;
            i++;
        }
        arr[++m] = {temp[i].a, temp[i].b, temp[i].c, cnt, 0};
    }
    cdq(1, m);
    for (int i = 1; i <= m; i++) {
        ans[arr[i].ans + arr[i].count - 1] += arr[i].count;
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

Dynamic to Static with CDQ

CDQ can also convert dynamic problems into static ones by introducing a time dimension. For example, in the "Dynamic Inversion Count" problem:

• Treat each deletion as a time step.
• For an element to contribute to a query, it must be active (not deleted) at query time.

Part 2: Chtholly Tree

Chtholly Tree is an ad-hoc data structure optimized for random data with frequent interval assignment operations. It works by maintaining intervals of identical values.

Core Idea

1. Split: Split an interval to isolate a specific position.
2. Assign: Delete existing subintervals in [l, r] and insert a new interval with the value x.
3. Operations: Use set iterators to traverse and modify affected intervals.

Template Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node {
    int l, r;
    mutable ll v;
    Node(int L, int R = -1, ll V = 0) : l(L), r(R), v(V) {}
    bool operator<(const Node& rhs) const {
        return l < rhs.l;
    }
};
set<Node> s;

using It = set<Node>::iterator;
It split(int pos) {
    auto it = s.lower_bound(Node(pos));
    if (it != s.end() && it->l == pos) return it;
    --it;
    int L = it->l, R = it->r;
    ll V = it->v;
    s.erase(it);
    s.insert(Node(L, pos - 1, V));
    return s.insert(Node(pos, R, V)).first;
}

void assign(int l, int r, ll v) {
    auto itr = split(r + 1);
    auto itl = split(l);
    s.erase(itl, itr);
    s.insert(Node(l, r, v));
}

void add(int l, int r, ll x) {
    auto itr = split(r + 1);
    for (auto it = split(l); it != itr; ++it) {
        it->v += x;
    }
}

ll kth(int l, int r, int k) {
    auto itr = split(r + 1);
    vector<pair<ll, int>> vec;
    for (auto it = split(l); it != itr; ++it) {
        vec.emplace_back(it->v, it->r - it->l + 1);
    }
    sort(vec.begin(), vec.end());
    for (auto& p : vec) {
        if (k <= p.second) {
            return p.first;
        }
        k -= p.second;
    }
    return -1;
}

ll powmod(ll base, ll exp, ll mod) {
    ll res = 1;
    while (exp > 0) {
        if (exp % 2 == 1) res = res * base % mod;
        base = base * base % mod;
        exp /= 2;
    }
    return res;
}

ll sum_pow(int l, int r, int ex, int mod) {
    auto itr = split(r + 1);
    ll res = 0;
    for (auto it = split(l); it != itr; ++it) {
        ll cnt = it->r - it->l + 1;
        res = (res + powmod(it->v, ex, mod) * cnt) % mod;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, seed, vmax;
    cin >> n >> m >> seed >> vmax;
    s.insert(Node(n + 1, n + 1, 0));
    auto rnd = [&seed]() {
        ll ret = seed;
        seed = (seed * 7 + 13) % 1000000007;
        return ret;
    };
    for (int i = 1; i <= n; i++) {
        int val = (rnd() % vmax) + 1;
        s.insert(Node(i, i, val));
    }
    while (m--) {
        int op = (rnd() % 4) + 1;
        int l = (rnd() % n) + 1;
        int r = (rnd() % n) + 1;
        if (l > r) swap(l, r);
        if (op == 1) {
            ll x = (rnd() % vmax) + 1;
            add(l, r, x);
        } else if (op == 2) {
            ll x = (rnd() % vmax) + 1;
            assign(l, r, x);
        } else if (op == 3) {
            int k = (rnd() % (r - l + 1)) + 1;
            cout << kth(l, r, k) << '\n';
        } else {
            int x = (rnd() % vmax) + 1;
            int y = (rnd() % vmax) + 1;
            cout << sum_pow(l, r, x, y) << '\n';
        }
    }
    return 0;
}

Part 3: Range Color Counting

For static range color counting, a common approach uses a pre array, where pre[i] is the last index with the same color as i. A position i contributes to query [l, r] if pre[i] < l.

Static Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int a[N], pre[N], pos[N], tr[N];
struct Query {
    int l, r, id, val;
} q[N * 2];
int ans[N];
int n, m;

int lowbit(int x) { return x & -x; }
void update(int idx, int val) {
    while (idx <= n) {
        tr[idx] += val;
        idx += lowbit(idx);
    }
}
int query(int idx) {
    int res = 0;
    while (idx > 0) {
        res += tr[idx];
        idx -= lowbit(idx);
    }
    return res;
}

bool compare(const Query& x, const Query& y) {
    return x.r < y.r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    memset(pos, 0, sizeof(pos));
    for (int i = 1; i <= n; i++) {
        pre[i] = pos[a[i]];
        pos[a[i]] = i;
    }
    cin >> m;
    int cnt = 0;
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        q[++cnt] = {l - 1, r, i, -1};
        q[++cnt] = {l, r, i, 1};
    }
    sort(q + 1, q + cnt + 1, compare);
    int current = 1;
    for (int i = 1; i <= cnt; i++) {
        while (current <= q[i].r) {
            update(pre[current] + 1, 1);
            current++;
        }
        ans[q[i].id] += q[i].val * query(q[i].l);
    }
    for (int i = 1; i <= m; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}