CDQ 分治

本文转载（或修改）自 OI-Wiki

引入

CDQ 分治是一种思想而不是具体的算法。目前这个思想的拓展十分广泛，依原理与写法的不同，大致分为三类：

• 解决和点对有关的问题。
• 1D 动态规划的优化与转移。
• 通过 CDQ 分治，将一些动态问题转化为静态问题。

CDQ 分治的思想最早由 IOI2008 金牌得主陈丹琦在高中时整理并总结，它也因此得名。

解决和点对有关的问题

这类问题多数类似于「给定一个长度为 \(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) 来实现的。剩下的第二类点对则需要额外设计算法解决。

处理偏序问题

P3810 【模板】三维偏序（陌上花开）

有 \(n\) 个元素，第 \(i\) 个元素有 \(a_i,b_i,c_i\) 三个属性，设 \(f(i)\) 表示满足 \(a_j \leq a_i\) 且 \(b_j \leq b_i\) 且 \(c_j \leq c_i\) 且 \(j \ne i\) 的 \(j\) 的数量。

对于 \(d \in [0, n)\)，求 \(f(i) = d\) 的数量。

\(1 \leq n \leq 10^5\)， \(1 \leq a_i, b_i, c_i \le k \leq 2 \times 10^5\)。

三维偏序是 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)\)。

关于代码中的 inplace_merge

inplace_merge 是 STL 中的归并函数，用于将两个有序序列合并。

函数声明：

void inplace_merge(Node* first, Node* middle, Node* last, function<bool(Node, Node)> comp = less<Node>);

将迭代器 [first, middle) 与 [middle, last) 中的两个有序序列原地合并，按 comp 比较，默认从小到大。

因此甚至可以这样写归并排序：

inplace_merge版本的归并排序

void merge_sort(int *arr, int l, int r)
{
    if (l >= r)
        return;
    int mid = (l + r) >> 1;
    merge_sort(arr, l, mid);
    merge_sort(arr, mid + 1, r);
    inplace_merge(arr + l, arr + mid + 1, arr + r + 1);
    return;
}

实现

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXM = 1e6 + 5;
int n, k, m, tot;
struct BIT
{
    int bit[MAXN];
    inline int lowbit(int x) { return x & (-x); }
    inline void add(int x, int d)
    {
        for (; x <= k; x += lowbit(x)) bit[x] += d;
    }
    inline int query(int x)
    {
        int res = 0;
        for (; x; x -= lowbit(x)) res += bit[x];
        return res;
    }
} bit;
struct Node
{
    int a, b, c, cnt, ans;
} ss[MAXN], s[MAXN];
int ans[MAXN];
bool cmpA(Node a, Node b)
{
    if (a.a == b.a) return a.b == b.b ? a.c < b.c : a.b < b.b;
    return a.a < b.a;
}
bool cmpB(Node a, Node b) { return a.b == b.b ? a.c < b.c : a.b < b.b; }
void cdq(int l, int r)
{
    if (l >= r) return;
    int mid = l + r >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);
    int i, j = l;
    for (i = mid + 1; i <= r; i++)
    {
        while (s[i].b >= s[j].b && j <= mid)
        {
            bit.add(s[j].c, s[j].cnt);
            j++;
        }
        s[i].ans += bit.query(s[i].c);
    }
    for (i = l; i < j; i++) bit.add(s[i].c, -s[i].cnt);
    inplace_merge(s + l, s + mid + 1, s + r + 1, cmpB);
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> ss[i].a >> ss[i].b >> ss[i].c;
    sort(ss + 1, ss + n + 1, cmpA);
    for (int i = 1; i <= n; i++)
    {
        tot++;
        if (i == n || ss[i].a != ss[i + 1].a || ss[i].b != ss[i + 1].b ||
            ss[i].c != ss[i + 1].c)
        {
            s[++m] = ss[i];
            s[m].cnt = tot;
            tot = 0;
        }
    }
    cdq(1, m);
    for (int i = 1; i <= m; i++) ans[s[i].cnt + s[i].ans - 1] += s[i].cnt;
    for (int i = 0; i < n; i++) cout << ans[i] << '\n';
    return 0;
}

优化1D/1D类dp

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 分治的递归树如下所示。

执行刚才的算法流程的话，以 \(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 值，只是转移顺序被拆开了而已，所以算法是正确的。

P2487 [SDOI2011] 拦截导弹

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度、并且能够拦截任意速度的导弹，但是以后每一发炮弹都不能高于前一发的高度，其拦截的导弹的飞行速度也不能大于前一发。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

在不能拦截所有的导弹的情况下，我们当然要选择使国家损失最小、也就是拦截导弹的数量最多的方案。但是拦截导弹数量的最多的方案有可能有多个，如果有多个最优方案，那么我们会随机选取一个作为最终的拦截导弹行动蓝图。

我方间谍已经获取了所有敌军导弹的高度和速度，你的任务是计算出在执行上述决策时，每枚导弹被拦截掉的概率。

保证总方案数不超过 C++ 中 double 类型的存储范围。

• 对于 \(100\%\) 的数据，\(1\le n\le 5\times 10^4\)， \(1\le h_i,v_i\le 10^9\)。

对于每个测试点，若输出的第一行与标准输出相同，则得到该测试点 \(40\%\) 的分数，若输出文件的第二行的每个数与标准输出的误差均不大于 \(10^{-4}\)，则得到该测试点 \(60\%\) 的分数，两项相加作为该测试点总得分。

这题有高度还有速度，也就是一个三维问题（分别是高度，速度，时间即输入顺序，下面会分别用 \(x,y,z\) 表示这三维）。我们考虑借鉴只有二维时的思路。

这一道题的第一问其实就是让我们求多了一维限制的最长不上升子序列。而第二问是求每枚导弹被拦截掉的概率，即每枚导弹在所有最长不上升子序列方案里的出现次数/总最长不上升子序列方案数。

我们可以比较套路地定义一下dp：

• \(dp_1\) ：表示以第 \(i\) 枚导弹为结尾的方案中的最长不上升子序列长度。
• \(dp_2\) ：表示以第 \(i\) 枚导弹为开头的方案中的最长不上升子序列长度。
• \(f_1\) ：表示以第 \(i\) 枚导弹为结尾的最长不上升子序列方案总数。
• \(f_2\) ：表示以第 \(i\) 枚导弹为开头的最长不上升子序列方案总数。

第一问的答案即 \(\max\{dp_{1,i}\}\) 或者 \(\max\{dp_{2,i}\}\)。

第二问第 \(i\) 枚导弹的答案即 \(f_{1,i} * f_{2,i}\)（乘法原理），且 \(dp_{1,i} + dp_{2,i} = \text{ans} - 1\)， \(ans\) 为第一问答案，减 \(1\) 是因 \(i\) 导弹被计算了两次。

故只要解决dp即可处理这个问题，显然 \(O(n^2)\) 的dp类比导弹拦截能很容易得出。

实现

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50005;
struct node
{
    int x, y, z;
    int dp;
    double f;
} a[MAXN];
int n;
int tr1[MAXN];
double tr2[MAXN];
int dp1[MAXN], dp2[MAXN];
double f1[MAXN], f2[MAXN];
bool cmp1(node i, node j)
{
    return i.x == j.x ? (i.y == j.y ? i.z < j.z : i.y > j.y) : i.x > j.x;
}
bool cmp2(node i, node j)
{
    return i.x == j.x ? (i.y == j.y ? i.z < j.z : i.y < j.y) : i.x < j.x;
}
bool cmp3(node i, node j)
{
    return i.y > j.y;
}
bool cmp4(node i, node j)
{
    return i.y < j.y;
}
int lowbit(int x)
{
    return x & -x;
}
void update(int x, int dp, double f)
{
    while (x <= n)
    {
        if (tr1[x] < dp)
        {
            tr1[x] = dp;
            tr2[x] = f;
        }
        else if (tr1[x] == dp)
            tr2[x] += f;
        x += lowbit(x);
    }
    return;
}
int query1(int x)
{
    int ans = 0;
    while (x)
    {
        ans = max(ans, tr1[x]);
        x -= lowbit(x);
    }
    return ans;
}
double query2(int x, int dp)
{
    double ans = 0;
    while (x)
    {
        if (tr1[x] == dp)
            ans += tr2[x];
        x -= lowbit(x);
    }
    return ans;
}
void del(int x)
{
    while (x <= n)
    {
        tr1[x] = tr2[x] = 0;
        x += lowbit(x);
    }
    return;
}
bool check(int p, int q, int opt)
{
    if (opt == 1)
        return a[p].y >= a[q].y;
    return a[p].y <= a[q].y;
}
void merge_sort(int l, int r, int opt)
{
    int mid = (l + r) >> 1;
    int p = l, q = mid + 1;
    while (p <= mid && q <= r)
    {
        if (check(p, q, opt))
        {
            update(a[p].z, a[p].dp, a[p].f);
            p++;
        }
        else
        {
            int val = query1(a[q].z) + 1;
            if (a[q].dp < val)
            {
                a[q].dp = val;
                a[q].f = query2(a[q].z, val - 1);
            }
            else if (a[q].dp == val)
                a[q].f += query2(a[q].z, val - 1);
            q++;
        }
    }
    while (q <= r)
    {
        int val = query1(a[q].z) + 1;
        if (a[q].dp < val)
        {
            a[q].dp = val;
            a[q].f = query2(a[q].z, val - 1);
        }
        else if (a[q].dp == val)
            a[q].f += query2(a[q].z, val - 1);
        q++;
    }
    for (int i = l; i < p; i++)
        del(a[i].z);
    return;
}
void solve(int l, int r, int opt)
{
    if (l == r)
        return;
    int mid = l + ((r - l) >> 1);
    solve(l, mid, opt);
    if (opt == 1)
    {
        sort(a + l, a + mid + 1, cmp3);
        sort(a + mid + 1, a + r + 1, cmp3);
    }
    else
    {
        sort(a + l, a + mid + 1, cmp4);
        sort(a + mid + 1, a + r + 1, cmp4);
    }
    merge_sort(l, r, opt);
    if (opt == 1)
        sort(a + mid + 1, a + r + 1, cmp1);
    else
        sort(a + mid + 1, a + r + 1, cmp2);
    solve(mid + 1, r, opt);
    return;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].x >> a[i].y;
        a[i].z = i;
        a[i].dp = 1;
        a[i].f = 1;
    }
    sort(a + 1, a + n + 1, cmp1);
    solve(1, n, 1);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        dp1[a[i].z] = a[i].dp;
        f1[a[i].z] = a[i].f;
        ans = max(ans, dp1[a[i].z]);
    }
    cout << ans << endl;
    for (int i = 1; i <= n; i++)
    {
        a[i].z = n - a[i].z + 1;
        a[i].dp = 1;
        a[i].f = 1;
    }
    sort(a + 1, a + n + 1, cmp2);
    solve(1, n, 2);
    double k = 0;
    for (int i = 1; i <= n; i++)
    {
        dp2[n - a[i].z + 1] = a[i].dp;
        f2[n - a[i].z + 1] = a[i].f;
        if (dp2[n - a[i].z + 1] == ans)
            k += f2[n - a[i].z + 1];
    }
    cout << fixed << setprecision(5);
    for (int i = 1; i <= n; i++)
    {
        if (dp1[i] + dp2[i] == ans + 1)
            cout << f1[i] * f2[i] / k << ' ';
        else
            cout << 0 << " ";
    }
    return 0;
}

P4093 [HEOI2016/TJOI2016] 序列

佳媛姐姐过生日的时候，她的小伙伴从某宝上买了一个有趣的玩具送给他。

玩具上有一个数列，数列中某些项的值可能会变化，但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性，她想请教你，能否选出一个子序列，使得在任意一种变化和原序列中，这个子序列都是不降的？请你告诉她这个子序列的最长长度即可。

对于 \(100\%\) 数据，所有数字均为正整数，且小于等于 \(10^5\)。 \(1\le x\le n\)。

记 \(f_i\) 为以第 \(i\) 项结尾的子序列最长长度。

则有转移： \(f_i = \max_{j < i}\{f_j\} + 1\)，同时还要满足 \(\text{maxval}_j \leq a_i\) 和 \(a_j \leq \text{minval}_i\)。其中 \(\text{maxval}_i\) 表示第 \(i\) 项最大能变成的值，\(\text{minval}_i\) 表示第 \(i\) 项最小能变成的值。

按照项从小到大转移，形成了天然的时间顺序，同时还要满足两个偏序限制。算上时间顺序，这是一个三维偏序问题，用 CDQ 分治 + 数据结构（用了树状数组）就能解决。

实现

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10, inf = 0x7fffffff, MAXV = 1e5 + 10;
struct node
{
    int mx, mn, val, pos;
} a[MAXN];
namespace bit
{
    int tr[MAXV];
    inline int lowbit(int x) { return x & (-x); }
    inline void update(int x, int val)
    {
        while (x <= 1e5)
        {
            tr[x] = max(tr[x], val);
            x += lowbit(x);
        }
    }
    inline int query(int x)
    {
        int res = 0;
        while (x)
        {
            res = max(res, tr[x]);
            x -= lowbit(x);
        }
        return res;
    }
    inline void clear(int x)
    {
        while (x <= 1e5)
        {
            tr[x] = 0;
            x += lowbit(x);
        }
    }
} // namespace bit
int dp[MAXN], n, m, ans;
void cdq(int l, int r)
{
    if (l >= r)
    {
        dp[l] = max(dp[l], 1);
        return;
    }
    int mid = (l + r) >> 1;
    sort(a + l, a + r + 1, [](node p, node q)
         { return p.pos < q.pos; });
    cdq(l, mid);
    sort(a + l, a + mid + 1, [](node p, node q)
         { return p.mx < q.mx; });
    sort(a + mid + 1, a + r + 1, [](node p, node q)
         { return p.val < q.val; });
    int i = l, j;
    // a[i].mx <= a[j].val && a[i].val <= a[j].mn
    for (j = mid + 1; j <= r; j++)
    {
        while (a[i].mx <= a[j].val && i <= mid)
        {
            bit::update(a[i].val, dp[a[i].pos]);
            i++;
        }
        dp[a[j].pos] = max(dp[a[j].pos], bit::query(a[j].mn) + 1);
    }
    while (i >= l)
        bit::clear(a[i--].val);
    cdq(mid + 1, r);
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i].val, a[i].mx = a[i].mn = a[i].val, a[i].pos = i;
    while (m--)
    {
        int x, y;
        cin >> x >> y;
        a[x].mn = min(a[x].mn, y);
        a[x].mx = max(a[x].mx, y);
    }
    cdq(1, n);
    for (int i = 1; i <= n; i++)
        ans = max(ans, dp[i]);
    cout << ans;
    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)+(\lceil \frac{n}{2} \rceil)+ O(n\log n)=O(n\log^2n)\)。

观察上述的算法流程，我们发现一开始我们只能解决静态的矩形加矩形求和问题，但只是简单地使用 CDQ 分治后，我们就可以离线地解决一个动态的矩形加矩形求和问题了。将动态问题转化为静态问题的精髓就在于 CDQ 分治每次仅仅处理跨越某一个点的修改和询问关系，这样的话我们就只需要考虑「所有询问都在修改之后」这个简单的问题了。也正是因为这一点，CDQ 分治被称为「动态问题转化为静态问题的工具」。

以下是这个模型的模板题：

P4390 [BalkanOI 2007] Mokia 摩基亚

摩尔瓦多的移动电话公司摩基亚（Mokia）设计出了一种新的用户定位系统。和其他的定位系统一样，它能够迅速回答任何形如 “用户 C 的位置在哪？” 的问题，精确到毫米。但其真正高科技之处在于，它能够回答形如 “给定区域内有多少名用户？” 的问题。

在定位系统中，世界被认为是一个 \(w\times w\) 的正方形区域，由 \(1\times 1\) 的方格组成。每个方格都有一个坐标 \((x, y)\)， \(1\leq x,y\leq w\)。坐标的编号从 \(1\) 开始。对于一个 \(4\times 4\) 的正方形，就有 \(1\leq x\leq 4\)， \(1\leq y\leq 4\)（如图）：

请帮助 Mokia 公司编写一个程序来计算在某个矩形区域内有多少名用户。

有三种命令，意义如下：

命令	参数	意义
\(0\)	\(w\)	初始化一个全零矩阵。本命令仅开始时出现一次。
\(1\)	\(x\ y\ a\)	向方格 \((x, y)\) 中添加 \(a\) 个用户。\(a\) 是正整数。
\(2\)	\(x_1\ y_1\ x_2\ y_2\)	查询 \(x_1\leq x\leq x_2\)， \(y_1\leq y\leq y_2\) 所规定的矩形中的用户数量。
\(3\)	无参数	结束程序。本命令仅结束时出现一次。

对于 \(100\%\) 的数据，保证：

• \(1\leq w\leq 2\times 10 ^ 6\)。
• \(1\leq x_1\leq x_2\leq w\)， \(1\leq y_1\leq y_2\leq w\)， \(1\leq x,y\leq w\)， \(0<a\leq 10000\)。
• 命令 \(1\) 不超过 \(160000\) 个。
• 命令 \(2\) 不超过 \(10000\) 个。

我们把 \([x_1, x_2] * [y_1, y_2]\) 查询拆成 \([0, x_2] * [0, y_2] + [0, x_1 - 1] * [0, y_1 - 1] - [0, x_2 - 1] * [0, y_1] - [0, x_1 - 1] * [0, y_2]\) 就行了。

还要注意一点，树状数组不能操作 \(0\) 的下标，我们把所有下标 \(+1\) 就行了。

然后就没有了。

实现

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int MAXN = 2e6 + 10;
ll n, m, ans[MAXN], M;
int ops[MAXN];
struct BIT
{
    int lowbit(const int x) { return x & (-x); }
    ll tr[MAXN];
    void add(int x, ll v)
    {
        for (x++; x <= n + 1; x += lowbit(x)) tr[x] += v;
    }
    void del(int x)
    {
        for (x++; x <= n + 1; x += lowbit(x)) tr[x] = 0;
    }
    ll qry(int x)
    {
        ll res = 0;
        for (x++; x; x -= lowbit(x)) res += tr[x];
        return res;
    }
} bit;
struct node
{
    // opt == 0: add a, opt == 1 or -1: ans[tim] += qry * opt
    ll opt, tim, x, y, a;
} a[MAXN];
void solve(int l, int r) // solve tim in [l, r] and sort array a[] by x
{
    if (l == r) return;
    int mid = (l + r) >> 1;
    solve(l, mid), solve(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r)
    {
        if (a[i].x <= a[j].x)
        {
            if (!a[i].opt) bit.add(a[i].y, a[i].a);
            i++;
        }
        else
        {
            if (a[j].opt) ans[a[j].tim] += a[j].opt * bit.qry(a[j].y);
            j++;
        }
    }
    while (j <= r)
    {
        if (a[j].opt) ans[a[j].tim] += a[j].opt * bit.qry(a[j].y);
        j++;
    }
    for (int t = l; t < i; t++)
        if (!a[t].opt) bit.del(a[t].y);
    inplace_merge(a + l, a + mid + 1, a + r + 1,
                  [](node p, node q)
                  { return p.x <= q.x; });
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> n;
    for (ll &i = M = 1, x1, y1, x2, y2, x, y, v, opt;; i++)
    {
        cin >> opt;
        ops[i] = opt;
        if (opt == 3)
        {
            i--;
            break;
        }
        switch (opt)
        {
        case 1:
            cin >> x >> y >> v;
            a[++m] = {0, i, x, y, v};
            break;
        case 2:
            cin >> x1 >> y1 >> x2 >> y2;
            a[++m] = {1, i, x1 - 1, y1 - 1, 0};
            a[++m] = {1, i, x2, y2, 0};
            a[++m] = {-1, i, x1 - 1, y2, 0};
            a[++m] = {-1, i, x2, y1 - 1, 0};
            break;
        }
    }
    solve(1, m);
    for (int i = 1; i <= M; i++)
        if (ops[i] == 2) cout << ans[i] << endl;
    return 0;
}

P5445 [APIO2019] 路灯

一辆自动驾驶的出租车正在 Innopolis 的街道上行驶。该街道上有 \(n+1\) 个停车站点，它们将街道划分成了 \(n\) 条路段。每一路段都拥有一个路灯。当第 \(i\) 个路灯亮起，它将照亮连接第 \(i\) 与第 \(i+1\) 个站点的路段。否则这条路段将是黑暗的。

安全起见，出租车只能在被照亮的路段上行驶。换言之，出租车能从站点 \(a\) 出发到达站点 \(b (a<b)\) 的条件是：连接站点 \(a\) 与 \(a+1\)， \(a + 1\) 与 \(a+2\)，……， \(b-1\) 与 \(b\) 的路段都被照亮。

在经过一些意外故障或修理之后，街道上的路灯可能是亮起的，也可能是熄灭的。

现在给定 \(0\) 时刻时，街道上路灯的初始状态。之后 \(1,2,\ldots,q\) 时刻，每时刻会发生下列两种事件之一：

• \(\text{toggle} \ i\) ：切换第 \(i\) 个路灯的状态。具体地说，若路灯原来亮起，则现在将熄灭；若路灯原来熄灭，则现在将亮起。

• \(\text{query} \ a \ b\) ：出租车部门的负责人想知道，从 \(0\) 时刻起到当前时刻，有多少个时刻满足：出租车能够从站点 \(a\) 出发到达站点 \(b\)。

请你帮助出租车部门的负责人回答他们的问题。

对于全部数据，\(1 \leq n,q \leq 3\times 10^5\)， \(|s|=n\)， \(1 \leq i \leq n\)， \(1 \leq a < b \leq n+1\)。

考虑把询问看成平面上的一个点，坐标为 \((a, b)\)。

每个坐标 \((x, y)\) 的值表示到当前 \(x\) 和 \(y\) 联通的时间和。

考虑一个修改的贡献，它其实就是把左边一段区间 \([l, x]\) 和右边一段区间 \([x+1, r]\) 联通或断开。

放到平面上发现其实就是横坐标在 \([l, x]\)，纵坐标在 \([x+1, r]\) 的矩形里修改，那么矩形左下角为 \([l, x+1]\)，右上角为 \([x, r]\)。

如果每个时间点都把相应矩形 \(+1\) 的话显然是不可行的，考虑起点和终点的时间差。

如果当前操作是联通，设当前时间为 \(t\)，则把相应矩形 \(-t\)，如果是断开则把矩形加 \(t\)。

这样我们询问时直接矩形单点查值即可，但是要注意，如果查询时当前区间仍然联通，那么对应矩形还没加 \(t\)，我们查完值以后答案还要再加 \(t\)。

矩形加具体就是差分成四个前缀修改，查询的时候直接查左下所有位置的和即可。

如果把左下角为 \((xa, ya)\)，右上角 \((xb, yb)\) 的闭区间都加一个 \(v\)，那么其实就是把 \((0,0),(xa, ya)\) 加一个 \(v\)， \((0,0),(xa, yb+1)\) 减 \(v\)， \((0,0),(xb+1, ya)\) 减 \(v\)， \((0,0),(xb+1, yb+1)\) 加 \(v\)。

二维平面加一维时间轴，CDQ 分治即可。

这里我们使用 set 维护连续颜色段，这个技术叫做珂朵莉树（ODT）。

实现

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 6e5 + 10;
typedef long long ll;
#define endl '\n'
string s;
int n, q, tot;
struct line
{
    int l, r;
    line(int a = 0, int b = 0) : l(a), r(b) {}
    inline bool operator<(const line &tmp) const { return l < tmp.l; }
};
set<line> odt;
set<line>::iterator ita, itb;
struct node
{
    int x, y, id, v;
    node(int a = 0, int b = 0, int c = 0, int d = 0) : x(a), y(b), id(c), v(d) {}
} d[MAXN << 2];
int t[MAXN];
inline int lowbit(const int x) { return x & (-x); }
inline void add(int x, int v)
{
    while (x <= n + 1) t[x] += v, x += lowbit(x);
}
inline int ask(int x)
{
    int res = 0;
    while (x) res += t[x], x -= lowbit(x);
    return res;
}
inline bool cmp(node a, node b)
{
    if (a.x != b.x) return a.x < b.x;
    return a.y != b.y ? a.y < b.y : a.id < b.id;
}
int ans[MAXN];
void solve(int l, int r)
{
    if (l == r) return;
    int mid = (l + r) >> 1;
    solve(l, mid);
    solve(mid + 1, r);
    int i = l, j = mid + 1, p = l - 1;
    while (i <= mid && j <= r)
    {
        if (cmp(d[i], d[j]))
        {
            if (!d[i].id) add(d[i].y, d[i].v);
            i++;
            continue;
        }
        if (d[j].id) ans[d[j].id] += ask(d[j].y);
        j++;
    }
    for (; j <= r; j++)
        if (d[j].id) ans[d[j].id] += ask(d[j].y);
    for (int k = l; k < i; k++)
        if (!d[k].id) add(d[k].y, -d[k].v);
    inplace_merge(d + l, d + mid + 1, d + r + 1, cmp);
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> q;
    cin >> s;
    s = " " + s;
    odt.insert(line(0, 0));
    odt.insert(line(n + 1, n + 1));
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == '0') continue;
        int R = i;
        while (s[R + 1] == '1') R++;
        odt.insert(line(i, R));
        i = R;
    }
    string ch;
    int a, b, cnt = 0;
    for (int i = 1; i <= q; i++)
    {
        cin >> ch >> a;
        if (ch[0] == 'q')
        {
            cin >> b;
            d[++tot] = node(a, b, ++cnt, 0);
            ita = prev(odt.lower_bound(line(a + 1, 0)));
            itb = prev(odt.lower_bound(line(b, 0)));
            if (ita == itb && ita->r >= b - 1) ans[cnt] += i;
            continue;
        }
        if (s[a] == '0')
        {
            ita = odt.lower_bound(line(a + 1, 0));
            itb = prev(ita);
            line A = (*ita), B = (*itb);
            int l = a, r = a;
            if (B.r == l - 1 && B.l >= 1) l = B.l, odt.erase(B);
            if (A.l == r + 1 && A.r <= n) r = A.r, odt.erase(A);
            odt.insert(line(l, r));
            d[++tot] = node(l, a + 1, 0, -i);
            d[++tot] = node(a + 1, r + 2, 0, -i);
            d[++tot] = node(l, r + 2, 0, i);
            d[++tot] = node(a + 1, a, 0, i);
            s[a] = '1';
            continue;
        }
        ita = prev(odt.lower_bound(line(a + 1, 0)));
        line A = (*ita);
        odt.erase(A);
        if (A.l < a) odt.insert(line(A.l, a - 1));
        if (A.r > a) odt.insert(line(a + 1, A.r));
        d[++tot] = node(A.l, a + 1, 0, i);
        d[++tot] = node(a + 1, A.r + 2, 0, i);
        d[++tot] = node(A.l, A.r + 2, 0, -i);
        d[++tot] = node(a + 1, a, 0, -i);
        s[a] = '0';
    }
    solve(1, tot);
    for (int i = 1; i <= cnt; i++) cout << ans[i] << endl;
    return 0;
}