分治杂记

分治（Divide and Conquer），就是把一个复杂的问题分成若干子问题，分别求解。本质是缩小了问题的规模。

普通的分治

[ABC373G] No Cross Matching

给定平面上的 \(n\) 个黑点和 \(n\) 个白点，构造一种方案，将黑白点两两匹配并连线段，使得任意两条线段不相交。

\(n \leq 100\) ，保证无三点共线，保证有解

找到最左下角的黑点，找到一个白点使得这两个点连线的两边内黑白点数量分别相等，然后分治即可。

找白点可以用极角排序，时间复杂度 \(O(n^2 \log n)\) 。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e2 + 7;

struct Point {
    int x, y, id;
} p[N << 1];

int match[N];

int n;

void solve(int l, int r) {
    if (l > r)
        return;

    sort(p + l, p + r + 1, [](const Point &a, const Point &b) { return a.x < b.x; });

    for (int i = l + 1; i <= r; ++i)
        p[i].x -= p[l].x, p[i].y -= p[l].y;

    sort(p + l + 1, p + r + 1, [](const Point &a, const Point &b) {
        return atan2(a.x, a.y) > atan2(b.x, b.y);
    });

    for (int i = l + 1, cnt = 0; i <= r; cnt += (p[i++].id <= n ? 1 : -1))
        if (!cnt && ((p[i].id <= n) ^ (p[l].id <= n))) {
            match[min(p[l].id, p[i].id)] = max(p[l].id, p[i].id);
            solve(l + 1, i - 1), solve(i + 1, r);
            return;
        }
}

signed main() {
    scanf("%d", &n);

    for (int i = 1; i <= n * 2; ++i)
        scanf("%d%d", &p[i].x, &p[i].y), p[i].id = i;

    solve(1, n * 2);

    for (int i = 1; i <= n; ++i)
        printf("%d ", match[i] - n);

    return 0;
}

一维点对

主要就是讨论点对分别在左右区间产生的贡献。

CF459D Pashmak and Parmida's problem

给定 \(a_{1 \sim n}\) ，设 \(f(l, r, x)\) 表示 \(x\) 在 \(a_{l \sim r}\) 中的出现次数。求有多少对 \(i < j\) 满足 \(f(1, i, a_i) > f(j, n, a_j)\) 。

\(n \leq 10^6\)

预处理 \(f(1, i, a_i)\) 和 \(f(i, n, a_i)\) 后就变为逆序对问题，可以归并做到 \(O(n \log n)\) ，比 DS 好写多了。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 7;

map<int, int> mp;

int a[N], pre[N], suf[N];

ll ans;
int n;

void solve(int l, int r) {
    if (l == r)
        return;

    int mid = (l + r) >> 1;
    solve(l, mid), solve(mid + 1, r);

    for (int i = l, j = mid; i <= mid; ++i) {
        while (j < r && pre[i] > suf[j + 1])
            ++j;

        ans += j - mid;
    }

    inplace_merge(pre + l, pre + mid + 1, pre + r + 1);
    inplace_merge(suf + l, suf + mid + 1, suf + r + 1);
}

signed main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i)
        scanf("%d", a + i), pre[i] = ++mp[a[i]];

    mp.clear();

    for (int i = n; i; --i)
        suf[i] = ++mp[a[i]];

    solve(1, n);
    printf("%lld", ans);
    return 0;
}

友好点对

给出二维平面上的 \(n\) 个不同点。若存在一个矩形只包含两个点（包括边界），则称这两个点为友好点对。求友好点对的数量。

\(n \leq 10^5\)

不难发现若两个点是友好点对，则最优的矩形一定是使得这两个点在对角线两端。

考虑按横坐标分治。以左下-右上为例，左上-右下是对称的。处理跨过中点的贡献时，固定左侧的某个点，则右侧能选择的点是一个上升序列。分别对左右区间维护单调栈即可。

P7883 平面最近点对（加强加强版）

给定 \(n\) 个二维平面上的点，求最近点对距离的平方值。

\(n \leq 4 \times 10^5\)

考虑按 \(x\) 坐标分治，记分治的分界线为 \(mid\) ，左右区间内部的最近点对距离的较小值为 \(d\) 。

考虑处理左右区间之间对答案的贡献，首先发现一个点 \((x, y)\) 满足 \(|x - mid| \leq d\) 时才有可能更新答案。将这些点拿出来，并按 \(y\) 坐标排序。对于其中的一个点 \((x, y)\) ，可能更新答案的点 \((x', y')\) 必然满足 \(|y - y'| \leq d\) ，那么只要找到附近满足该条件的点更新即可。直觉可以发现这样的点是常数级别的，不然内部就可以更新了。

时间复杂度 \(O(n \log n)\) 。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll inf = 1e18;
const int N = 4e5 + 7;

struct Point {
    int x, y;
} p[N], tmp[N];

int n;

inline ll dist(const Point &a, const Point &b) {
    return 1ll * (a.x - b.x) * (a.x - b.x) + 1ll * (a.y - b.y) * (a.y - b.y);
}

inline ll solve(int l, int r) {
    if (l == r)
        return inf;
        
    int mid = (l + r) >> 1, midx = p[mid].x;
    ll d = min(solve(l, mid), solve(mid + 1, r));
    inplace_merge(p + l, p + mid + 1, p + r + 1, 
        [](const Point &a, const Point &b) { return a.y < b.y; });
    int len = 0;
    
    for (int i = l; i <= r; ++i)
        if (1ll * (midx - p[i].x) * (midx - p[i].x) < d)
            tmp[++len] = p[i];
    
    for (int i = 1; i <= len; ++i)
        for (int j = i + 1; j <= len && 1ll * (tmp[j].y - tmp[i].y) * (tmp[j].y - tmp[i].y) < d; ++j)
            d = min(d, dist(tmp[i], tmp[j]));
    
    return d;
}

signed main() {
    scanf("%d", &n);
    
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &p[i].x, &p[i].y);
    
    stable_sort(p + 1, p + 1 + n, [](const Point &a, const Point &b) { return a.x < b.x; });
    printf("%lld", solve(1, n));
    return 0;
}

CF429D Tricky Function

给定 \(a_{1 \sim n}\) ，令 \(f(i, j) = (i - j)^2 + g^2(i, j)\) ，其中 \(g(i, j) = \sum_{k = \min(i, j) + 1}^{\max(i, j)} a_k\) ，求 \(\min_{1 \leq i < j \leq n} f(i, j)\) 。

\(n \leq 10^5\)

首先可以发现 \(f(i, j) = f(j, i)\) ，钦定 \(j < i\) ，则 \(g(i, j) = s_i - s_j\) ，其中 \(s\) 为前缀和，因此 \(f(i, j) = (i - j)^2 + (s_i - s_j)^2\) 。

发现这个形式很像两点距离公式，问题转化为给定平面上 \(n\) 个点 \((i, s_i)\) ，求最近点对。不难用分治做到 \(O(n \log n)\) 。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll inf = 1e18;
const int N = 1e5 + 7;

struct Point {
    int x, y;
} p[N], tmp[N];

int n;

inline ll dist(const Point &a, const Point &b) {
    return 1ll * (a.x - b.x) * (a.x - b.x) + 1ll * (a.y - b.y) * (a.y - b.y);
}

inline ll solve(int l, int r) {
    if (l == r)
        return inf;
        
    int mid = (l + r) >> 1, midx = p[mid].x;
    ll d = min(solve(l, mid), solve(mid + 1, r));
    inplace_merge(p + l, p + mid + 1, p + r + 1, 
        [](const Point &a, const Point &b) { return a.y < b.y; });
    int len = 0;
    
    for (int i = l; i <= r; ++i)
        if (1ll * (midx - p[i].x) * (midx - p[i].x) < d)
            tmp[++len] = p[i];
    
    for (int i = 1; i <= len; ++i)
        for (int j = i + 1; j <= len && 1ll * (tmp[j].y - tmp[i].y) * (tmp[j].y - tmp[i].y) < d; ++j)
            d = min(d, dist(tmp[i], tmp[j]));
    
    return d;
}

signed main() {
    scanf("%d", &n);
    
    for (int i = 1; i <= n; ++i)
        scanf("%d", &p[i].y), p[i].x = i, p[i].y += p[i - 1].y;
    
    printf("%lld", solve(1, n));
    return 0;
}

Xor

给定 \(a_{0 \sim 2^n - 1}\) 和 \(b_{0 \sim n}\) ，令 \(c_i = \sum_{j = 0}^{2^n - 1} a_j \times b_{\operatorname{popcount}(i \oplus j)}\) ，求 \(c_{0 \sim 2^n - 1}\) ，

\(n \leq 18\)

考虑按二进制位分治。设当前分治区间为 \([l, r]\) ，深度为 \(d\) ，其中 \([l, mid]\) 的第 \(d\) 为均为 \(0\) ，\([mid + 1, r]\) 的第 \(d\) 位均为 \(1\) 。

设 \(f_{i, j}\) 表示分治区间内与 \(i\) 有 \(j\) 位二进制不同的数的和，不难合并 \([l, mid]\) 和 \([mid + 1, r]\) 的 \(f\) 。

时间复杂度应该是 \(O(n^2 2^n)\) 的。

基于中点的序列分治

主要就是讨论跨过中点的区间的贡献，一般的维护信息方式是从中间向两边扩展。

CF549F Yura and Developers

给定数组 \(a_{1 \sim n}\) 以及模数 \(k\) ，求满足以下条件的区间 \([l, r]\) 的数量：

• \(r - l + 1 \geq 2\) 。
• \(\sum_{i = l}^r a_i \equiv \max_{i = l}^r a_i \pmod{k}\) 。

\(n \leq 3 \times 10^5\) ，\(k \leq 10^6\)

考虑分治，讨论如何计算跨过中点的贡献。先求出以 \(i\) 为左端点且区间最大值出现在左区间的所有右端点的答案，可以用指针维护可行右端点的区间。那么得到 \(s_r \equiv mx + s_{i - 1}\) ，直接用桶存一下即可。

右区间同理，注意不能统计左区间也有最大值的情况，时间复杂度 \(O(n \log n)\) 。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 3e5 + 7, K = 1e6 + 7;

int a[N], s[N], cnt[K];

ll ans;
int n, k;

void solve(int l, int r) {
    if (l == r)
        return;
    
    int mid = (l + r) >> 1;
    solve(l, mid), solve(mid + 1, r);
    int j = mid + 1;
    
    for (int i = mid, mx = a[i]; i >= l; mx = max(mx, a[--i])) {
        for (; j <= r && a[j] <= mx; ++j)
            ++cnt[s[j]];
        
        ans += cnt[(s[i - 1] + mx) % k];
    }
    
    for (--j; j > mid; --j)
        --cnt[s[j]];
    
    for (int i = mid + 1, mx = a[i]; i <= r; mx = max(mx, a[++i])) {
        for (; j >= l && a[j] < mx; --j)
            ++cnt[s[j - 1]];
        
        ans += cnt[(s[i] - mx % k + k) % k];
    }

    for (++j; j <= mid; ++j)
        --cnt[s[j - 1]];
}

signed main() {
    scanf("%d%d", &n, &k);
    
    for (int i = 1; i <= n; ++i)
        scanf("%d", a + i), s[i] = (s[i - 1] + a[i]) % k;
    
    solve(1, n);
    printf("%lld", ans);
    return 0;
}

P8317 [FOI2021] 幸运区间

给出长度为 \(n\) 的序列，每个位置上有 \(d\) 个数。需要选出 \(k\) 个数。

如果一个区间内每个位置上的 \(d\) 个数至少有一个出现在选出的 \(k\) 个数中，则是一个幸运区间。

求最长的幸运区间。

\(n \leq 10^5\) ，\(d \leq 4\) ，\(k \leq 3\)

考虑分治，每次从中点开始，暴力向两端扩展，不能扩展时加入一个数继续扩展。由于 \(d, k\) 都很小，加入的数直接暴搜即可，时间复杂度 \(O(nd \log n + nd^k)\) 。

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

int a[N][D];
bool chose[N];

int n, d, k, ansl, ansr;

void dfs(const int L, const int R, int cnt, int l, int r) {
    while (l > L) {
        bool flag = false;

        for (int i = 1; i <= d; ++i)
            flag |= chose[a[l - 1][i]];

        if (flag)
            --l;
        else
            break;
    }

    while (r < R) {
        bool flag = false;

        for (int i = 1; i <= d; ++i)
            flag |= chose[a[r + 1][i]];

        if (flag)
            ++r;
        else
            break;
    }

    if (r - l + 1 == ansr - ansl + 1 ? l < ansl : r - l + 1 > ansr - ansl + 1)
        ansl = l, ansr = r;

    if (cnt == k)
        return;

    if (l > L) {
        for (int i = 1; i <= d; ++i)
            chose[a[l - 1][i]] = true, dfs(L, R, cnt + 1, l - 1, r), chose[a[l - 1][i]] = false;
    }

    if (r < R) {
        for (int i = 1; i <= d; ++i)
            chose[a[r + 1][i]] = true, dfs(L, R, cnt + 1, l, r + 1), chose[a[r + 1][i]] = false;
    }
}

void solve(int l, int r) {
    if (l > r)
        return;

    int mid = (l + r) >> 1;
    solve(l, mid - 1), solve(mid + 1, r);

    for (int i = 1; i <= d; ++i)
        chose[a[mid][i]] = true, dfs(l, r, 1, mid, mid), chose[a[mid][i]] = false;
}

signed main() {
    int T;
    scanf("%d", &T);

    for (int task = 1; task <= T; ++task) {
        scanf("%d%d%d", &n, &d, &k);

        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= d; ++j)
                scanf("%d", a[i] + j);

        ansl = ansr = n + 1, solve(1, n);
        printf("Case #%d: %d %d\n", task, ansl - 1, ansr - 1);
    }

    return 0;
}

CF526F Pudding Monsters

给定一个 \(n \times n\) 的棋盘，其中有 \(n\) 个棋子，每行每列恰好有一个棋子。

对于所有的 \(1 \leq k \leq n\)，求有多少个 \(k \times k\) 的子棋盘中恰好有 \(k\) 个棋子。

\(n \le 3 \times 10^5\)

首先转化为统计值域连续区间的数量，即有多少区间满足 \(\max - \min = r - l\) 。

考虑直接分治：

• 最大最小值均在左半段：\(mx - mn = j - i \Rightarrow j = i + mx - mn\) 。
• 最小值在左半段，最大值在右半段：\(mx_j - mn_i = j - i \Rightarrow mn_i - i = mx_j - j\) 。
• 最大最小值均在右半段：与上面对称。
• 最大值在左半段，最小值在右半段：与上面对称。

时间复杂度 \(O(n \log n)\) 。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 3e5 + 7;

int a[N], mx[N], mn[N], cnt[N << 1];

ll ans;
int n;

void solve(int l, int r) {
    if (l == r) {
        ++ans;
        return;
    }
    
    int mid = (l + r) >> 1;
    solve(l, mid), solve(mid + 1, r);
    mn[mid] = mx[mid] = a[mid];

    for (int i = mid - 1; i >= l; --i)
        mn[i] = min(mn[i + 1], a[i]), mx[i] = max(mx[i + 1], a[i]);
    
    mn[mid + 1] = mx[mid + 1] = a[mid + 1];
    
    for (int i = mid + 2; i <= r; ++i)
        mn[i] = min(mn[i - 1], a[i]), mx[i] = max(mx[i - 1], a[i]);
    
    for (int i = mid; i >= l; --i) {
        int j = i + mx[i] - mn[i];
        
        if (mid + 1 <= j && j <= r && mn[i] < mn[j] && mx[j] < mx[i])
            ++ans;
    } // min in left, max in left
    
    for (int j = mid + 1; j <= r; ++j) {
        int i = j - mx[j] + mn[j];
        
        if (l <= i && i <= mid && mn[j] < mn[i] && mx[i] < mx[j])
            ++ans;
    } // min in right, max in right
    
    for (int i = mid, k = mid + 1, j = mid + 1; i >= l; --i) {
        for (; j <= r && mn[j] > mn[i]; ++j)
            ++cnt[mx[j] - j + N];
        
        for (; k < j && mx[k] < mx[i]; ++k)
            --cnt[mx[k] - k + N];
        
        ans += cnt[mn[i] - i + N];
    } // min in left, max in right
    
    for (int i = mid + 1; i <= r; ++i)
        cnt[mx[i] - i + N] = 0;
    
    for (int j = mid + 1, k = mid, i = mid; j <= r; ++j) {
        for (; i >= l && mn[i] > mn[j]; --i)
            ++cnt[mx[i] + i];
        
        for (; k > i && mx[k] < mx[j]; --k)
            --cnt[mx[k] + k];
        
        ans += cnt[mn[j] + j];
    } // min in right, max in left
    
    for (int i = l; i <= mid; ++i)
        cnt[mx[i] + i] = 0;
}

signed main() {
    scanf("%d", &n);
    
    for (int i = 1; i <= n; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        a[x] = y;
    }
    
    solve(1, n);
    printf("%lld", ans);
    return 0;
}

基于断点的序列分治

断点：当前分治区间内合法子区间一定不包含的点。

主要思想就是每次按断点将区间分治处理，若没有端点则该区间合法。

寻找断点常用中途相遇法，找一个目标位置时可以从两边开始找，复杂度分析和启发式分裂是一样的。

若还要维护每个点的贡献，则可以钦定处理当前区间时仅存在当前区间的贡献，并在回溯时删除。

每次先删除断点和小区间的贡献，再递归大区间，再加入小区间的贡献，再递归小区间。

值得一提的是这样维护可以支持下标的大小关系不改变。

UVA1608 不无聊的序列 Non-boring sequences

给定 \(a_{1 \sim n}\) ，判断是否存在一个区间，其不存在唯一元素。

\(n \leq 2 \times 10^5\)

考虑分治，每次用唯一元素的位置将其分为两个区间。

采用中途相遇法，从两端同时开始找，若前驱后继都不在该区间内，则其是该区间的唯一元素。

复杂度分析和启发式分裂的复杂度一样，为 \(O(n \log n)\) 。

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

int a[N], lst[N], nxt[N];

int n;

bool solve(int l, int r) {
    if (l >= r)
        return false;

    int pl = l, pr = r, mid = -1;

    for (int pl = l, pr = r; pl <= pr && mid == -1; ++pl, --pr) {
        if (lst[pl] < l && nxt[pl] > r)
            mid = pl;
        else if (lst[pr] < l && nxt[pr] > r)
            mid = pr;
    }

    return ~mid ? solve(l, mid - 1) || solve(mid + 1, r) : true;
}

signed main() {
    int T;
    scanf("%d", &T);

    while (T--) {
        scanf("%d", &n);
        map<int, int> mp;

        for (int i = 1; i <= n; ++i) {
            scanf("%d", a + i);
            lst[i] = (mp.find(a[i]) == mp.end() ? 0 : mp[a[i]]), mp[a[i]] = i;
        }

        mp.clear();

        for (int i = n; i; --i)
            nxt[i] = (mp.find(a[i]) == mp.end() ? n + 1 : mp[a[i]]), mp[a[i]] = i;

        puts(solve(1, n) ? "boring" : "non-boring");
    }

    return 0;
}

金牌歌手

给定序列 \(a_{1 \sim n}, b_{1 \sim n}\) ，其中 \(b\) 单调不升。求最长区间 \([l, r]\) ，满足区间内的任意元素在区间内的出现次数均 \(\geq b_{r - l + 1}\) 。

\(n \leq 10^6\)

由于 \(b\) 单调不升，若一个数字使得 \([l, r]\) 不合法，那么 \([l, r]\) 内所有包含该数字的子区间必然不合法。

考虑分治，每次找到一个不合法的位置将区间分为两个部分，问题转化为求当前分治区间内某个数的出现次数。

考虑维护一个桶 \(cnt\) ，钦定每次分治处理时 \(cnt\) 恰为当前区间内数字的出现次数，并在回溯时清空。那么只要每次将小区间里的数字一个个删除，然后递归大区间，再一个个加入小区间里的数，再递归小区间即可。

时间复杂度 \(O(n \log n)\) 。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;

int a[N], b[N], cnt[N];

int n;

int solve(int l, int r) {
    if (l > r)
        return 0;

    int mid = -1;

    for (int pl = l, pr = r; pl <= pr && mid == -1; ++pl, --pr) {
        if (cnt[a[pl]] < b[r - l + 1])
            mid = pl;
        else if (cnt[a[pr]] < b[r - l + 1])
            mid = pr;
    }

    if (mid == -1) {
        for (int i = l; i <= r; ++i)
            --cnt[a[i]];

        return r - l + 1;
    } else if (mid - l > r - mid) {
        for (int i = mid; i <= r; ++i)
            --cnt[a[i]];

        int res = solve(l, mid - 1);

        for (int i = mid + 1; i <= r; ++i)
            ++cnt[a[i]];

        return max(res, solve(mid + 1, r));
    } else {
        for (int i = l; i <= mid; ++i)
            --cnt[a[i]];

        int res = solve(mid + 1, r);

        for (int i = l; i < mid; ++i)
            ++cnt[a[i]];

        return max(res, solve(l, mid - 1));
    }
}

signed main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i)
        scanf("%d", a + i), ++cnt[a[i]];

    for (int i = 1; i <= n; ++i)
        scanf("%d", b + i);

    printf("%d", solve(1, n));
    return 0;
}

二维分治

一般的分治方式是每次切割边长较大者的中线。

CF364E Empty Rectangles

有一个 \(n \times m\) 的01矩阵，询问有多少个子矩阵和为 \(k\) 。

\(n, m \leq 2500\) ，\(k \leq 6\)

考虑跨中线的答案，以竖直切割为例。枚举 \(y\) 坐标作为上下边界，维护 \(left_i, right_i\) 分别表示中线左右矩形中 \(1\) 的个数 \(< i\) 时最多扩展到的位置，统计答案时枚举 \(k\) 个 \(1\) 的分布即可。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2.5e3 + 7, K = 11;

int s[N][N];
char str[N];

ll ans;
int n, m, k;

inline int query(int xl, int xr, int yl, int yr) {
    return s[xr][yr] - s[xl - 1][yr] -  s[xr][yl - 1] + s[xl - 1][yl - 1];
}

void solve(int xl, int xr, int yl, int yr) {
    if (xl == xr && yl == yr) {
        ans += (query(xl, xr, yl, yr) == k);
        return;
    }
    
    if (xr - xl > yr - yl) {
        int mid = (xl + xr) >> 1;
        solve(xl, mid, yl, yr), solve(mid + 1, xr, yl, yr);
        
        for (int l = yl; l <= yr; ++l) {
            vector<int> left(k + 2, xl), right(k + 2, xr);
            left[0] = mid + 1, right[0] = mid;
            
            for (int r = l; r <= yr; ++r) {
                for (int i = 1; i <= k + 1; ++i) {
                    while (query(left[i], mid, l, r) >= i)
                        ++left[i];
                    
                    while (query(mid + 1, right[i], l, r) >= i)
                        --right[i];
                }
                
                for (int i = 0; i <= k; ++i)
                    ans += 1ll * (left[i] - left[i + 1]) * (right[k - i + 1] - right[k - i]);
            }
        }
    } else {
        int mid = (yl + yr) >> 1;
        solve(xl, xr, yl, mid), solve(xl, xr, mid + 1, yr);
        
        for (int l = xl; l <= xr; ++l) {
            vector<int> down(k + 2, yl), up(k + 2, yr);
            down[0] = mid + 1, up[0] = mid;
            
            for (int r = l; r <= xr; ++r) {
                for (int i = 1; i <= k + 1; ++i) {
                    while (query(l, r, down[i], mid) >= i)
                        ++down[i];
                    
                    while (query(l, r, mid + 1, up[i]) >= i)
                        --up[i];
                }
                
                for (int i = 0; i <= k; ++i)
                    ans += 1ll * (down[i] - down[i + 1]) * (up[k - i + 1] - up[k - i]);
            }
        }
    }
}

signed main() {
    scanf("%d%d%d", &n, &m, &k);
    
    for (int i = 1; i <= n; ++i) {
        scanf("%s", str + 1);
        
        for (int j = 1; j <= m; ++j)
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + (str[j] == '1');
    }
    
    solve(1, n, 1, m);
    printf("%lld", ans);
    return 0;
}

笛卡尔树分治

即最值分治，每次按最值的位置将区间分为两部分。

需要保证每层的复杂度仅与小区间有关，否则会退化到平方级别。

通常是按照启发式分裂的套路，枚举短区间，算长区间的贡献。

P4755 Beautiful Pair

给定序列 \(a_{1 \sim n}\) ，求有多少对 \(i \leq j\) 满足 \(a_i \times a_j \leq \max_{k = i}^j a_k\) 。

\(n \leq 10^5\)

构建笛卡尔树结构，设当前分治到区间 \([l, r]\) ，当前笛卡尔树上的节点在原序列上的编号是 \(p\) 。

根据分治套路，我们只需要计算跨过 \(p\) 的答案，然后 \([l, p - 1]\) 和 \([p + 1, r]\) 分治处理。

以左边为短区间为例，考虑枚举左边，算右边的贡献。可以枚举点对的左端点 \(l\) ，则 \(a_r \leq \frac{a_p}{a_l}\) 。

时间复杂度 \(O(n \log^2 n)\) 。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 7;

int a[N];

ll ans;
int n;

template <class T = int>
inline T read() {
    char c = getchar();
    bool sign = c == '-';
    
    while (c < '0' || c > '9')
        c = getchar(), sign |= c == '-';
    
    T x = 0;
    
    while ('0' <= c && c <= '9')
        x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    
    return sign ? (~x + 1) : x;
}

namespace SMT {
const int S = N << 5;

int s[S], lc[S], rc[S];
int rt[N];

int tot;

int insert(int x, int nl, int nr, int k) {
    int y = ++tot;
    lc[y] = lc[x], rc[y] = rc[x], s[y] = s[x] + 1;
    
    if (nl == nr)
        return y;
    
    int mid = (nl + nr) >> 1;
    
    if (k <= mid)
        lc[y] = insert(lc[x], nl, mid, k);
    else
        rc[y] = insert(rc[x], mid + 1, nr, k);
    
    return y;
}

int query(int x, int y, int nl, int nr, int k) {
    if (nl == nr)
        return s[y] - s[x];
    
    int mid = (nl + nr) >> 1;
    
    if (k <= mid)
        return query(lc[x], lc[y], nl, mid, k);
    else
        return (s[lc[y]] - s[lc[x]]) + query(rc[x], rc[y], mid + 1, nr, k);
}
} // namespace SMT

namespace CST {
int lc[N], rc[N];

int root;

inline void build() {
    static int sta[N];

    for (int i = 1, top = 0; i <= n; ++i) {
        int k = top;
        
        while (k && a[sta[k]] < a[i])
            --k;
        
        if (k)
            rc[sta[k]] = i;
        else
            root = i;
        
        if (k < top)
            lc[i] = sta[k + 1];
        
        sta[top = ++k] = i;
    }
}

void solve(int x, int l, int r) {
    if (x - l <= r - x) {
        for (int i = l; i <= x; ++i)
            ans += SMT::query(SMT::rt[x - 1], SMT::rt[r], 1, 1e9, a[x] / a[i]);
    } else {
        for (int i = x; i <= r; ++i)
            ans += SMT::query(SMT::rt[l - 1], SMT::rt[x], 1, 1e9, a[x] / a[i]);
    }
    
    if (lc[x])
        solve(lc[x], l, x - 1);
    
    if (rc[x])
        solve(rc[x], x + 1, r);
}
} // namespace CST

signed main() {
    n = read();
    
    for (int i = 1; i <= n; ++i)
        SMT::rt[i] = SMT::insert(SMT::rt[i - 1], 1, 1e9, a[i] = read());
    
    CST::build(), CST::solve(CST::root, 1, n);
    printf("%lld", ans);
    return 0;
}

其他

树上分治：点分治、边分治。

在线转离线：主要是 cdq 分治、分治 FFT 以及线段树分治。

强制在线：建立分治结构（如线段树、猫树），本质是 DS 题。

基于答案的分治：整体二分。