NOI 一轮复习：分治

分治是将复杂的问题拆成多个（一般是两个）相似的子问题，直到最后分成的子问题可以简单求解，然后通过子问题的答案合并出大问题的答案。

仿照分治的结构可以衍生出一大堆静态分治算法。

普通分治

[uoj979] 决战库尔斯克

Portal.

首先排序去重。如果选择钦定最小值，发现需要枚举最小值的倍数然后在一段中二分出最大值，但是值域很大，寄了。

那么钦定最大值，最小值可以选择严格比其一半大的，那么答案是差。假定最小的严格比一半大的是 $a_{mid}$ 。

考虑小于的部分对大于的部分的影响，枚举小数 $a_i$ ，发现需要 $a_i - 1 > a_r - a_{mid}$ ，这样就只有至多两段 $a_i$ 的倍数了，直接二分。

于是递归下去即可， $O(n\log V\log n)$ ，两个 log 都跑不满。代码。

* [CF1442D] Sum

Portal.

给定 $n$ 个不降的数组。有一个值 $ans$ ，初始为 $0$ 。你需要进行如下操作 $k$ 次：

选择一个数组，把 $ans$ 加上数组的第一个元素，之后把它删除。

请求出 $ans$ 最大是多少。所有数组的元素总个数 $\leq 10^6$ ， $n,k\leq 3000$ 。

注意到数组是单调不降的，因此要取一个数组就会一直取下去直到不能取或者取光了。

所以可以想到一个暴力一点的做法：将一个数组视为一个有体积有价值的物品，然后正反做两遍 01 背包，枚举没取满的那个数组和这个数组取多少个，再枚举前面取的体积，这样就可以得出后面取的体积，并计算出总价值，时间复杂度为 $O(nk^2)$ 。

这样肯定过不去，发现就是合并太慢了，考虑使用分治算法合并：求解 $(l,r)$ 时，我们先将 $(l,mid)$ 加入背包，然后递归求解 $(mid+1,r)$ ，当 $l=r$ 时就可以枚举当前体积了。时间复杂度 $O(nk\log n)$ 。

这个问题被称为缺一背包，意思是其中有一个可以取不满，一般采用上述分治法解决。

int n, k;
vector<i64> a[3005];
i64 ans = 0, f[3005];

void merge(int l, int r) {
    if (l == r) {
        for (int i = 0; i <= min(k, (int)a[l].size() - 1); ++i)
            ans = max(ans, a[l][i] + f[k - i]);
        return;
    }
    int mid = l + r >> 1;
    i64 g[3005];
    memcpy(g, f, sizeof(g));
    for (int i = mid + 1; i <= r; ++i)
        for (int j = k; j >= a[i].size() - 1; --j)
            f[j] = max(f[j], f[j - a[i].size() + 1] + a[i][a[i].size() - 1]);
    merge(l, mid);
    memcpy(f, g, sizeof(f));
    for (int i = l; i <= mid; ++i)
        for (int j = k; j >= a[i].size() - 1; --j)
            f[j] = max(f[j], f[j - a[i].size() + 1] + a[i][a[i].size() - 1]);
    merge(mid + 1, r);
}

int main(void) {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        int m; scanf("%d", &m); a[i].resize(m + 1);
        for (int j = 1, x; j <= m; ++j) scanf("%lld", &a[i][j]), a[i][j] += a[i][j - 1];
    }
    merge(1, n); printf("%lld\n", ans);
    return 0;
}

二维分治

其实就是对两个东西进行分治，每次将其中一个东西切半（为了保证效率，一般选择其中区间更长的一个切半），然后合并答案。

[CF364E] Empty Rectangles.

给定一个 $n\times m(1\le n, m\le 2.5\times 10^3)$ 的 01 矩阵，询问有多少个子矩阵满足只有 $k(1\le k\le 6)$ 个 1。

本题要求恰好有 $k$ 个 1 的子矩形数量，我们将当前矩形劈成两半（以劈成左一半和右一半为例），那么符合条件的子矩形要么在左半，要么在右半，要么跨越中线。

考虑跨越中线的如何合并。我们枚举子矩形的上下边界，然后开个桶 $p$ 统计左半矩形所含 $1$ 数量小于 $i$ 时左边界的最小值（右半矩形同理），然后直接枚举左半边的 $1$ 的个数就可以统计了。代码。

CDQ 分治

树套树的本质作用是降维，但是如果允许离线，则可以使用 CDQ 分治高效地完成这个问题。

最重要的应用是解决三维偏序问题。分别处理三个信息。第一维可以将原数组按照 $x$ 排序， $x_i\le x_j$ 转化为 $i<j$ 。注意此时如果数都相同会出问题，因此去个重。第二维可以在分治时采用类似于归并排序的方式解决（求正序对），不过由于第三维的限制，并不是所有的信息都可以加到答案里的，需要整一个权值树状数组来处理第三维的信息：左半段序列的信息加入树状数组，右半段信息进行统计。代码。

CDQ 分治的写法非常灵活，像三维偏序问题是对分治树进行后序遍历来统计答案的。对于一些 DP 问题，往往可以在中序遍历时统计前面一半对后面一半的影响。

例题

这里选择一些比较有代表性的问题。

【模板】离线静态四维数点

Portal.

四维偏序模板题。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;

int n, m, lsh[N * 2], C[N * 2], ans[N];
struct Node {
    int a, b, c, d, id, op;
    bool operator< (const Node a) const {
        if (this->a != a.a) return this->a < a.a;
        return id < a.id;
    }
} a[N * 2], b[N * 2], T[N * 2];
inline void add(int x, int k) { for (; x <= n; x += x & -x) C[x] += k; }
inline int sum(int x) { int r = 0; for (; x; x -= x & -x) r += C[x]; return r; }

void cdq2(int l, int r) {
    if (l == r) return; int mid = l + r >> 1;
    cdq2(l, mid); cdq2(mid + 1, r);
    for (int i = l, p = l, q = mid + 1; i <= r; ++i) {
        if (p <= mid && (q > r || b[p].c <= b[q].c)) {
            if (b[p].op == 0 && b[p].id == 0) add(b[p].d, 1);
            ++p;
        } else {
            if (b[q].op == 1 && b[q].id) ans[b[q].id] += sum(b[q].d);
            ++q;
        }
    }
    for (int i = l; i <= mid; ++i) if (b[i].op == 0 && b[i].id == 0) add(b[i].d, -1);
    merge(b + l, b + mid + 1, b + mid + 1, b + r + 1, T + l, [](Node x, Node y) { return x.c != y.c ? x.c < y.c : x.id < y.id; });
    for (int i = l; i <= r; ++i) b[i] = T[i];
    // sort(b + l, b + r + 1, [](Node x, Node y) { return x.c != y.c ? x.c < y.c : x.id < y.id; });
}
void cdq(int l, int r) {
    if (l == r) return; int mid = l + r >> 1;
    cdq(l, mid); cdq(mid + 1, r);
    for (int i = l; i <= mid; ++i) a[i].op = 0; // a 小的左半部分产生贡献
    for (int i = mid + 1; i <= r; ++i) a[i].op = 1; // a 大的右半部分计算答案
    
    merge(a + l, a + mid + 1, a + mid + 1, a + r + 1, T + l, [](Node x, Node y) { return x.b != y.b ? x.b < y.b : x.id < y.id; }); // 按照 b 排序，进行 CDQ 分治计算答案
    for (int i = l; i <= r; ++i) a[i] = b[i] = T[i];

    // sort(a + l, a + r + 1, [](Node x, Node y) { return x.b != y.b ? x.b < y.b : x.id < y.id; });
    // for (int i = l; i <= r; ++i) b[i] = a[i];

    cdq2(l, r);
}

int main(void) {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n + m; ++i) {
        cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d; a[i].c *= -1; a[i].d *= -1; lsh[i] = a[i].d;
        if (i > n) a[i].id = i - n;
    }
    n += m; sort(a + 1, a + n + 1); sort(lsh + 1, lsh + n + 1);
    for (int i = 1; i <= n; ++i) a[i].d = lower_bound(lsh + 1, lsh + n + 1, a[i].d) - lsh;
    cdq(1, n);
    for (int i = 1; i <= m; ++i) cout << ans[i] << '\n';
    return 0;
}