「做题记录」分治选做

· · 算法·理论

先写一些分治,然后做题。

二区间合并

考虑如下问题:

给你一个长为 n 的静态序列 a_1,a_2,\cdots,a_n。q 次询问给出 [l,r],查询

a_l \otimes a_{l+1} \cdots \otimes a_{r}

其中 \otimes 是具有结合律的运算,计算 x \otimes y 的代价为 O(k)。

我们知道线段树可以在 O(kn) 预处理后,以 O(k \log n) 的代价在线回答每次询问。

二区间合并(也称为猫树分治)则可以在 O(k n \log n) 的时间内离线解决该问题。

猫树本身是一种对线段树结构进行魔改的数据结构。它的核心思想是:

二区间合并 / 猫树分治使用了类似的思想。算法流程如下:

一张原理图:

下面分析处理长为 n 的区间时,二区间合并的复杂度。可以列出如下递归式:

T(n)=2T\left(\dfrac{n}{2}\right)+O(kn)

得 T(n)=O(kn \log n)。

最值分治

最值分治是一种特殊的二区间合并。其处理的问题常常与最值结构相关,因此我们将二区间合并中的 m 改成区间 [l, r] 中最值出现的位置,然后统计最值到两侧的贡献。

笛卡尔树是一种典型的最值分治结构。它是一棵二叉树,每个节点有权值二元组 (i,a_i),要求下标 i 满足二叉搜索树性质,权值 a_i 满足堆性质。

笛卡尔树可在 O(n) 时间内构建。顺序插入每个 a_i,可知新节点一定位于当前根的右链上。自底向上比较右链节点的权值,若满足偏序关系,则将新节点挂为右子,原右子树变为其左子树。用单调栈维护右链。

int n, a[N], l[N], r[N];
void build() {
    stack<int> st;
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && a[st.top()] > a[i]) l[i] = st.top(), st.pop();
        if (!st.empty()) r[st.top()] = i;
        st.emplace(i);
    }
}

笛卡尔树可视为一种分治结构:找到当前区间最值,然后从最值两段劈开继续递归。因此最值分治也可以视作笛卡尔树上 DP。

网格图分治

网格图分治是在平面上的分治。网格图分治也可以叫做“二平面合并”,或者二维猫树分治。

P3350 [ZJOI2016] 旅行者:

给出一个 n \times m 的无向带权网格图。q 次询问从 (x_1,y_1) 到 (x_2,y_2) 的最短路。

类似于二区间合并,将所有询问离线后进行分治处理。对于当前考虑的子网格:

原理图:

这样一来:

下面简要分析网格图分治的复杂度。

根据均值不等式,上述算法的最劣时间复杂度在网格的长和宽同阶时取得。因此不妨将网格视为边长为 n 的正方形进行分析,此时递归式为

T(n)=O(n^3 \log n)+4T(n/2)

由主定理得 T(n)=O(n^3 \log n)。

更一般地,设网格图的面积为 S,询问数量为 q,则时间复杂度为 O\left( (S+q) \sqrt{S} \log S\right)。而如果最短路部分可以加速到线性,复杂度可以优化到 O\left((S+q) \sqrt{S}\right)。

:::::info[P3350 代码]

const int N = 1e5 + 5, inf = 1e9;

int n, m, q, ans[N];
using query = tuple<int, int, int, int, int>;  // {x1, y1, x2, y2, id}
vector<query> qry;
// L, R, U, D
const int dirx[] = {0, 0, 0, -1, 1};
const int diry[] = {0, -1, 1, 0, 0};
vector<vector<int>> dis, e[5];

struct node {
    int x, y, d;
    node(int a = 0, int b = 0, int c = 0) : x(a), y(b), d(c) {}
    bool operator< (const node& a) const {return d > a.d;}
};

void dijkstra(int lx, int rx, int ly, int ry, int sx, int sy, const vector<query>& q) {
    if (dis.empty()) dis.resize(n + 5, vector<int>(m + 5, 0));
    for (int x = lx; x <= rx; x++) {
        for (int y = ly; y <= ry; y++) dis[x][y] = inf;
    }
    priority_queue<node> h;
    dis[sx][sy] = 0, h.emplace(sx, sy, 0);
    while (!h.empty()) {
        auto [x, y, dl] = h.top(); h.pop();
        if (dl != dis[x][y]) continue;
        for (int d = 1; d <= 4; d++) {
            int nx = x + dirx[d], ny = y + diry[d];
            if (nx < lx || nx > rx || ny < ly || ny > ry) continue;
            if (dis[nx][ny] > dis[x][y] + e[d][x][y]) dis[nx][ny] = dis[x][y] + e[d][x][y], h.emplace(nx, ny, dis[nx][ny]);
        }
    }
    for (const auto& [x1, y1, x2, y2, id] : q) ans[id] = min(ans[id], dis[x1][y1] + dis[x2][y2]);
}

void solve(int lx, int rx, int ly, int ry, vector<query> q) {
    if (lx > rx || ly > ry || q.empty()) return;
    if (rx - lx > ry - ly) {
        int mid = (lx + rx) >> 1;
        for (int y = ly; y <= ry; y++) dijkstra(lx, rx, ly, ry, mid, y, q);
        vector<query> ql, qr;
        for (const auto& [x1, y1, x2, y2, id] : q) {
            if (x1 < mid && x2 < mid) ql.emplace_back(x1, y1, x2, y2, id);
            if (mid < x1 && mid < x2) qr.emplace_back(x1, y1, x2, y2, id);
        }
        solve(lx, mid - 1, ly, ry, ql), solve(mid + 1, rx, ly, ry, qr);
    } else {
        int mid = (ly + ry) >> 1;
        for (int x = lx; x <= rx; x++) dijkstra(lx, rx, ly, ry, x, mid, q);
        vector<query> ql, qr;
        for (const auto& [x1, y1, x2, y2, id] : q) {
            if (y1 < mid && y2 < mid) ql.emplace_back(x1, y1, x2, y2, id);
            if (mid < y1 && mid < y2) qr.emplace_back(x1, y1, x2, y2, id);
        }
        solve(lx, rx, ly, mid - 1, ql), solve(lx, rx, mid + 1, ry, qr);
    }
}

void _main() {
    cin >> n >> m;
    for (int d = 1; d <= 4; d++) e[d].resize(n + 5, vector<int>(m + 5, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < m; j++) cin >> e[2][i][j], e[1][i][j + 1] = e[2][i][j];
    }
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= m; j++) cin >> e[4][i][j], e[3][i + 1][j] = e[4][i][j];
    }
    cin >> q;
    for (int i = 1, x1, y1, x2, y2; i <= q; i++) cin >> x1 >> y1 >> x2 >> y2, qry.emplace_back(x1, y1, x2, y2, i);
    fill(ans + 1, ans + q + 1, inf);
    solve(1, n, 1, m, qry);
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
} 

:::::

点分治

点分治是一种树上的分治,常用于对某些限定条件的路径进行静态统计。可以认为二区间合并是点分治在链上的特殊情况。

P3806 【模板】点分治:

给定一棵有 n 个点的树,q 次询问树上距离为 k 的点对是否存在。

本题给出的树是一棵无根树。不妨任选一个点 p 为根,则路径被分为两类:

对于第二种情形,我们已经看到了子问题的结构,递归分治即可。下面主要处理经过 p 的路径。

从 p 开始自顶向下做 DFS,维护每个 u 到 p 之间的距离 d,然后枚举一个 u,问题变成距离为 k-d 的点 v 是否出现过,容易用一个长为 k 的数组维护。

不过我们发现一个问题:u,v 不能位于同一个子树内。在点分治中,对于这种情况,一般有两种处理方法:

对于本题,可行性不具有可减性,我们选择第一种方法。

注意到如果随意选择 p,会被链的情形卡到 O(n^2)。因此,点分治的核心是每次选择重心作为 p。由于重心的性质,每棵子树大小都不会超过一半,每次递归规模折半,复杂度就是 O(n \log n) 了。

对于本题,我们还要做 q 次询问,总复杂度是 O(nq \log n) 的。由于点分治的 O(n \log n) 常数很大,我们应该把所有询问一起处理,而不是每次询问点分一次。

:::::info[P3806 代码]

const int N = 1e4 + 5, K = 1e7 + 5;
int n, q, cur, ctr, k[N], sz[N], vis[N], ans[N];
vector<pair<int, int>> e[N];

void dfs1(int u, int fa) {   // 找重心
    sz[u] = 1;
    for (auto [v, w] : e[u]) {
        if (v == fa || vis[v]) continue;
        dfs1(v, u), sz[u] += sz[v];
    }
    if (!ctr && 2 * sz[u] >= cur) ctr = u;
}
void dfs2(int u, int fa) {   // 统计子树大小
    cur++;
    for (auto [v, w] : e[u]) if (!vis[v] && v != fa) dfs2(v, u);
}
void dfs3(int u, int fa, int dep, vector<int>& vec) {   // 统计距离
    if (dep >= K) return;
    vec.emplace_back(dep);
    for (auto [v, w] : e[u]) {
        if (v == fa || vis[v]) continue;
        dfs3(v, u, dep + w, vec);
    }
}

bitset<K> has;
void update(int u) {
    vector<int> vec = {0};
    has[0] = 1;
    for (auto [v, w] : e[u]) {
        if (vis[v]) continue;
        vector<int> cur; dfs3(v, u, w, cur);
        for (int d : cur) for (int i = 1; i <= q; i++) {
            if (k[i] >= d && has[k[i] - d]) ans[i] = true;
        }
        for (int d : cur) has[d] = 1, vec.emplace_back(d);
    }
    for (int d : vec) has[d] = 0;
}
void solve(int u) {
    vis[u] = true, update(u);
    for (auto [v, w] : e[u]) {
        if (vis[v]) continue;
        cur = ctr = 0, dfs2(v, u), dfs1(v, u), solve(ctr);
    }
}

void _main() {
    cin >> n >> q;
    for (int i = 1, u, v, w; i < n; i++) {
        cin >> u >> v >> w;
        e[u].emplace_back(v, w), e[v].emplace_back(u, w);
    }
    for (int i = 1; i <= q; i++) cin >> k[i];
    cur = n, dfs1(1, -1), solve(ctr);
    for (int i = 1; i <= q; i++) cout << (ans[i] ? "AYE\n" : "NAY\n");
} 

:::::

边分治

边分治和点分治非常相似,都是用来处理树上信息统计的分治。区别在于,点分治的分治中心是点,而边分治的分治中心则是一条边。

记 s_u 为子树 u 的大小。类比点分治,我们找到 \max(s_v,n-s_v) 最小的边 (u,v),然后处理跨过 (u,v) 边的贡献,将两侧的贡献递归到子树中计算。

然而朴素边分治的复杂度是假的。因此,我们需要将树进行三度化,即通过建虚点的方法,将多叉树转成二叉树再做边分治。

需要说明的是,三度化的技巧不局限于边分治。如果点分治难以合并多个信息,我们也可以三度化后点分治。

线段树分治

线段树分治是利用线段树结构对时间轴分治的一种技巧。一般来说,这类问题的形式如下:维护一些信息,这些信息在一个时间段内出现,离线回答某个时刻的信息并。

如果直接对时间轴扫描线,用数据结构维护某种信息,则需要信息具有可减性。比如并查集连边就是无法做到快速删除的。而线段树分治只要求操作可撤销,比如并查集是可以快速撤销的。

下面以模板题 P5787 【模板】线段树分治 / 二分图为例:

维护一个 n 个点,m 条边的无向图,有 k 个时刻,第 i 条边 (u_i,v_i) 出现的时间段为 [l_i,r_i)。判断每个时刻图是否为二分图。

先考虑如何判断二分图:使用扩展域并查集,将点 u 拆成两个点 u_0,u_1,对于 (u,v) 连边 u_0\to v_1, u_1 \to v_0,图是二分图当且仅当对于所有 u,u_0,u_1 无边。

注意到连边不具有可减性,但并查集可撤销。

具体地,使用并查集维护父亲的所属关系,并将每次操作入栈。撤销时,我们不断出栈,并做原操作的逆操作。可以发现这里不能路径压缩,可以用启发式合并做到 O(n \log n)。

下面正式叙述线段树分治的流程。

对时间轴建立线段树,每个节点代表了一个时间段。在节点上挂 vector 来表示这个节点的操作。可以在 O(\log k) 的时间内插入一个操作。

插入完成后,从根节点自顶向下扫描线段树,维护当前的连边状态,每到一个节点就进行操作,退出节点就撤销操作。

可以发现上述算法的时间复杂度为 O(n \log n \log k)。

:::::info[P5787 代码]

const int N = 1e5 + 5;
int n, m, k;
struct dsu {
    int fa[N << 1], sz[N << 1];
    stack<int, vector<int>> st;
    void init() {iota(fa, fa + (N << 1), 0), fill(sz, sz + (N << 1), 1);}
    int find(int x) {return x == fa[x] ? x : find(fa[x]);}
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        fa[x] = y, sz[y] += sz[x], st.emplace(x);
    }
    void undo(int x) {
        while ((int) st.size() > x) {
            int u = st.top(); st.pop();
            if (u != fa[u]) sz[fa[u]] -= sz[u], fa[u] = u;
        }
    }
} uf;

vector<pair<int, int>> val[N << 2];
#define ls (rt << 1)
#define rs (rt << 1 | 1)
void change(int tl, int tr, const pair<int, int>& c, int l = 1, int r = k, int rt = 1) {
    if (tl <= l && r <= tr) return val[rt].emplace_back(c), void();
    int mid = (l + r) >> 1;
    if (tl <= mid) change(tl, tr, c, l, mid, ls);
    if (tr > mid) change(tl, tr, c, mid + 1, r, rs);
}
bool ans[N];
void solve(int l = 1, int r = k, int rt = 1) {
    int mid = (l + r) >> 1, keep = 1, step = uf.st.size();
    for (const auto &i : val[rt]) {
        int u = i.first, v = i.second;
        if (uf.find(u) == uf.find(v)) {
            fill(ans + l, ans + r + 1, 0), keep = 0;
            break;
        }
        uf.unite(u, v + n), uf.unite(u + n, v);
    }
    if (!keep) return uf.undo(step), void();
    if (l == r) ans[l] = 1;
    else solve(l, mid, ls), solve(mid + 1, r, rs);
    uf.undo(step);
}

void _main() {
    cin >> n >> m >> k;
    uf.init();
    for (int i = 1, u, v, l, r; i <= m; i++) {
        cin >> u >> v >> l >> r;
        change(l + 1, r, {u, v});
    }
    solve();
    for (int i = 1; i <= k; i++) cout << (ans[i] ? "Yes" : "No") << '\n';
}

:::::

CDQ 分治

本来这里有一堆东西,但是我发现 https://www.luogu.com.cn/article/hsdkbux2 写的远好于我,所以就删掉了。读者可以阅读这篇专栏来学习。

下面补一个参考资料中没有提到的用途:CDQ 分治的结构还可以用来优化建图。

先回顾一下前后缀优化建图,它主要适用于将一个点向一段连续的前缀或后缀区间连边的场景。
我们利用前后缀和的结构,建一排前缀虚点链 p_i \to p_{i+1} 和后缀虚点链 s_i \to s_{i-1}。那么向前后缀连边的操作可以转化为找到对应虚点,并且在实点和虚点之间连边。边数为 O(n)。

考虑一种按偏序关系建图的问题,下面举一个例子:

给定一个 n 个点的有向图,每个点有点权 a_i。若 u<v \land a_u>a_v 则连边 u \to v。

直接做显然是 O(n^2) 的。注意到连边是二维偏序,考虑对这个过程 CDQ 分治。

对值域分治,设当前分治区间 [l,r],考虑从 [l,m] 向 (m,r] 连边。此时第一维限制已经满足,而第二维限制可以用类似于偏序问题的方法,先对 [l,m],(m,r] 内部按 a_i 排序。

排序后,对于 v \in (m,r],可向其连边的 u \in [l,m] 必然是一段后缀。于是可以对左区间构造虚点链,用双指针维护 i,j,将右区间的实点和左区间的虚点连边即可。

对于本题,使用归并排序则连边的复杂度为 O(n \log n)。

CDQ 优化建图的本质是使用 CDQ 分治套数据结构优化建图,来解决一些直接使用数据结构难以维护的连边关系。上一题中,我们使用的是 CDQ 分治套前后缀优化建图。

缺一分治

见「做题记录」背包 DP 选做。

练习

P6240 好吃的题目

给出 n 个物品,体积为 v_i,价值为 w_i。q 次询问,给出 l,r,V,求区间 [l,r] 上容量为 V 的 01 背包。

:::::success[题解]

01 背包的转移式为 f_i \gets f_{i-v_i}+w_i。若已有两个背包数组 f 和 g,需要求它们合并后容量为 V 的最大价值,可以做一个 (\max,+) 卷积:

\max_{i=0}^V (f_{i}+g_{V-i})

单次合并是 O(V) 的。如果你不想挑战图灵奖,就不用想着优化合并复杂度了。

直接使用线段树无法通过本题。采用二区间合并,从每个区间中点向两侧预处理背包数组即可。总时间复杂度为 O(nV \log n + qV)。

:::::

:::::info[代码]

const int N = 4e4 + 5, M = 205, Q = 2e5 + 5;
using node = tuple<int, int, int, int>;  // {l, r, V, id}

int n, q, v[N], w[N], ans[Q];
void solve(int l, int r, vector<node> qry) {
    if (qry.empty()) return;
    if (l == r) {  // 边界情况特判
        for (auto& [ql, qr, V, id] : qry) ans[id] = V >= v[l] ? w[l] : 0;
        return;
    }
    int mid = (l + r) >> 1;
    vector<vector<int>> f(mid - l + 5, vector<int>(M + 5, 0));   // 左侧
    vector<vector<int>> g(r - mid + 5, vector<int>(M + 5, 0));   // 右侧
    for (int i = mid; i >= l; i--) {
        int len = mid - i + 1;
        f[len] = f[len - 1];
        for (int j = M; j >= v[i]; j--) f[len][j] = max(f[len][j], f[len - 1][j - v[i]] + w[i]);
    }
    for (int i = mid + 1; i <= r; i++) {
        int len = i - mid;
        g[len] = g[len - 1];
        for (int j = M; j >= v[i]; j--) g[len][j] = max(g[len][j], g[len - 1][j - v[i]] + w[i]);
    }
    vector<node> ls, rs;
    for (auto& [ql, qr, V, id] : qry) {
        if (qr <= mid) {
            ls.emplace_back(ql, qr, V, id);
        } else if (mid < ql) {
            rs.emplace_back(ql, qr, V, id);
        } else {
            // (max, +) 卷积合并
            for (int j = 0; j <= V; j++) ans[id] = max(ans[id], f[mid - ql + 1][j] + g[qr - mid][V - j]);
        }
    }
    solve(l, mid, ls), solve(mid + 1, r, rs);
}

void _main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> v[i];
    for (int i = 1; i <= n; i++) cin >> w[i];
    vector<node> vec;
    for (int i = 1, l, r, v; i <= q; i++) {
        cin >> l >> r >> v;
        vec.emplace_back(l, r, v, i);
    }
    solve(1, n, vec);
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

:::::

P6109 [Ynoi2009] rprmq1

有一个 n \times n 的矩形,元素初值为 0。先进行 m 次矩形加,再进行 q 次矩形求 max。

:::::success[题解] 考虑本题的实际意义:将 x 轴视为时间轴。这样修改可以差分成 3-side 矩形,问题变为:

查询时间段的历史最值是困难的,但是前缀查询则是容易的。

对时间轴做二区间合并,在中点同侧的查询归入子问题。对于跨过中点的询问,我们从中点出发跑两次历史最值。

为了让每次询问时,有且仅有关联的操作被执行,需要精细讨论一下分治的顺序:

  1. 先将询问划分为左侧询问、右侧询问和跨过中点的询问三部分。将跨过中点的询问按照时间分组。
  2. 执行时刻 [l,m] 中的所有操作。
  3. 在时刻 m+1 进行重置,此时历史最值更新到当前最值。
  4. 执行时刻 (m,r] 中的所有操作,并且更新右端点关联的询问。
  5. 撤销时刻 (m,r] 中的所有操作。此时 [1,m] 的操作被正确执行,递归 (m,r]。
  6. 在时刻 m 进行重置,撤销 (m,r] 中的历史最值。
  7. 撤销时刻 [l,m] 中的所有操作,并且更新左端点关联的询问。此时 [1,l) 的操作被正确执行,递归 [l,m]。

注意一个细节:对于每个时刻的操作,必须先执行数值小的操作,否则历史最值会捕捉到一个虚假的峰值。所以执行操作要升序执行,撤销操作要倒序执行。

现在我们需要一棵历史和线段树,支持区间加、区间重置,维护当前最值、历史最值。考虑用 (\max,+) 矩阵推,设当前最值 M,历史最值 H,线段树维护向量 $ \begin{bmatrix} M \ H \end{bmatrix}

区间加 $x$ 为: $$ \begin{bmatrix} M+x \\ \max(H,M+x) \end{bmatrix} = \begin{bmatrix} x&-\infty \\ x&0 \end{bmatrix} \begin{bmatrix} M \\ H \end{bmatrix} $$ 区间重置为: $$ \begin{bmatrix} H\\ H \end{bmatrix} = \begin{bmatrix} -\infty & 0\\ -\infty & 0 \end{bmatrix} \begin{bmatrix} M \\ H \end{bmatrix} $$ 懒得半群优化了,视 $n,m$ 同阶,复杂度 $O(n \log^2 n+q \log n)$ 带 $8$ 倍常数。 ::::: :::::info[代码] ```cpp line-numbers line-numbers const int N = 5e4 + 5; const i64 inf = 1e15; using query = tuple<int, int, int, int, int>; using matrix = tuple<i64, i64, i64, i64>; using vec = tuple<i64, i64>; using opt = tuple<int, int, i64>; const matrix I = {0, -inf, -inf, 0}; matrix operator* (const matrix& a, const matrix& b) { auto [a00, a01, a10, a11] = a; auto [b00, b01, b10, b11] = b; i64 c00 = max(a00 + b00, a01 + b10); i64 c01 = max(a00 + b01, a01 + b11); i64 c10 = max(a10 + b00, a11 + b10); i64 c11 = max(a10 + b01, a11 + b11); return {c00, c01, c10, c11}; } vec operator* (const matrix& a, const vec& b) { auto [a00, a01, a10, a11] = a; auto [b0, b1] = b; i64 c0 = max(a00 + b0, a01 + b1), c1 = max(a10 + b0, a11 + b1); return {c0, c1}; } vec operator* (const vec& a, const vec& b) { return {max(get<0>(a), get<0>(b)), max(get<1>(a), get<1>(b))}; } int n, m, q; struct segtree { #define ls (rt << 1) #define rs (rt << 1 | 1) vec val[N << 2]; matrix tag[N << 2]; void pushup(int rt) {val[rt] = val[ls] * val[rs];} void pushdown(int rt) { if (tag[rt] == I) return; val[ls] = tag[rt] * val[ls], val[rs] = tag[rt] * val[rs]; tag[ls] = tag[rt] * tag[ls], tag[rs] = tag[rt] * tag[rs]; tag[rt] = I; } void build(int l = 1, int r = n, int rt = 1) { tag[rt] = I; if (l == r) return; int mid = (l + r) >> 1; build(l, mid, ls), build(mid + 1, r, rs); } void change(int tl, int tr, const matrix& c, int l = 1, int r = n, int rt = 1) { if (tl <= l && r <= tr) return tag[rt] = c * tag[rt], val[rt] = c * val[rt], void(); int mid = (l + r) >> 1; pushdown(rt); if (tl <= mid) change(tl, tr, c, l, mid, ls); if (tr > mid) change(tl, tr, c, mid + 1, r, rs); pushup(rt); } vec ask(int tl, int tr, int l = 1, int r = n, int rt = 1) { if (tl <= l && r <= tr) return val[rt]; int mid = (l + r) >> 1; pushdown(rt); if (tl <= mid && mid < tr) return ask(tl, tr, l, mid, ls) * ask(tl, tr, mid + 1, r, rs); return tl <= mid ? ask(tl, tr, l, mid, ls) : ask(tl, tr, mid + 1, r, rs); } } sgt; vector<opt> op[N]; i64 ans[N * 10]; void solve(int l, int r, vector<query> q) { if (q.empty()) return; if (l == r) { // 特判 for (auto& [l2, r2, x] : op[l]) sgt.change(l2, r2, {x, -inf, x, 0}); // 执行 for (auto& [l1, r1, l2, r2, id] : q) ans[id] = max(ans[id], get<0>(sgt.ask(l2, r2))); reverse(op[l].begin(), op[l].end()); for (auto& [l2, r2, x] : op[l]) sgt.change(l2, r2, {-x, -inf, -x, 0}); // 撤销 reverse(op[l].begin(), op[l].end()); return; } int mid = (l + r) >> 1; vector<query> ql, qr, qc; // 1. 划分查询 for (auto& [l1, r1, l2, r2, id] : q) { if (r1 <= mid) ql.emplace_back(l1, r1, l2, r2, id); else if (mid < l1) qr.emplace_back(l1, r1, l2, r2, id); else qc.emplace_back(l1, r1, l2, r2, id); } vector<vector<query>> L(mid - l + 1), R(r - mid + 1); for (auto& [l1, r1, l2, r2, id] : qc) { L[l1 - l].emplace_back(l1, r1, l2, r2, id); R[r1 - mid - 1].emplace_back(l1, r1, l2, r2, id); } for (int i = l; i <= mid; i++) { // 2. 执行时刻 [l, mid] 中的操作 for (auto& [l2, r2, x] : op[i]) sgt.change(l2, r2, {x, -inf, x, 0}); } sgt.change(1, n, {0, -inf, 0, -inf}); // 3. 在时刻 mid+1 重置 for (int i = mid + 1; i <= r; i++) { // 4. 执行时刻 (mid, r] 中的操作,并更新询问 for (auto& [l2, r2, x] : op[i]) sgt.change(l2, r2, {x, -inf, x, 0}); for (auto& [l1, r1, l2, r2, id] : R[i - mid - 1]) ans[id] = max(ans[id], get<1>(sgt.ask(l2, r2))); } for (int i = r; i > mid; i--) { // 5. 撤销时刻 (mid, r] 中的操作 reverse(op[i].begin(), op[i].end()); for (auto& [l2, r2, x] : op[i]) sgt.change(l2, r2, {-x, -inf, -x, 0}); reverse(op[i].begin(), op[i].end()); } solve(mid + 1, r, qr); // 5. 递归右侧 sgt.change(1, n, {0, -inf, 0, -inf}); // 6. 在时刻 mid 重置 for (int i = mid; i >= l; i--) { // 7. 撤销时刻 [l, mid] 中的操作,并更新询问 for (auto& [l1, r1, l2, r2, id] : L[i - l]) ans[id] = max(ans[id], get<1>(sgt.ask(l2, r2))); reverse(op[i].begin(), op[i].end()); for (auto& [l2, r2, x] : op[i]) sgt.change(l2, r2, {-x, -inf, -x, 0}); reverse(op[i].begin(), op[i].end()); } solve(l, mid, ql); // 7. 递归右侧 } void _main() { cin >> n >> m >> q; for (int i = 1, l1, l2, r1, r2, x; i <= m; i++) { cin >> l1 >> l2 >> r1 >> r2 >> x; op[l1].emplace_back(l2, r2, x); if (r1 < n) op[r1 + 1].emplace_back(l2, r2, -x); } for (int i = 1; i <= n; i++) sort(op[i].begin(), op[i].end(), [](const opt& a, const opt& b) -> bool { return get<2>(a) < get<2>(b); }); vector<query> vec; for (int i = 1, l1, l2, r1, r2; i <= q; i++) { cin >> l1 >> l2 >> r1 >> r2; vec.emplace_back(l1, r1, l2, r2, i); } sgt.build(), solve(1, n, vec); for (int i = 1; i <= q; i++) cout << ans[i] << '\n'; } ``` ::::: ### [CF448C Painting Fence](https://www.luogu.com.cn/problem/CF448C) > 给定序列 $a_i$,每次操作可将一个区间内的所有元素减 $1$,或将某个点的值直接置 $0$。 > > 操作过程中值不能为负,求使所有元素变为 $0$ 的最小操作次数。 > > $n \le 5000$,1 秒,512 MB。 :::::success[题解] 一个重要观察是:对于一个区间,要么直接推平(全部置 $0$),要么先减去区间最小值再从最小值处分裂。因为减到一半再使用单点置 $0$ 必然不如直接推平优。 基于此,可以设 $f(l,r,v)$ 为区间 $[l,r]$ 已经减去了 $v$ 后的答案,找到区间最小值 $a_x$,则: $$ f(l,r,v)=\min\left(r-l+1,f(l,x-1,v+a_x)+a_x-v+f(x+1,r,v+a_x)\right) $$ 这是一个最值分治,可以在小根笛卡尔树上 DP 做到 $O(n)$。 ::::: :::::info[代码] ```cpp line-numbers line-numbers int n, a[N], rt, l[N], r[N], sz[N], f[N]; void build() { stack<int> st; for (int i = 1; i <= n; i++) { while (!st.empty() && a[st.top()] > a[i]) l[i] = st.top(), st.pop(); if (!st.empty()) r[st.top()] = i; else rt = i; st.emplace(i); } } void dfs(int u, int h) { if (!u) return; dfs(l[u], a[u]), dfs(r[u], a[u]); sz[u] = sz[l[u]] + sz[r[u]] + 1; f[u] = min(sz[u], a[u] - h + f[l[u]] + f[r[u]]); } void _main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; build(), dfs(rt, 0); cout << f[rt]; } ``` ::::: ### [ABC282Ex Min + Sum](https://www.luogu.com.cn/problem/AT_abc282_h) > 给你两个序列 $a,b$,求出满足 > $$ > \min_{i=l}^r a_i + \sum_{i=l}^r b_i > $$ > 的 $(l,r)$ 对数。 > > $n \le 2 \times 10^5$,2 秒,1024 MB。 :::::success[题解] 注意到题面里统计的是 $\min$ 相关的信息,考虑最值分治。对于当前处理的区间 $[l,r]$,找到区间最小值 $a_m$,然后对 $[l,m),(m,r]$ 分治。 在统计区间的贡献时,我们钦定 $i \in [l,m],j \in [m,r]$,统计 $(i,j)$ 的数目,则最小值固定为 $a_m$。设 $b$ 的前缀和为 $p$,则须满足 $p_j-p_{i-1} \ge S-a_m$。 枚举 $i$ 统计 $j$ 的数目,由于 $p$ 单调不降,直接做一个二分即可。 采用类似于启发式合并的思想,每次枚举短的一边算答案,则复杂度满足 $T(n)=2T\left(\dfrac{n}{2}\right)+O(n \log n)$,得 $T(n)=O(n \log^2 n)$。 ::::: :::::info[代码] ```cpp line-numbers line-numbers #define int long long const int N = 2e5 + 5; using node = pair<int, int>; int n, s, a[N], b[N], p[N]; node st[20][N]; node ask(int l, int r) { int k = lg(r - l + 1); return min(st[k][l], st[k][r - (1 << k) + 1]); } int solve(int l, int r) { if (l > r) return 0; if (l == r) return a[l] + b[l] <= s; auto [mn, mid] = ask(l, r); int res = solve(l, mid - 1) + solve(mid + 1, r); if (mid - l < r - mid) { for (int i = l; i <= mid; i++) res += upper_bound(p + mid, p + r + 1, s - mn + p[i - 1]) - (p + mid); } else { for (int j = mid; j <= r; j++) res += (p + mid) - lower_bound(p + l - 1, p + mid, p[j] - s + mn); } return res; } void _main() { cin >> n >> s; for (int i = 1; i <= n; i++) cin >> a[i], st[0][i] = {a[i], i}; for (int i = 1; (1 << i) <= n; i++) { for (int j = 1; j + (1 << i) - 1 <= n; j++) st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]); } for (int i = 1; i <= n; i++) cin >> b[i], p[i] = p[i - 1] + b[i]; cout << solve(1, n); } ``` ::::: ### [CF232E Quick Tortoise](https://www.luogu.com.cn/problem/CF232E) > 给你一个 $n \times m$ 的网格,网格上有障碍和空地两种,一次移动只能向右或向下。$q$ 次询问是否能从 $(x_1,y_1)$ 走到 $(x_2,y_2)$。 > > $n, m \le 500$,$q \le 6 \times 10^5$,1.5 秒,500 MB。 :::::success[题解] 先乱写一个 DP,设 $f_{x,y}$ 表示 $(x,y)$ 能否走到,转移就是 $f_{x,y} \to f_{x+1,y}, f_{x,y} \to f_{x,y+1}$,视 $n,m$ 同阶则直接做为 $O(qn^2)$。 考虑套网格图分治,每次沿着长边分裂,从中线上的每个点出发跑 DP。具体地,我们将左上角的 DP 反过来跑,右下角的 DP 正着跑,然后更新询问。 复杂度 $O(n^3 +nq)$,在本题[卡常严重](https://codeforces.com/contest/232/submission/365954672),难以通过,需要进一步优化。 注意到本题是可行性 DP,这启示我们不要对中线上每个点单独 DP,而是应该将中线作为整体进行 DP,并且寻求 bitset 优化。 重设状态为:$f_{x,y,k}$ 表示从 $(x,y)$ 出发,能否到达中线上的第 $k$ 个点。将 $f$ 的第三维开成 bitset,也就是用 $F_{x,y}$ 记录状态。类似定义 $G_{x,y}$。 - 以 $F_{x,y}$ 为例,转移形如 $F_{x,y} \gets F_{x+1,y} \cup F_{x,y+1}$。 - 查询等价于 $F_{x_1,y_1} \cap G_{x_2,y_2} \ne \varnothing$。 简单分析一下可以知道现在的复杂度是 $O\left(\dfrac{n^3+nq}{w}\right)$ 的,可以通过。 ::::: :::::info[代码] ```cpp line-numbers line-numbers const int N = 505, Q = 6e5 + 5; using query = tuple<int, int, int, int, int>; // {x1, y1, x2, y2, id} int n, m, q; char s[N][N]; bool ans[Q]; bitset<N> F[N][N], G[N][N]; void solve(int lx, int rx, int ly, int ry, const vector<query>& q) { if (lx > rx || ly > ry || q.empty()) return; if (rx - lx > ry - ly) { int mid = (lx + rx) >> 1; vector<query> ql, qr, qc; for (auto& [x1, y1, x2, y2, id] : q) { if (x1 < mid && x2 < mid) ql.emplace_back(x1, y1, x2, y2, id); else if (mid < x1 && mid < x2) qr.emplace_back(x1, y1, x2, y2, id); else qc.emplace_back(x1, y1, x2, y2, id); } // for (int y = ly; y <= ry; y++) update(lx, rx, ly, ry, mid, y, qc); for (int y = ry; y >= ly; y--) { F[mid][y].reset(); if (s[mid][y] == '#') continue; F[mid][y].set(y - ly); if (y < ry) F[mid][y] |= F[mid][y + 1]; } for (int y = ly; y <= ry; ++y) { G[mid][y].reset(); if (s[mid][y] == '#') continue; G[mid][y].set(y - ly); if (y > ly) G[mid][y] |= G[mid][y - 1]; } for (int x = mid - 1; x >= lx; --x) { for (int y = ry; y >= ly; --y) { F[x][y].reset(); if (s[x][y] == '#') continue; F[x][y] = F[x + 1][y]; if (y < ry) F[x][y] |= F[x][y + 1]; } } for (int x = mid + 1; x <= rx; ++x) { for (int y = ly; y <= ry; ++y) { G[x][y].reset(); if (s[x][y] == '#') continue; G[x][y] = G[x - 1][y]; if (y > ly) G[x][y] |= G[x][y - 1]; } } for (auto& [x1, y1, x2, y2, id] : qc) { if ((F[x1][y1] & G[x2][y2]).any()) ans[id] = 1; } solve(lx, mid - 1, ly, ry, ql), solve(mid + 1, rx, ly, ry, qr); } else { int mid = (ly + ry) >> 1; vector<query> ql, qr, qc; for (auto& [x1, y1, x2, y2, id] : q) { if (y1 < mid && y2 < mid) ql.emplace_back(x1, y1, x2, y2, id); else if (mid < y1 && mid < y2) qr.emplace_back(x1, y1, x2, y2, id); else qc.emplace_back(x1, y1, x2, y2, id); } // for (int x = lx; x <= rx; x++) update(lx, rx, ly, ry, x, mid, qc); for (int x = rx; x >= lx; --x) { F[x][mid].reset(); if (s[x][mid] == '#') continue; F[x][mid].set(x - lx); if (x < rx) F[x][mid] |= F[x + 1][mid]; } for (int x = lx; x <= rx; ++x) { G[x][mid].reset(); if (s[x][mid] == '#') continue; G[x][mid].set(x - lx); if (x > lx) G[x][mid] |= G[x - 1][mid]; } for (int y = mid - 1; y >= ly; --y) { for (int x = rx; x >= lx; --x) { F[x][y].reset(); if (s[x][y] == '#') continue; F[x][y] = F[x][y + 1]; if (x < rx) F[x][y] |= F[x + 1][y]; } } for (int y = mid + 1; y <= ry; ++y) { for (int x = lx; x <= rx; ++x) { G[x][y].reset(); if (s[x][y] == '#') continue; G[x][y] = G[x][y - 1]; if (x > lx) G[x][y] |= G[x - 1][y]; } } for (auto& [x1, y1, x2, y2, id] : qc) { if ((F[x1][y1] & G[x2][y2]).any()) ans[id] = 1; } solve(lx, rx, ly, mid - 1, ql), solve(lx, rx, mid + 1, ry, qr); } } void _main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> (s[i] + 1); cin >> q; vector<query> vec; for (int i = 1, x1, y1, x2, y2; i <= q; i++) { cin >> x1 >> y1 >> x2 >> y2; vec.emplace_back(x1, y1, x2, y2, i); } solve(1, n, 1, m, vec); for (int i = 1; i <= q; i++) cout << (ans[i] ? "Yes\n" : "No\n"); } ``` ::::: ### [P9040 [PA 2021] Desant 2](https://www.luogu.com.cn/problem/P9040) > 给定一个长为 $n$ 的序列 $a$。有 $q$ 次询问,对区间 $[l,r]$ 求解如下问题: > > > 对区间 $[l,r]$,将其划分为若干不相交连续段,每段长度恰好为 $k$,允许最多一个元素不属于任何段,最大化各段元素和之和。 > > $k, n, q \le 3 \times 10^5$,10 秒,1024 MB。 :::::success[题解] 记 $p_i$ 为 $a_i$ 的前缀和,设 $f_i$ 为考虑到第 $i$ 个元素的最大得分,容易写出 DP 转移: $$ f_i =\max(f_{i-1},f_{i-k}+s_i-s_{i-k}) $$ 对于每次询问,令 $f_{l-1} \gets 0$ 然后跑 DP,视 $n,q$ 同阶,复杂度 $O(n^2)$。 如果直接用矩阵优化可以做到 $O(nk^3)$,二区间合并可以做到 $O(nk \log n)$,和我一样没有前途。 将上述 DP 转移视为一个自动机,可以建成如下 DAG: - 边 $i \to i+1$,权值为 $0$; - 边 $i \to i+k$,权值为 $p_{i+k}-p_i$。 这样,问题等价于:询问从 $l-1$ 到 $r$ 的最长路。 我们观察一下这个图的形态: ![](https://cdn.luogu.com.cn/upload/image_hosting/rhge7hre.png) (借用了[这篇题解](https://www.luogu.com.cn/article/vx6i6dsm)里的图) 这个 DAG 的结构相当于一个 $k \times \left\lfloor n/k\right \rfloor$ 的网格图加上了若干斜边,自然想到网格图分治。 考虑一下怎么处理斜边。注意到这些斜边只会在第一次按行分治时起作用,因此可以在这一层单独暴力处理斜边,不影响整体复杂度。 我们可以用简单的 DP 跑出中线向两侧的最短路,复杂度就是 $O((n+q)\sqrt{n})$ 的。 ::::: :::::info[代码] ```cpp line-numbers line-numbers const int N = 6e5 + 5; const int64 inf = 1e18; int n, k, q; int64 a[N], ans[N], dis[N]; using query = tuple<int, int, int, int, int>; // {x1, y1, x2, y2, id} vector<query> qry; void update(int lx, int rx, int ly, int ry, int sx, int sy, const vector<query>& q) { int s = sx * k + sy; for (int x = lx; x <= rx; x++) { for (int y = ly; y <= ry; y++) dis[x * k + y] = -inf; } dis[s] = 0; auto chk = [&](int i) -> bool {return lx <= i / k && i / k <= rx && ly <= i % k && i % k <= ry;}; for (int x = sx; x >= lx; x--) { for (int y = ry; y >= ly; y--) { int i = x * k + y; if (i > s) continue; if (chk(i + 1)) dis[i] = max(dis[i], dis[i + 1]); if (chk(i + k)) dis[i] = max(dis[i], dis[i + k] + a[i + k] - a[i]); } } for (int x = sx; x <= rx; x++) { for (int y = ly; y <= ry; y++) { int i = x * k + y; if (i < s) continue; if (chk(i + 1)) dis[i + 1] = max(dis[i + 1], dis[i]); if (chk(i + k)) dis[i + k] = max(dis[i + k], dis[i] + a[i + k] - a[i]); } } for (const auto& [x1, y1, x2, y2, id] : q) { if (x1 * k + y1 > s || x2 * k + y2 < s) continue; ans[id] = max(ans[id], dis[x1 * k + y1] + dis[x2 * k + y2]); } } void solve(int lx, int rx, int ly, int ry, vector<query> q) { if (lx > rx || ly > ry || q.empty()) return; if (rx - lx > ry - ly) { int mid = (lx + rx) >> 1; for (int y = ly; y <= ry; y++) update(lx, rx, ly, ry, mid, y, q); vector<query> ql, qr; for (const auto& [x1, y1, x2, y2, id] : q) { if (x1 < mid && x2 < mid) ql.emplace_back(x1, y1, x2, y2, id); if (mid < x1 && mid < x2) qr.emplace_back(x1, y1, x2, y2, id); } solve(lx, mid - 1, ly, ry, ql), solve(mid + 1, rx, ly, ry, qr); } else { int mid = (ly + ry) >> 1; if (ly == 0 && ry == k - 1) { // 斜边 for (int x = lx; x <= rx; x++) update(lx, rx, ly, ry, x, 0, q); } for (int x = lx; x <= rx; x++) update(lx, rx, ly, ry, x, mid, q); vector<query> ql, qr; for (const auto& [x1, y1, x2, y2, id] : q) { if (y1 < mid && y2 < mid) ql.emplace_back(x1, y1, x2, y2, id); if (mid < y1 && mid < y2) qr.emplace_back(x1, y1, x2, y2, id); } solve(lx, rx, ly, mid - 1, ql), solve(lx, rx, mid + 1, ry, qr); } } void _main() { cin >> n >> k >> q; for (int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1]; for (int i = 1, l, r; i <= q; i++) { cin >> l >> r, l--; qry.emplace_back(l / k, l % k, r / k, r % k, i); } solve(0, n / k, 0, k - 1, qry); for (int i = 1; i <= q; i++) cout << ans[i] << '\n'; } ``` ::::: ### [P8182 「EZEC-11」雪的魔法](https://www.luogu.com.cn/problem/P8182) > 给定长度为 $n$ 的序列 $a$,有 $q$ 次询问。 > > 一次操作可选择一个长度不超过 $k$ 的子区间,将其中所有数减一。 > > 求将区间 $[l,r]$ 内所有数变为 $0$ 的最小操作次数。 > > $k, n, q \le 10^5$,1.2 秒,512 MB。 :::::success[题解] > 本题在笔者的另一篇文章[《十二重铲雪法》](https://www.luogu.com.cn/article/g8tpeakq)中亦有记载。 这种问题笔者称之为“铲雪题”。下面直接给出本题的等价问题: > 将区间中每个位置赋一个权值 $w_i \in \{-1,0,1\}$,满足任意长度不超过 $k$ 的子区间的权值和不超过 $1$。最大化 $\sum a_i w_i$。 ::::info[为什么] 前置知识:线性规划、对偶原理。 设 $\mathcal I$ 表示所有路径,对每条路径 $S$ 给出一个非负整数 $x_S$ 表示 $S$ 被经过的次数,原问题即: $$ \begin{aligned} \min & \sum _{S \in \mathcal{I}} x_S\\ \text{subject to } & \sum_{u \in S} x_S=a_u, \\ & x_S \ge 0. \end{aligned} $$ 拆成不等式以得到标准形式: $$ \begin{aligned} \min & \sum _{S \in \mathcal{I}} x_S\\ \text{subject to } & \sum_{u \in S} x_S \ge a_u, \\ & \sum_{u \in S} -x_S \ge -a_u, \\ & x_S \ge 0. \end{aligned} $$ 得到对偶问题 $$ \begin{aligned} \max & \sum _{u} a_u(p_u-q_u)\\ \text{subject to } & \sum_{u \in S} (p_u-q_u) \le 1, \\ & p_u,q_u \ge 0. \end{aligned} $$ 换元,令 $w_u=p_u-q_u$,问题变为 $$ \begin{aligned} \max & \sum _{u} a_uw_u\\ \text{subject to } & \sum_{u \in S} w_u \le 1. \end{aligned} $$ 用自然语言表述这个问题,相当于找到一组整数 $w_u$,对所有满足条件的路径,$w_u$ 之和不大于 $1$,最大化 $a_uw_u$ 的和。 显然 $w_u \le 1$。同时对 $w_u \le -2$,总能调整法找到所有 $w_u \ge -1$ 的解。因此 $w_u \in \{-1,0,1\}

::::

考虑 k \ge n 的情况,此时原问题等价于积木大赛,答案即所有正差分之和,也即 \sum \max(0,a_i-a_{i-1})。

我们称:按照积木大赛得到的答案是平凡的。对于对偶问题,这样的答案会偏小,因为对偶问题的限制是相对松的。

设 f_i 为考虑到第 i 个位置的答案,初始 f_l=a_l。对于 i=l+1,l+2,\cdots,r,有如下转移方程:

f_i=\max(f_{i-1}+\max(0,a_i-a_{i-1}),f_{i-k}+a_i)

其中,f_{i-1}+\max(0,a_i-a_{i-1}) 是平凡的。而 f_{i-k}+a_i 的意思是将 [i-k+1,i-1] 中的权值全部置 0,并且令 w_i=1。

这个 DP 的正确性不是很显然。但是仔细思考一下,对于一个不平凡的情况,如果 [i-k+1,i-1] 中存在非零权值,那么这总能规约到一个平凡情况。因此,我们得到了一个 O(nq) 做法。

观察一下这个 DP 式子,可以继续使用和上一题相同的网格图分治优化 DP。唯一不同的点在于起点 l 带了点权,加上去即可。复杂度 O((n+q) \sqrt{n})。

:::::

:::::info[代码]

const int N = 2e5 + 5;
const int64 inf = 1e18;

int n, k, q;
int64 a[N], ans[N], dis[N];
using query = tuple<int, int, int, int, int>;  // {x1, y1, x2, y2, id}
vector<query> qry;

void update(int lx, int rx, int ly, int ry, int sx, int sy, const vector<query>& q) {
    int s = sx * k + sy;
    for (int x = lx; x <= rx; x++) {
        for (int y = ly; y <= ry; y++) dis[x * k + y] = -inf;
    }
    dis[s] = 0;
    auto chk = [&](int i) -> bool {return lx <= i / k && i / k <= rx && ly <= i % k && i % k <= ry;};
    for (int x = sx; x >= lx; x--) {
        for (int y = ry; y >= ly; y--) {
            int i = x * k + y;
            if (i > s) continue;
            if (chk(i + 1)) dis[i] = max(dis[i], dis[i + 1] + max(0LL, a[i + 1] - a[i]));
            if (chk(i + k)) dis[i] = max(dis[i], dis[i + k] + a[i + k]);
        }
    }
    for (int x = sx; x <= rx; x++) {
        for (int y = ly; y <= ry; y++) {
            int i = x * k + y;
            if (i < s) continue;
            if (chk(i + 1)) dis[i + 1] = max(dis[i + 1], dis[i] + max(0LL, a[i + 1] - a[i]));
            if (chk(i + k)) dis[i + k] = max(dis[i + k], dis[i] + a[i + k]);
        }
    }
    for (const auto& [x1, y1, x2, y2, id] : q) {
        if (x1 * k + y1 > s || x2 * k + y2 < s) continue;
        ans[id] = max(ans[id], a[x1 * k + y1] + dis[x1 * k + y1] + dis[x2 * k + y2]);
    }
}

void solve(int lx, int rx, int ly, int ry, vector<query> q) {
    if (lx > rx || ly > ry || q.empty()) return;
    if (rx - lx > ry - ly) {
        int mid = (lx + rx) >> 1;
        for (int y = ly; y <= ry; y++) update(lx, rx, ly, ry, mid, y, q);
        vector<query> ql, qr;
        for (const auto& [x1, y1, x2, y2, id] : q) {
            if (x1 < mid && x2 < mid) ql.emplace_back(x1, y1, x2, y2, id);
            if (mid < x1 && mid < x2) qr.emplace_back(x1, y1, x2, y2, id);
        }
        solve(lx, mid - 1, ly, ry, ql), solve(mid + 1, rx, ly, ry, qr);
    } else {
        int mid = (ly + ry) >> 1;
        if (ly == 0 && ry == k - 1) {  // 斜边
            for (int x = lx; x <= rx; x++) update(lx, rx, ly, ry, x, 0, q);
        }
        for (int x = lx; x <= rx; x++) update(lx, rx, ly, ry, x, mid, q);
        vector<query> ql, qr;
        for (const auto& [x1, y1, x2, y2, id] : q) {
            if (y1 < mid && y2 < mid) ql.emplace_back(x1, y1, x2, y2, id);
            if (mid < y1 && mid < y2) qr.emplace_back(x1, y1, x2, y2, id);
        }
        solve(lx, rx, ly, mid - 1, ql), solve(lx, rx, mid + 1, ry, qr);
    }
}

void _main() {
    cin >> n >> k >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1, l, r; i <= q; i++) {
        cin >> l >> r;
        qry.emplace_back(l / k, l % k, r / k, r % k, i);
    }
    solve(0, n / k, 0, k - 1, qry);
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
} 

:::::

QOJ888 Travel around China

给出一个 n \times m 的网格图,点有点权。可以上下左右走,求任意点对间最短路之和,对 10^9+7 取模。

:::::success[题解]

网格图最短路启示我们使用网格图分治,n=3 告诉我们只用对行分治,每一次中线上有且仅有三个点。

对中线两侧的点对计算贡献。容易从中线向两端跑出最短路,分别记为 f_{0/1/2, x, y} 和 g_{0/1/2,x,y}。此时 (x_1,y_1) \to (x_2,y_2) 的最短路即

\min_{i \in [0, 2]} (f_{i,x_1,y_1}+g_{i,x_2,y_2})

由于 i 的取值仅有 3 种,考虑直接讨论拆掉 \min。不妨钦定 i=0 最小,则:

发现上述条件其实与 (x_1,y_1), (x_2, y_2) 无关。两个条件移项后是一个二维偏序结构,如果用二维平面来刻画这一问题,相当于有若干点,需要查询一个矩形中点的权值和。

将 f,g 中的值离散化后,容易树状数组配合扫描线解决此问题。

钦定 i=1,i=2 最小的情形基本同理。但是注意直接按上述算法会把相等的情况算重,需要注意取等条件有所不同:

现在答案还漏算了同一列的情况。对于同列点 (x_1,y_0) \to (x_2, y_0),我们预处理列内部的最短路,前缀最短路,后缀最短路,根据这些合并答案即可。

综上,我们得到的算法复杂度满足 T(m)=2T\left(\dfrac{m}{2}\right)+O(m \log m),得 T(m)=O(m \log^2 m),可以通过。

:::::

:::::info[代码]

const int N = 1.5e5 + 5;
const i64 inf = 1e18;
using node = array<i64, 3>;
using point = tuple<i64, i64, i64, i64, int>;  // {x, y, f, g, type}

int n, m, w[3][N];
i64 col[3][3][N], pre[3][3][N], suf[3][3][N], L[3][3][N], R[3][3][N];

struct BIT {
    int n, cnt[N * 3]; mint sum[N * 3];
    void init(int _n) {n = _n, fill(cnt, cnt + n + 1, 0), fill(sum, sum + n + 1, 0);}
    void add(int x, mint c) {
        for (; x <= n; x += lowbit(x)) cnt[x]++, sum[x] += c;
    }
    pair<int, mint> ask(int x) {
        int c = 0; mint s = 0;
        for (; x >= 1; x -= lowbit(x)) c += cnt[x], s += sum[x];
        return {c, s};
    }
} B;

void prework() {
    for (int c = 1; c <= m; c++) 
        for (int i = 0; i < 3; i++) 
            for (int j = 0; j < 3; j++) {
                for (int k = min(i, j); k <= max(i, j); k++) col[i][j][c] += w[k][c];
                pre[i][j][c] = suf[i][j][c] = col[i][j][c];
            }
    for (int c = 2; c <= m; c++) 
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) 
        for (int x = 0; x < 3; x++) for (int y = 0; y < 3; y++) {
            i64 val = pre[x][y][c - 1] + w[x][c] + (x == y ? 0 : w[y][c]);
            pre[i][j][c] = min(pre[i][j][c], col[i][x][c] - w[x][c] + val + col[y][j][c] - w[y][c]);
        }
    for (int c = m - 1; c >= 1; c--) 
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) 
        for (int x = 0; x < 3; x++) for (int y = 0; y < 3; y++) {
            i64 val = suf[x][y][c + 1] + w[x][c] + (x == y ? 0 : w[y][c]);
            suf[i][j][c] = min(suf[i][j][c], col[i][x][c] - w[x][c] + val + col[y][j][c] - w[y][c]);
        }
}
mint calc(vector<node>& a, vector<node>& b) {
    mint res = 0;
    for (int i = 0; i < 3; i++) {
        int j = i == 0 ? 1 : 0, k = i == 2 ? 1 : 2;
        vector<point> p;
        vector<i64> d;  // 离散化
        for (auto& u : a) {
            p.emplace_back(u[i] - u[j], u[i] - u[k], u[i], 0, 0);
            d.emplace_back(u[i] - u[k]);
        }
        for (auto& u : b) {
            p.emplace_back(u[j] - u[i], u[k] - u[i], 0, u[i], 1);
            d.emplace_back(u[k] - u[i]);
        }
        sort(d.begin(), d.end()), d.erase(unique(d.begin(), d.end()), d.end());
        auto idx = [&](i64 x) -> int {
            return lower_bound(d.begin(), d.end(), x) - d.begin() + 1;
        };
        sort(p.begin(), p.end(), [&](const point& a, const point& b) -> bool {
            if (get<0>(a) != get<0>(b)) return get<0>(a) < get<0>(b);
            return i > j ? get<4>(a) > get<4>(b) : get<4>(a) < get<4>(b);  // x 维严格偏序
        });
        B.init(d.size() + 1);
        for (auto [x, y, f, g, type] : p) {
            y = idx(y);
            if (type == 0) {
                B.add(y, f);
            } else {
                if (i > k) y--;  // y 维严格偏序
                if (y <= 0) continue;
                auto [cnt, sum] = B.ask(y);
                res += sum + mint(cnt) * g;
            }
        }
    } return res;
}
mint solve(int l, int r) {
    if (l == r) return 0;
    int mid = (l + r) >> 1;
    mint res = solve(l, mid) + solve(mid + 1, r);
    for (int i = 0; i < 3; i++) 
        for (int j = 0; j < 3; j++) L[i][j][mid] = col[i][j][mid];
    for (int c = mid - 1; c >= l; c--) 
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) {
            L[i][j][c] = inf;
            for (int x = 0; x < 3; x++) L[i][j][c] = min(L[i][j][c], L[x][j][c + 1] + col[i][x][c]);
        }
    for (int i = 0; i < 3; i++) 
        for (int j = 0; j < 3; j++) R[i][j][mid + 1] = col[i][j][mid + 1];
    for (int c = mid + 2; c <= r; c++) 
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) {
            R[i][j][c] = inf;
            for (int x = 0; x < 3; x++) R[i][j][c] = min(R[i][j][c], R[i][x][c - 1] + col[x][j][c]);
        }
    vector<node> vl, vr;
    for (int c = l; c <= mid; c++) for (int i = 0; i < 3; i++) {
        node u; 
        for (int k = 0; k < 3; k++) {
            u[k] = inf;
            for (int j = 0; j < 3; j++) u[k] = min(u[k], pre[i][j][c] + L[j][k][c] - w[j][c]);
        }
        vl.emplace_back(u);
    }
    for (int c = mid + 1; c <= r; c++) for (int i = 0; i < 3; i++) {
        node u; 
        for (int k = 0; k < 3; k++) {
            u[k] = inf;
            for (int j = 0; j < 3; j++) u[k] = min(u[k], suf[i][j][c] + R[k][j][c] - w[j][c]);
        }
        vr.emplace_back(u);
    }
    return res + calc(vl, vr);
}

void _main() {
    cin >> n >> m;
    for (int i = 0; i < 3; i++) {
        for (int j = 1; j <= m; j++) cin >> w[i][j];
    }
    prework();
    mint res = solve(1, m);
    for (int c = 1; c <= m; c++) 
        for (int i = 0; i < 3; i++) 
            for (int j = i + 1; j < 3; j++) {
                i64 d = inf;
                for (int k = 0; k < 3; k++) d = min(d, pre[i][k][c] + suf[k][j][c] - w[k][c]);
                res += d;
            }
    cout << res * 2;
}

:::::

P4178 Tree

给定一棵 n 个节点的树,每条边有边权,求出树上两点距离小于等于 k 的点对数量。

:::::success[题解]

点分治起手,考虑如何统计跨过根节点的点对数目。

如果使用分别统计的处理方法,我们需要维护一棵平衡树来支持排名查询,代码难度稍大。

下面演示使用容斥的处理方法:先计算当前子树内所有合法点对数,再减去每个儿子内部的点对数。计算儿子内的点对数时,我们钦定点对在其中合并。

点对数的具体计算可以使用双指针。按距离排序后,我们要统计 d_i+d_j \le k 的数目,这具有单调性,可以通过指针移动维护。

使用正确的实现,复杂度为 O(n \log^2 n)。

:::::

:::::info[代码]

const int N = 4e4 + 5;
int n, k, cur, ctr, ans, sz[N], vis[N];
vector<pair<int, int>> e[N];

void dfs1(int u, int fa) {   // 找重心
    sz[u] = 1;
    for (auto [v, w] : e[u]) {
        if (v == fa || vis[v]) continue;
        dfs1(v, u), sz[u] += sz[v];
    }
    if (!ctr && 2 * sz[u] >= cur) ctr = u;
}
void dfs2(int u, int fa) {   // 统计子树大小
    cur++;
    for (auto [v, w] : e[u]) if (!vis[v] && v != fa) dfs2(v, u);
}
void dfs3(int u, int fa, int dep, vector<int>& vec) {   // 统计距离
    vec.emplace_back(dep);
    for (auto [v, w] : e[u]) {
        if (v == fa || vis[v]) continue;
        dfs3(v, u, dep + w, vec);
    }
}

int calc(int u, int d) {
    vector<int> vec; dfs3(u, -1, d, vec);
    sort(vec.begin(), vec.end());
    int res = 0;
    for (int i = 0, j = vec.size() - 1; i < j; ) {
        if (vec[i] + vec[j] <= k) res += j - i, i++;
        else j--;
    } return res;
}
void solve(int u) {
    vis[u] = true, ans += calc(u, 0);
    for (auto [v, w] : e[u]) {
        if (vis[v]) continue;
        ans -= calc(v, w);
        cur = ctr = 0, dfs2(v, u), dfs1(v, u), solve(ctr);
    }
}

void _main() {
    cin >> n;
    for (int i = 1, u, v, w; i < n; i++) {
        cin >> u >> v >> w;
        e[u].emplace_back(v, w), e[v].emplace_back(u, w);
    }
    cin >> k, cur = n, dfs1(1, -1);
    solve(ctr), cout << ans;
}

:::::

CF293E Close Vertices

给定一棵 n 个节点的树,边带权,给出 X,Y,求树上边数 \le X 且距离 \le Y 的路径数。

:::::success[题解]

对 Y 的限制做点分治,完全套用上一题的做法。

对 X 的限制用数据结构维护。在计算跨过根节点的路径时,我们先全部插入该数据结构中,在双指针移动过程中进行删除,同时支持前缀查询。可以使用树状数组来维护。

做完了,复杂度 O(n \log^2 n)。

:::::

:::::info[代码]

const int N = 1e5 + 5;
int n, X, Y, cur, ctr, sz[N], vis[N];
i64 ans, tr[N];
void add(int x, i64 c) {
    for (x++; x < N; x += lowbit(x)) tr[x] += c;
}
i64 ask(int x) {
    i64 res = 0;
    for (x++; x >= 1; x -= lowbit(x)) res += tr[x];
    return res;
}
vector<pair<int, int>> e[N];

void dfs1(int u, int fa) {   // 找重心
    sz[u] = 1;
    for (auto [v, w] : e[u]) {
        if (v == fa || vis[v]) continue;
        dfs1(v, u), sz[u] += sz[v];
    }
    if (!ctr && 2 * sz[u] >= cur) ctr = u;
}
void dfs2(int u, int fa) {   // 统计子树大小
    cur++;
    for (auto [v, w] : e[u]) if (!vis[v] && v != fa) dfs2(v, u);
}
void dfs3(int u, int fa, int dep, int dis, vector<pair<int, int>>& vec) {   // 统计深度 & 距离
    vec.emplace_back(dis, dep);
    for (auto [v, w] : e[u]) {
        if (v == fa || vis[v]) continue;
        dfs3(v, u, dep + 1, dis + w, vec);
    }
}

i64 calc(int u, int dep, int dis) {
    vector<pair<int, int>> vec; dfs3(u, -1, dep, dis, vec);
    sort(vec.begin(), vec.end());
    for (auto [_, d] : vec) add(d, 1);
    i64 res = 0;
    int i = 0, j = vec.size() - 1;
    while (i < j) {
        auto [dis1, dep1] = vec[i]; auto [dis2, dep2] = vec[j];
        if (dis1 + dis2 <= Y) add(dep1, -1), res += ask(X - dep1), i++;
        else add(dep2, -1), j--;
    } 
    if (i == j) add(vec[i].second, -1);
    return res;
}
void solve(int u) {
    vis[u] = true, ans += calc(u, 0, 0);
    for (auto [v, w] : e[u]) {
        if (vis[v]) continue;
        ans -= calc(v, 1, w);
        cur = ctr = 0, dfs2(v, u), dfs1(v, u), solve(ctr);
    }
}

void _main() {
    cin >> n >> X >> Y;
    for (int u = 2, v, w; u <= n; u++) {
        cin >> v >> w;
        e[u].emplace_back(v, w), e[v].emplace_back(u, w);
    }
    cur = n, dfs1(1, -1);
    solve(ctr), cout << ans;
} 

:::::

P5311 [Ynoi2011] 成都七中

给你一个 n 个节点的无根树,点有颜色,q 次查询给出 l,r, x,求保留 [l,r] 中的节点后 x 所在连通块颜色数。

:::::success[题解]

记 S_{x,[l,r]} 为保留 [l,r] 后 x 的可达点集,有关键观察:\forall y \in S_{x,[l,r]}, S_{x,[l,r]}=S_{y,[l,r]}。

点分治起手,设分治中心为 c,则将 c 作为代表元求解子树中的问题。具体地,对于子树中的询问 (l,r,x),我们判断是否有 c \in S_{x,[l,r]},若满足条件则求解 S_{c,[l,r]} 的答案,若不满足则作为子问题分治处理。

现在问题转化为:求从 c 出发,只经过 [l,r] 的可达点集中的颜色数。

设 (u,v) 两点间的路径为 p_1,p_2,\cdots,p_k,则 (u,v) 可达当且仅当 \forall 1 \le i \le k, p_i \in [l,r],即 [\min p, \max p] \subseteq [l,r]。

于是从 c 开始自顶向下维护两个值 mx_u, mn_u,表示 u 到 c 的路径上的最大 / 最小编号,此时 u 带贡献的必要条件是 l \le mn_u \le mx_u \le r。用二维平面来刻画,将 (mn_u,mx_u) 作为一个点,问题即:在 x \le l, y\le r 的区域内数颜色。

将颜色去重后进行二维数点。对于同种颜色,若存在两点 (x_1,y_1),(x_2,y_2) 且 x_1 \le x_2, y_1 \le y_2,则 (x_2,y_2) 是无用的。去重以后,将查询按 l 降序排序,对 x 扫描线。

采用类似于 HH 的项链的处理方式,维护一个树状数组,同时记录每种颜色上一次出现的位置,激活新位置时要删除上一个位置。

按照上述过程实现,视 n,q,V 同阶复杂度 O(n \log^2 n)。

::::::

:::::info[代码]

const int N = 1e5 + 5;
using query = tuple<int, int, int, int>;  // {l, r, x, id}
using point = tuple<int, int, int>;  // {x, y, col}

struct BIT {
    int tr[N];
    void add(int x, int c) {
        for (; x < N; x += lowbit(x)) tr[x] += c;
    }
    int ask(int x) {
        int res = 0;
        for (; x >= 1; x -= lowbit(x)) res += tr[x];
        return res;
    }
} B;

int n, q, col[N], ans[N];
vector<int> e[N];

int ctr, cur, sz[N], vis[N];
void dfs1(int u, int fa) {
    sz[u] = 1;
    for (int v : e[u]) {
        if (v == fa || vis[v]) continue;
        dfs1(v, u), sz[u] += sz[v];
    }
    if (!ctr && 2 * sz[u] >= cur) ctr = u;
}
void dfs2(int u, int fa) {
    cur++;
    for (int v : e[u]) if (v != fa && !vis[v]) dfs2(v, u);
}

int mn[N], mx[N], bel[N];
void dfs3(int u, int fa, int minv, int maxv, int b, vector<int>& vec) {
    minv = min(minv, u), maxv = max(maxv, u);
    mn[u] = minv, mx[u] = maxv, bel[u] = b, vec.emplace_back(u);
    for (int v : e[u]) if (v != fa && !vis[v]) dfs3(v, u, minv, maxv, b, vec);
} 

int last[N];
vector<query> child[N];
vector<pair<int, int>> cp[N];
void update(int u, vector<query>& q, vector<pair<int, vector<query>>>& nxt) {
    vector<int> vec = {u};
    mn[u] = u, mx[u] = u, bel[u] = -1;
    for (int v : e[u]) {
        if (!vis[v]) dfs3(v, u, u, u, v, vec);
    }
    vector<query> now;
    for (auto& [l, r, x, id] : q) {
        if (l <= mn[x] && mx[x] <= r) now.emplace_back(l, r, x, id);
        else child[bel[x]].emplace_back(l, r, x, id);
    }
    for (int v : e[u]) {   // 下传询问
        if (vis[v] || child[v].empty()) continue;
        nxt.emplace_back(v, child[v]), child[v].clear();
    }

    // 扫描线
    vector<point> p;
    for (int v : vec) cp[col[v]].emplace_back(mn[v], mx[v]);
    for (int v : vec) {   // 去重
        if (cp[col[v]].empty()) continue;
        sort(cp[col[v]].begin(), cp[col[v]].end(), greater<pair<int, int>>());
        int ymin = 1e9;
        for (auto& [x, y] : cp[col[v]]) {
            if (y < ymin) ymin = y, p.emplace_back(x, y, col[v]);
        }
        cp[col[v]].clear();
    }
    sort(now.begin(), now.end(), greater<query>());
    sort(p.begin(), p.end(), greater<point>());

    int i = 0;
    vector<int> undo;
    for (auto& [l, r, x, id] : now) {
        for (; i < (int)p.size() && get<0>(p[i]) >= l; i++) {
            auto& [_, y, c] = p[i];
            if (last[c]) B.add(last[c], -1);
            last[c] = y, B.add(last[c], 1);
            undo.emplace_back(c);
        }
        ans[id] = B.ask(r);
    }
    for (int c : undo) if (last[c]) B.add(last[c], -1), last[c] = 0;
}

void solve(int u, vector<query>& q) {
    if (q.empty()) return;
    vis[u] = true;
    vector<pair<int, vector<query>>> nxt;
    update(u, q, nxt);
    for (auto& [v, vec] : nxt) {
        cur = ctr = 0, dfs2(v, u), dfs1(v, u);
        solve(ctr, vec);
    }
}

void _main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> col[i];
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        e[u].emplace_back(v), e[v].emplace_back(u);
    }
    vector<query> vec;
    for (int i = 1, l, r, x; i <= q; i++) {
        cin >> l >> r >> x;
        vec.emplace_back(l, r, x, i);
    }
    cur = n, dfs1(1, -1), solve(ctr, vec);
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n'; 
} 

:::::

P14012 [POCamp 2023] 枫树 / Maple Tree

交互题。交互库有一个大小为 n 的无根树,边带权。一次询问给出 a,b,c,查询 \text{dis}(a,b)<\text{dis}(a,c) 是否成立。保证任意两点距离不同,且节点度数 \le 3。还原树的形态。

:::::success[题解] 不妨将 1 作为根。令 a=1 后一次查询相当于比较 b,c 的深度,于是可以将所有点按照深度升序排序。

这得到的是一个拓扑序。考虑按拓扑序增量构造,一次加点就是加叶子,只需确定叶子的父亲。

另一个重要观察是,可以通过一次询问排除一半子树。具体地,对于叶子 x 和边 (u,v),询问 \text{dis}(u,x) 和 \text{dis}(v,x) 可以确定 x 在 u 子树还是 v 子树中。

注意到树是三度化的,这恰好为边分治提供了条件。于是我们用边分治挂叶子,一次加点可以做到 \log n 次询问。这样总询问次数就是 2n \log n 的了,可以通过。

:::::info[代码]

const int N = 1005;
int n, p[N], sz[N], vis[N];
vector<int> e[N];
bool ask(int x, int y, int z) {
    cout << "? " << y << ' ' << z << ' ' << x << endl;
    char c; cin >> c;
    return c == 'A';
}

void dfs1(int u, int fa) {
    sz[u] = 1;
    for (int v : e[u]) {
        if (v == fa || vis[v]) continue;
        dfs1(v, u), sz[u] += sz[v];
    }
}
void dfs2(int u, int fa) {
    vis[u] = true;
    for (int v : e[u]) {
        if (v == fa || vis[v]) continue; 
        dfs2(v, u);
    }
}
void solve(int x, int u) {
    dfs1(u, -1); int c = sz[u];
    if (c == 1) {
        e[u].emplace_back(x), e[x].emplace_back(u);
        return;
    }
    int p = -1, q = -1, mw = 1e9;
    function<void(int, int)> dfs = [&](int u, int fa) -> void {
        for (int v : e[u]) {
            if (v == fa || vis[v]) continue;
            int w = max(sz[v], c - sz[v]);
            if (w < mw) p = u, q = v, mw = w;
            dfs(v, u);
        }
    };
    dfs(u, -1);
    if (ask(x, p, q)) dfs2(q, p), solve(x, p);
    else dfs2(p, q), solve(x, q);
}

void _main() {
    cin >> n;
    iota(p + 1, p + n + 1, 1);
    stable_sort(p + 2, p + n + 1, [](int x, int y) -> bool {
        return ask(1, x, y);
    });
    for (int i = 2; i <= n; i++) {
        fill(vis + 1, vis + n + 1, 0);
        solve(p[i], 1);
    }
    cout << "!\n";
    for (int u = 1; u <= n; u++) 
        for (int v : e[u]) if (u < v) cout << u << ' ' << v << '\n';
    cout << endl;
}

:::::

P4219 [BJOI2014] 大融合

维护一个 n 个点的森林,初始两两无边。支持加边,查询有几条路径经过给定的边。

:::::success[题解]

考虑查询操作的答案,忽略边 (u,v) 后,答案为 u 所在连通块大小乘 v 所在连通块大小。

不妨将“忽略”看成是一次删边,在查询后再加边。具体地,对于一次查询,我们新建三个时刻,在时刻 k 删边,时刻 k+1 查询,时刻 k+2 加边。

可以用线段树分治 + 可撤销并查集维护,视 n,q 同阶复杂度 O(n \log^2 n)。

:::::

:::::info[代码]

const int N = 3e5 + 5;
int n, q, k;
struct unionfind {
    int fa[N], sz[N];
    stack<int> st;
    unionfind() {iota(fa, fa + N, 0), fill(sz, sz + N, 1);}
    int find(int x) {return x == fa[x] ? x : find(fa[x]);}
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        fa[x] = y, sz[y] += sz[x], st.emplace(x);
    }
    void undo(int x) {
        while ((int) st.size() > x) {
            int u = st.top(); st.pop();
            if (u != fa[u]) sz[fa[u]] -= sz[u], fa[u] = u;
        }
    }
} dsu;

#define ls (rt << 1)
#define rs (rt << 1 | 1)
vector<pair<int, int>> val[N << 2];
void insert(int tl, int tr, const pair<int, int>& c, int l = 1, int r = N, int rt = 1) {
    if (tl <= l && r <= tr) return val[rt].emplace_back(c), void();
    int mid = (l + r) >> 1;
    if (tl <= mid) insert(tl, tr, c, l, mid, ls);
    if (tr > mid) insert(tl, tr, c, mid + 1, r, rs);
}

map<pair<int, int>, int> last;
pair<int, int> ask[N];
i64 cnt, ans[N];

void solve(int l = 1, int r = N, int rt = 1) {
    int step = dsu.st.size();
    for (auto [u, v] : val[rt]) dsu.unite(u, v);
    if (l == r) {
        auto [u, v] = ask[l];
        if (u != 0) {
            u = dsu.find(u), v = dsu.find(v);
            cout << 1LL * dsu.sz[u] * dsu.sz[v] << '\n';
        }
        return dsu.undo(step), void();
    }
    int mid = (l + r) >> 1;
    solve(l, mid, ls), solve(mid + 1, r, rs), dsu.undo(step);
}

void _main() {
    cin >> n >> q;
    for (int i = 1, u, v; i <= q; i++) {
        char opt; cin >> opt >> u >> v;
        if (u > v) swap(u, v);
        pair<int, int> e = {u, v};
        if (opt == 'A') last[e] = ++k;
        else insert(last[e], k, e), ask[++k] = e, last[e] = ++k;
    }
    for (auto [e, st] : last) insert(st, k, e);
    solve();
} 

:::::

CF601E A Museum Robbery

有 n 件物品,体积为 v_i,价值为 w_i。支持下列操作:

  1. 加入物品。
  2. 删除物品。
  3. 对所有 V \le k 询问容量为 V 的 01 背包。
*注意体积 & 价值的表示与原题相反。*

:::::success[题解]

背包追加是 O(k) 的,但是直接删除是 O(nk) 的,复杂度达到 O(q^2k),无法通过。

但是我们发现每个物品出现的时间是一个时间段,考虑线段树分治,在进入子树时进行 O(k) 的追加。

没有必要考虑退背包等科技。可以直接 O(n) 复制修改前的背包,做完 DP 后将背包数组再传递给左右儿子,继续复制。

复杂度为 O(qk \log q)。

:::::

:::::info[代码]

const int N = 1e5 + 5, M = 1e3 + 5;
const mint base = 10000019;
int n, k, q, cnt, cur;
tuple<int, int, int, int> e[N];

#define ls (rt << 1)
#define rs (rt << 1 | 1)
vector<pair<int, int>> val[N << 2];
void insert(int tl, int tr, const pair<int, int>& c, int l = 1, int r = cur, int rt = 1) {
    if (tl <= l && r <= tr) return val[rt].emplace_back(c), void();
    int mid = (l + r) >> 1;
    if (tl <= mid) insert(tl, tr, c, l, mid, ls);
    if (tr > mid) insert(tl, tr, c, mid + 1, r, rs);
}
void solve(vector<int>& dp, int l = 1, int r = cur, int rt = 1) {
    vector<int> f(dp.begin(), dp.end());
    for (auto& [v, w] : val[rt]) {
        for (int i = k; i >= v; i--) f[i] = max(f[i], f[i - v] + w);
    }
    if (l == r) {
        mint res = 0;
        for (int i = k; i >= 1; i--) res = res * base + f[i];
        return cout << res << '\n', void();
    }
    int mid = (l + r) >> 1;
    solve(f, l, mid, ls), solve(f, mid + 1, r, rs);
}

void _main() {
    cin >> n >> k;
    for (int i = 1, v, w; i <= n; i++) cin >> w >> v, e[i] = {v, w, 1, -1};
    cin >> q, cnt = n, cur = 1;
    for (int opt, v, w; q--; ) {
        cin >> opt;
        if (opt == 1) cin >> w >> v, e[++cnt] = {v, w, cur, -1};
        else if (opt == 2) cin >> v, get<3>(e[v]) = cur - 1;
        else cur++;   // cur 作为查询时刻
    }
    cur--;
    for (int i = 1; i <= cnt; i++) {
        auto [v, w, l, r] = e[i];
        if (r == -1) r = cur;
        if (l <= r) insert(l, r, {v, w});
    }
    vector<int> f(M + 5);
    solve(f);
}

:::::

P2056 [ZJOI2007] 捉迷藏

给你一棵无根树,你需要维护一个点集 S,初始时 S=\{1,2,\cdots,n\}。有如下操作:

  1. 将一个节点加入 / 移出点集 S。
  2. 查询点集 S 的直径。

:::::success[题解]

对于动态维护点集直径的问题,我们有结论:设 S 的直径端点为 (u,v),则 S \cup \{w\} 的直径必然是 (u,v),(u,w),(v,w) 之一。反证法容易证明。

求出 LCA 维护树上距离,即可做到 O(\log n) \sim O(1) 的加点。

我们发现每个点在点集中出现的时刻也是一个时间段,可以线段树分治,用同样的方法加点。

直接将修改后的直径端点复制给儿子,让儿子继续递归,即可做到撤销的效果。

视 n,q 同阶则复杂度 O(n \log^2 n) \sim O(n \log n),取决于 LCA 求法。

:::::

:::::info[代码]

const int N = 6e5 + 5;

int n, q, last[N], ins[N];
vector<int> e[N];

int sz[N], fa[N], dep[N], son[N], top[N];
void dfs1(int u) {
    sz[u] = 1;
    for (int v : e[u]) {
        if (v == fa[u]) continue;
        fa[v] = u, dep[v] = dep[u] + 1, dfs1(v), sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int t) {
    top[u] = t;
    if (son[u]) dfs2(son[u], t);
    for (int v : e[u]) {
        if (v != fa[u] && v != son[u]) dfs2(v, v);
    }
}
int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    } return dep[u] < dep[v] ? u : v;
}
int dis(int u, int v) {
    if (u == -1 || v == -1) return -1;
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

#define ls (rt << 1)
#define rs (rt << 1 | 1)
vector<int> val[N << 2];
bool ask[N];
void insert(int tl, int tr, int c, int l = 1, int r = q + 2, int rt = 1) {
    if (tl <= l && r <= tr) return val[rt].emplace_back(c), void();
    int mid = (l + r) >> 1;
    if (tl <= mid) insert(tl, tr, c, l, mid, ls);
    if (tr > mid) insert(tl, tr, c, mid + 1, r, rs);
}
void solve(int u, int v, int l = 1, int r = q + 2, int rt = 1) {
    for (int w : val[rt]) {
        int d0 = dis(u, v), d1 = dis(u, w), d2 = dis(v, w);
        if (u == -1 || v == -1) u = v = w;
        else if (d1 >= d0 && d1 >= d2) v = w;
        else if (d2 >= d0 && d2 >= d1) u = v, v = w; 
    }
    if (l == r) {
        if (ask[l]) cout << dis(u, v) << '\n';
        return;
    }
    int mid = (l + r) >> 1;
    solve(u, v, l, mid, ls), solve(u, v, mid + 1, r, rs);
}

void _main() {
    cin >> n;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        e[u].emplace_back(v), e[v].emplace_back(u);
    }
    cin >> q, dfs1(1), dfs2(1, 1);
    fill(last + 1, last + n + 1, 1), fill(ins + 1, ins + n + 1, 1);
    for (int i = 2, x; i <= q + 1; i++) {
        char opt; cin >> opt;
        if (opt == 'C') {
            cin >> x;
            if (ins[x]) ins[x] = 0, insert(last[x], i, x);
            else ins[x] = 1, last[x] = i;
        } else {
            ask[i] = true;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (ins[i]) insert(last[i], q + 2, i);
    }
    solve(-1, -1);
}

:::::

P3206 [HNOI2010] 城市建设

你需要维护一个 n 个点 m 条边的无向带权图。q 次操作,修改一条边的边权,然后查询最小生成树的边权和。

:::::success[题解]

线段树分治起手,但是加边删边无法简单地维护 MST,使用 LCT 常数过大且实现难度大。

考虑在线段树叶子节点直接跑 O(m \log m) 的 Kruskal,复杂度 O(qm\log m) 无法通过。

本题的精妙之处在于,在进入子树递归时,只保留当前不确定是否在 MST 中的边。

在线段树上的节点 [l,r],所有的边可以分为两类:

通过分析 E_0 中的边在两种极端情况下的表现,我们可以决策 E_1 中的边是否必要。

  1. 删除无用边:令 E_2 \gets E_1。对于 (u,v,w) \in E_0,将 (u,v,+\infty) 加入 E_2,对 G_2=(V,E_2) 跑 MST。
    此时 Kruskal 优先选择 E_1 中的边作为 MST 中的边。在这种情形下,若 e \in E_1 且 e 不属于 MST,这说明在 G_1=(V,E_1) 中已经存在了连接 e 两端的路径,则边 e 一定无用。
    对于这种边 e,我们直接将其删除。

  2. 锁定必选边:令 E_3 \gets E_1。对于 (u,v,w) \in E_0,将 (u,v,-\infty) 加入 E_3,对 G_3=(V,E_3) 跑 MST。
    此时 Kruskal 优先选择 E_0 中的边作为 MST 中边。在这种情形下,若 e \in E_1 且 e 还属于 MST,这说明在 G_0=(V,E_0) 中 e 的两端是不连通的,而 e 的边权是将其连通的最小代价,则边 e 是必选边。
    对于必选边 e,可以提前将 e 的权值加入答案,然后将 e 的两个端点缩成一点,边 e 不参与后续计算。

缩点后 |V| 是 O(r-l) 的,删边后 |V|,|E| 同阶,因此向儿子传递的边集也是 O(r-l) 的,每层跑 Kruskal 可以接受。总体复杂度即 O(q \log q \log m)。

实现的时候,我们不用建立线段树的显式结构,可以直接递归分治。所以这个东西其实更像 CDQ 分治。代码写的有点乱。

:::::

:::::info[代码]

const int N = 7e4 + 5, inf = 1e9;
using modify = pair<int, int>;  // {id, w}
using edge = tuple<int, int, int>;  // {u, v, id}
using wedge = tuple<int, int, int, bool, int>; // {w, u, v, in E1, id}

int n, m, q, fa[N], in0[N], val[N];
modify mod[N];
i64 ans[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}

void init(vector<edge>& e) {
    for (auto [u, v, id] : e) fa[u] = u, fa[v] = v;
}
void init(vector<wedge>& e) {
    for (auto [w, u, v, is1, id] : e) fa[u] = u, fa[v] = v;
}
void solve(int l, int r, vector<edge>& e, i64 tot) {
    auto cmp = [&](const edge& a, const edge& b) -> bool {
        return val[get<2>(a)] < val[get<2>(b)];
    };
    if (l == r) {
        auto [id, w] = mod[l];
        val[id] = w, init(e), sort(e.begin(), e.end(), cmp), ans[l] = tot;
        for (auto [u, v, id] : e) {
            u = find(u), v = find(v);
            if (u != v) fa[u] = v, ans[l] += val[id];
        }
        return;
    }
    // 1. 划分 E0, E1
    for (int i = l; i <= r; i++) in0[mod[i].first] = true;
    vector<edge> e0, e1;
    for (auto [u, v, id] : e) {
        if (in0[id]) e0.emplace_back(u, v, id);
        else e1.emplace_back(u, v, id);
    }
    for (int i = l; i <= r; i++) in0[mod[i].first] = false;

    // 2. 删除无用边
    vector<wedge> e2;
    for (auto [u, v, id] : e1) e2.emplace_back(val[id], u, v, 1, id);
    for (auto [u, v, id] : e0) e2.emplace_back(inf, u, v, 0, id);
    init(e2), sort(e2.begin(), e2.end());
    vector<edge> e1n;
    for (auto [w, u, v, is1, id] : e2) {
        int fu = find(u), fv = find(v);
        if (fu == fv) continue;
        fa[fu] = fv;
        if (is1) e1n.emplace_back(u, v, id); 
    }

    // 3. 锁定必选边
    vector<wedge> e3;
    for (auto [u, v, id] : e1n) e3.emplace_back(val[id], u, v, 1, id);
    for (auto [u, v, id] : e0) e3.emplace_back(-inf, u, v, 0, id);
    init(e3), sort(e3.begin(), e3.end());
    vector<edge> must, pend;
    for (auto [w, u, v, is1, id] : e3) {
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            fa[fu] = fv;
            if (is1) tot += val[id], must.emplace_back(u, v, id);
        } else {
            if (is1) pend.emplace_back(u, v, id);
        }
    }

    // 4. 缩点
    init(e);
    for (auto [u, v, id] : must) fa[find(u)] = find(v);
    vector<edge> en;
    for (auto [u, v, id] : pend) {
        u = find(u), v = find(v);
        if (u == v) continue;
        en.emplace_back(u, v, id);
    }
    for (auto [u, v, id] : e0) {
        u = find(u), v = find(v);
        if (u == v) continue;
        en.emplace_back(u, v, id);
    }

    // 5. 递归
    int mid = (l + r) >> 1;
    solve(l, mid, en, tot), solve(mid + 1, r, en, tot);
}

void _main() {
    cin >> n >> m >> q;
    iota(fa + 1, fa + n + 1, 1);
    vector<edge> e;
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        e.emplace_back(u, v, i), val[i] = w;
    }
    for (int i = 1; i <= q; i++) cin >> mod[i];
    solve(1, q, e, 0);
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

:::::

P9168 [省选联考 2023] 人员调度

给你一棵以 1 为根的有根树,有 k 个人初始位于 x_1,x_2,\cdots,x_k,且每个人有一个权值 v_i。

你需要进行 q 次操作,支持加人、删人。在开始和每次操作后,查询如下问题的答案:

将每个人的位置改到子树内,定义得分为每个节点上权值最大值的和,求最大得分。查询之间独立。

:::::success[题解]

设 S_u 为节点 u 处所有人的权值集合。先考虑单次查询怎么做。

我们维护一个多重集 C_u 表示 u 子树内所有人的权值集合,可以自底向上求得

C_u=S_u \cup \bigcup_{v \in \operatorname{son}(u)} C_v

如果 |C_u| 超过了 u 子树大小,就弹出最小值直到合法。容易发现这个贪心策略是正确的。

使用可并堆或者 multiset 启发式合并维护,复杂度 O(qn \log n),可以获得 48 分。

注意到题目中加人删人的操作使得每个人的出现时间是一个时间段,考虑线段树分治,将删除变成撤销。现在必须正面维护合并的过程。

直接对着集合合并维护是困难的,考虑加点过程,关注其对答案的影响。

为每个节点维护一个剩余容量 f_u=sz_u-|C_u|,其中 sz_u 为子树大小。则合法条件为 \forall u, f_u \ge 0。

当我们在 u 处加入一个权值为 x 的人时:

先重链剖分,建一棵支持区间加法、区间求最小值的线段树来维护 f_u。加点就是根链 -1,撤销就是根链 +1,并且在线段树上二分求区间内最靠右的 0 的位置。

再在每个节点开一个 multiset,维护当前时刻被选中并被放到 u 的人。加点直接插入,撤销直接删除。在线段树上再维护一下被选的最小权值即可。

综上,视 n,q,k 同阶,复杂度做到 O(n \log^3 n),树剖带 \dfrac{1}{2} 常数可以通过。

:::::

:::::info[代码]

const int N = 2e5 + 5, inf = 1e9;
using node = pair<int, int>;  // {val, id}

int n, k, q, fa[N];
vector<int> e[N];
multiset<node> st[N]; 

int dn, dep[N], sz[N], son[N], dfn[N], top[N], rev[N];
void dfs1(int u) {
    sz[u] = 1;
    for (int v : e[u]) {
        dep[v] = dep[u] + 1, dfs1(v), sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int t) {
    dfn[u] = ++dn, rev[dn] = u, top[u] = t;
    if (son[u]) dfs2(son[u], t);
    for (int v : e[u]) if (v != son[u]) dfs2(v, v);
}

struct segtree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
    int fmin[N << 2], tag[N << 2];
    node vmin[N << 2];
    void pushup(int rt) {fmin[rt] = min(fmin[ls], fmin[rs]), vmin[rt] = min(vmin[ls], vmin[rs]);}
    void apply(int rt, int c) {fmin[rt] += c, tag[rt] += c;}
    void pushdown(int rt) {
        if (!tag[rt]) return;
        apply(ls, tag[rt]), apply(rs, tag[rt]), tag[rt] = 0;
    }
    void build(int l = 1, int r = n, int rt = 1) {
        if (l == r) return fmin[rt] = sz[rev[l]], vmin[rt] = {inf, -1}, void();
        int mid = (l + r) >> 1;
        build(l, mid, ls), build(mid + 1, r, rs), pushup(rt);
    }
    void fadd(int tl, int tr, int c, int l = 1, int r = n, int rt = 1) {
        if (tl <= l && r <= tr) return apply(rt, c), void();
        int mid = (l + r) >> 1; pushdown(rt);
        if (tl <= mid) fadd(tl, tr, c, l, mid, ls);
        if (tr > mid) fadd(tl, tr, c, mid + 1, r, rs);
        pushup(rt);
    }
    int find(int tl, int tr, int l = 1, int r = n, int rt = 1) {
        if (fmin[rt] > 0) return -1;
        if (l == r) return l;
        int mid = (l + r) >> 1, res = -1; pushdown(rt);
        if (tr > mid) res = find(tl, tr, mid + 1, r, rs);
        if (tl <= mid && res == -1) res = find(tl, tr, l, mid, ls);
        return res;
    }
    void vadd(int x, int l = 1, int r = n, int rt = 1) {
        if (l == r) {
            int u = rev[x];
            vmin[rt] = st[u].empty() ? node(inf, -1) : *st[u].begin();
            return;
        }
        int mid = (l + r) >> 1; pushdown(rt);
        if (x <= mid) vadd(x, l, mid, ls);
        else vadd(x, mid + 1, r, rs);
        pushup(rt);
    }
    node vask(int tl, int tr, int l = 1, int r = n, int rt = 1) {
        if (tl <= l && r <= tr) return vmin[rt];
        int mid = (l + r) >> 1; pushdown(rt);
        if (tl <= mid && mid < tr) return min(vask(tl, tr, l, mid, ls), vask(tl, tr, mid + 1, r, rs));
        return tl <= mid ? vask(tl, tr, l, mid, ls) : vask(tl, tr, mid + 1, r, rs);
    }
} sgt;

int find(int u) {
    for (; u; u = fa[top[u]]) {
        int id = sgt.find(dfn[top[u]], dfn[u]);
        if (id != -1) return rev[id];
    } return -1;
}
void fadd(int u, int c) {
    for (; u; u = fa[top[u]]) sgt.fadd(dfn[top[u]], dfn[u], c);
}

vector<int> val[N << 2];
void insert(int tl, int tr, int c, int l = 0, int r = q, int rt = 1) {
    if (tl <= l && r <= tr) return val[rt].emplace_back(c), void();
    int mid = (l + r) >> 1;
    if (tl <= mid) insert(tl, tr, c, l, mid, ls);
    if (tr > mid) insert(tl, tr, c, mid + 1, r, rs);
}

node p[N];
i64 cur, ans[N];
void add(int x) {
    auto [v, u] = p[x];
    cur += v, st[u].emplace(v, x);
    sgt.vadd(dfn[u]), fadd(u, -1);
}
void del(int x) {
    auto [v, u] = p[x];
    cur -= v, st[u].erase(st[u].find(node(v, x)));
    sgt.vadd(dfn[u]), fadd(u, 1);
}

stack<pair<int, int>> his; 
void solve(int l = 0, int r = q, int rt = 1) {
    int step = his.size();
    for (int id : val[rt]) {
        int u = find(p[id].second);
        if (u == -1) {
            add(id), his.emplace(id, -1);
        } else {
            node res = sgt.vask(dfn[u], dfn[u] + sz[u] - 1);
            if (res.first >= p[id].first) continue;
            del(res.second), add(id);
            his.emplace(id, res.second);
        }
    }
    int mid = (l + r) >> 1;
    if (l == r) ans[l] = cur;
    else solve(l, mid, ls), solve(mid + 1, r, rs);
    while ((int)his.size() > step) {
        auto [x, y] = his.top(); his.pop(), del(x);
        if (y != -1) add(y);
    }
}

int L[N], R[N];
void _main() {
    cin >> n >> n >> k >> q;
    for (int u = 2; u <= n; u++) cin >> fa[u], e[fa[u]].emplace_back(u);
    dfs1(1), dfs2(1, 1), sgt.build();
    for (int i = 1, x, y; i <= k; i++) cin >> x >> y, p[i] = {y, x}, R[i] = q;
    int m = k;
    for (int i = 1, opt, x, v; i <= q; i++) {
        cin >> opt >> x;
        if (opt == 1) cin >> v, m++, p[m] = {v, x}, L[m] = i, R[m] = q;
        else R[x] = i - 1;
    }
    for (int i = 1; i <= m; i++) if (L[i] <= R[i]) insert(L[i], R[i], i);
    solve();
    for (int i = 0; i <= q; i++) cout << ans[i] << ' ';
}

:::::

P3157 [CQOI2011] 动态逆序对

给出一个长为 n 的排列,q 次操作,每次删除一个数,查询删除之前序列的逆序对数。

:::::success[题解]

先对原序列跑归并排序 / 树状数组求出逆序对数,问题变为每次操作减少的逆序对数。

把每个元素被删除的时刻 t_i 纳入考虑范围。对于数字 a_i,有贡献的 (i,j) 满足如下条件:

这是一个三维偏序问题,做两次 CDQ 分治即可 O(n \log^2 n)。你也可以理解 CDQ 分治将动态问题静态化。

:::::

:::::info[代码]

const int N = 1e5 + 5;
int n, q, a[N], pos[N], t[N];
i64 cnt[N];

struct BIT {
    int tr[N];
    void add(int x, int c) {
        for (; x <= n; x += lowbit(x)) tr[x] += c;
    }
    int ask(int x) {
        int res = 0;
        for (; x >= 1; x -= lowbit(x)) res += tr[x];
        return res;
    }
} B;

struct CDQ {
    using node = tuple<int, int, int>;  // {y, z, id}
    node a[N]; BIT B; i64 ans[N];
    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;
        vector<node> tmp;
        auto iadd = [&]() -> void {
            auto [y, z, id] = a[i];
            B.add(z, 1), tmp.emplace_back(a[i++]);
        };
        auto jadd = [&]() -> void {
            auto [y, z, id] = a[j];
            ans[id] += B.ask(z - 1), tmp.emplace_back(a[j++]);
        };
        while (i <= mid && j <= r) {
            if (get<0>(a[i]) < get<0>(a[j])) iadd();
            else jadd();
        }
        while (i <= mid) iadd();
        while (j <= r) jadd();
        for (int k = l; k <= mid; k++) B.add(get<1>(a[k]), -1);
        copy(tmp.begin(), tmp.end(), a + l);
    }
} C1, C2;

void _main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i], pos[a[i]] = i;
    fill(t + 1, t + n + 1, q + 1);
    for (int i = 1, x; i <= q; i++) cin >> x, t[pos[x]] = i; 
    i64 inv = 0;
    for (int i = 1; i <= n; i++) inv += i - 1 - B.ask(a[i]), B.add(a[i], 1);
    for (int i = 1; i <= n; i++) {
        C1.a[i] = {n - a[i] + 1, q - t[i] + 2, i};
        C2.a[n - i + 1] = {a[i], q - t[i] + 2, i};
    }
    C1.solve(1, n), C2.solve(1, n);
    for (int i = 1; i <= n; i++) {
        if (t[i] <= q) cnt[t[i]] = C1.ans[i] + C2.ans[i];
    }
    for (int i = 1; i <= q; i++) cout << inv << '\n', inv -= cnt[i];
}

:::::

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

给出 n 个元素,元素有四个属性值 a_i,b_i,c_i,d_i。q 次询问给出 A,B,C,D,求满足 a_i \le A \land b_ i\le B \land c_i \ge C \land d_i \ge D 的元素数目。

:::::success[题解]

典型的四维偏序,先对 a_i 排序降掉第一维。然后对 b_i 做 CDQ 分治,用双指针维护最后一个满足 b_i 偏序于 b_j 的 i。

此时还需考虑 c,d 的偏序关系,我们把每个元素打上标记,表示它属于外层分治的左区间还是右区间,问题就变成了三维偏序,可以套用 CDQ 分治解决。

本题有一点细节:需要将 c,d 取反再离散化,因为偏序关系是相反的。

总复杂度为 O(n \log^3 n),可以通过。更一般地,对于 k 维偏序问题,使用 CDQ 套 CDQ 的复杂度为 O(n \log^{k-1} n)。

:::::

:::::info[代码]

const int N = 8e5 + 5;
int n, m, q;
vector<int> vec;
struct node {
    int a, b, c, d, type, id, part;
} a[N], b[N];
i64 ans[N];

struct BIT {
    int tr[N];
    void add(int x, int c) {
        for (; x <= m; x += lowbit(x)) tr[x] += c;
    }
    int ask(int x) {
        int res = 0;
        for (; x >= 1; x -= lowbit(x)) res += tr[x];
        return res;
    }
} 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 = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (b[i].c <= b[j].c) {
            if (b[i].part == 0) B.add(b[i].d, 1);
            i++;
        } else {
            if (b[j].part == 1) ans[b[j].id] += B.ask(b[j].d);
            j++;
        }
    }
    for (; i <= mid; i++) {
        if (b[i].part == 0) B.add(b[i].d, 1);
    }
    for (; j <= r; j++) {
        if (b[j].part == 1) ans[b[j].id] += B.ask(b[j].d);
    }
    for (int k = l; k <= mid; k++) {
        if (b[k].part == 0) B.add(b[k].d, -1);
    }
    inplace_merge(b + l, b + mid + 1, b + r + 1, [](const node& a, const node& b) -> bool {
        return a.c < b.c;
    });
}
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, cnt = 0;
    while (i <= mid && j <= r) {
        if (a[i].b <= a[j].b) {
            if (a[i].type == 0) b[++cnt] = a[i], b[cnt].part = 0;
            i++;
        } else {
            if (a[j].type == 1) b[++cnt] = a[j], b[cnt].part = 1;
            j++;
        }
    }
    for (; i <= mid; i++) {
        if (a[i].type == 0) b[++cnt] = a[i], b[cnt].part = 0;
    }
    for (; j <= r; j++) {
        if (a[j].type == 1) b[++cnt] = a[j], b[cnt].part = 1;
    }
    cdq(1, cnt);
    inplace_merge(a + l, a + mid + 1, a + r + 1, [](const node& a, const node& b) -> bool {
        return a.b < b.b;
    });
}

void _main() {
    cin >> n >> q;
    for (int i = 1, a, b, c, d; i <= n; i++) {
        cin >> a >> b >> c >> d;
        ::a[i] = {a, b, -c, -d, 0, 0, 0};
        vec.emplace_back(-d);
    }
    for (int i = 1, a, b, c, d; i <= q; i++) {
        cin >> a >> b >> c >> d;
        ::a[i + n] = {a, b, -c, -d, 1, i, 0};
        vec.emplace_back(-d);
    }
    sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()), m = vec.size();
    for (int i = 1; i <= n + q; i++) a[i].d = lower_bound(vec.begin(), vec.end(), a[i].d) - vec.begin() + 1;
    sort(a + 1, a + n + q + 1, [](const node& a, const node& b) -> bool {
        if (a.a != b.a) return a.a < b.a;
        if (a.b != b.b) return a.b < b.b;
        if (a.c != b.c) return a.c < b.c;
        return a.d != b.d ? a.d < b.d : a.type < b.type;
    });
    solve(1, n + q);
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

:::::

P2487 [SDOI2011] 拦截导弹

给出二维平面上的 n 个点 (x_i,y_i)。先求出 LDS 长度,再求出对于每个 i 求出第 i 个点被选入二维 LDS 的概率。LDS 指最长不升子序列。

:::::success[题解]

根据 ABC354F 的首尾合并思想,可以设计出前后缀 DP,设 f_{0,i} 为以 i 结尾的 LDS 长度,g_{0,i} 为以 i 结尾的 LDS 数目,得转移

f_{0,i}=1+\max_{j<i,x_i \le x_j, y_i \le y_j} f_{0,j}

同理设 f_{1,i} 为开头的 LDS 长度,g_{1,i} 为以 i 开头的 LDS 数目,倒着枚举 i 进行转移,式子类似。

可得第一问答案为 a=\max\limits_{i=1}^n f_{0,i},则 (x_i,y_i) 可以被选入 LDS 当且仅当 f_{0,i}+f_{1,i}-1=a,此时乘法原理合并前后缀贡献,得包含 i 的 LDS 有 g_{0,i} \times g_{1,i},除一下总数就是概率,复杂度 O(n^2)。

观察 DP 式,转移关系 j \to i 满足三维偏序结构,使用两次 CDQ 分治优化 DP 即可做到 O(n \log^2 n)。

一些实现细节:

:::::

:::::info[代码]

const int N = 5e4 + 5;
int n, m, d[N];

using info = pair<int, double>;
info operator+ (const info& a, const info& b) {
    if (a.first != b.first) return max(a, b);
    return {a.first, a.second + b.second};
}
info& operator+= (info& a, const info& b) {return a = a + b;}
struct BIT {
    info tr[N];
    void add(int x, info c) {
        for (; x <= m; x += lowbit(x)) tr[x] += c;
    }
    info ask(int x) {
        info res;
        for (; x >= 1; x -= lowbit(x)) res += tr[x];
        return res;
    }
    void clear(int x) {
        for (; x <= m; x += lowbit(x)) tr[x] = info(-1, -1);
    }
} B1, B2;
struct node {
    int id, x, y;
    info pre, suf;
} a[N];

void solve1(int l, int r) {
    if (l == r) {
        if (a[l].pre.first == 0) a[l].pre = info(1, 1);
        return;
    }
    int mid = (l + r) >> 1;
    solve1(l, mid);
    vector<int> L, R;
    for (int i = l; i <= mid; i++) L.emplace_back(i);
    for (int i = mid + 1; i <= r; i++) R.emplace_back(i);
    sort(L.begin(), L.end(), [](int x, int y) -> bool {return a[x].x > a[y].x;});
    sort(R.begin(), R.end(), [](int x, int y) -> bool {return a[x].x > a[y].x;});
    int i = 0;
    for (int j : R) {
        for (; i < (int)L.size() && a[L[i]].x >= a[j].x; i++) B1.add(m - a[L[i]].y + 1, a[L[i]].pre);
        info u = B1.ask(m - a[j].y + 1);
        if (u.first > 0) a[j].pre += info(u.first + 1, u.second);
    }
    for (int k = 0; k < i; k++) B1.clear(m - a[L[k]].y + 1);
    solve1(mid + 1, r);
}

void solve2(int l, int r) {
    if (l == r) {
        if (a[l].suf.first == 0) a[l].suf = info(1, 1);
        return;
    }
    int mid = (l + r) >> 1;
    solve2(mid + 1, r);
    vector<int> L, R;
    for (int i = l; i <= mid; i++) L.emplace_back(i);
    for (int i = mid + 1; i <= r; i++) R.emplace_back(i);
    sort(L.begin(), L.end(), [](int x, int y) -> bool {return a[x].x < a[y].x;});
    sort(R.begin(), R.end(), [](int x, int y) -> bool {return a[x].x < a[y].x;});
    int i = 0;
    for (int j : L) {
        for (; i < (int)R.size() && a[R[i]].x <= a[j].x; i++) B2.add(a[R[i]].y, a[R[i]].suf);
        info u = B2.ask(a[j].y);
        if (u.first > 0) a[j].suf += info(u.first + 1, u.second);
    }
    for (int k = 0; k < i; k++) B2.clear(a[R[k]].y);
    solve2(l, mid);
} 

void _main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y;
        a[i].id = i, d[i] = a[i].y;
    }
    sort(d + 1, d + n + 1), m = unique(d + 1, d + n + 1) - d - 1;
    for (int i = 1; i <= n; i++) a[i].y = lower_bound(d + 1, d + m + 1, a[i].y) - d;
    solve1(1, n), solve2(1, n);
    int len = 1;
    for (int i = 1; i <= n; i++) len = max(len, a[i].pre.first);
    cout << len << '\n' << fixed << setprecision(5);
    double tot = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i].pre.first == len) tot += a[i].pre.second;
    }
    for (int i = 1; i <= n; i++) {
        auto [f0, g0] = a[i].pre;
        auto [f1, g1] = a[i].suf;
        if (f0 + f1 - 1 == len) cout << g0 * g1 / tot << ' ';
        else cout << 0.0 << ' ';
    }
} 

:::::

P5979 [PA 2014] Druzyny

给出 n 个物品,每个物品有属性 l_i,r_i,你需要将它们划分为若干连续段,满足第 i 个物品所属连续段长度 \in [l_i,r_i]。

求出最大段数和达成此段数的方案数,或者报告无解。方案数对 10^9+7 取模。

:::::success[题解]

容易设计一个朴素 DP,设 f_i 为以 i 结尾的最大段数,枚举上一段结束点 j 有

f_i=1+\max_{j\le i, \forall k \in [j,i], j-i+1 \in [l_k,r_k]} f_j

方案数容易根据 f 的转移同时维护,下面只对 f 的求解考虑。

将 \forall k \in [j,i], j-i+1 \in [l_k,r_k] 单独拿出来看,发现只需取交集,即条件等价于 j-i+1 \in \bigcap\limits_{k \in[j,i]} [l_k,r_k]。记 L(j,i)=\max\limits_{k \in [j,i]} l_k, R(j,i)=\max\limits_{k \in [j,i]} r_i,则交集 S(j,i)=[L(j,i),R(j,i)]。通过倒序枚举 j 维护交集可做到 O(n^2),获得 46 分。

DP 式不满足决策单调性,j 的取值也不连续,只能考虑 CDQ 分治优化 DP。计算出左段 [l,m] 的 DP,我们考虑其对 (m,r] 中每个点的影响。

将点对 (i,j) 有影响的条件列出:

本题最为精妙的点在于将第二个条件按照 m 拆开:

第一个条件关于 i,第二个条件关于 j,形成了一个二维数点结构,考虑扫描线。这里的扫描线比较巧妙,展开叙述一下:

把一个 i 产生贡献和贡献消失的信息挂到下标上。对序列开一棵线段树,支持单点修改,区间求 max。则 j 对于 i 会被影响的下标也是一段区间,可以直接在线段树上求出。

复杂度 O(n \log^2 n),在 7s 下足以通过。

:::::

:::::info[代码]

const int N = 1e6 + 5, inf = 1e9;
int n, a[N], b[N];
using node = pair<int, mint>;
node operator+ (const node& a, const node& b) {
    if (a.first != b.first) return max(a, b);
    return {a.first, a.second + b.second};
}

int tot;
struct segtree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
    node sum[N << 2];
    void pushup(int rt) {sum[rt] = sum[ls] + sum[rs];}
    void build(int l = 0, int r = tot, int rt = 1) {
        sum[rt] = node(-inf, 0);
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(l, mid, ls), build(mid + 1, r, rs);
    }
    void change(int x, const node& c, int l = 0, int r = tot, int rt = 1) {
        if (l == r) return sum[rt] = c, void();
        int mid = (l + r) >> 1;
        if (x <= mid) change(x, c, l, mid, ls);
        else change(x, c, mid + 1, r, rs);
        pushup(rt);
    }
    node ask(int tl, int tr, int l = 0, int r = tot, int rt = 1) {
        if (tl <= l && r <= tr) return sum[rt];
        int mid = (l + r) >> 1;
        if (tl <= mid && mid < tr) return ask(tl, tr, l, mid, ls) + ask(tl, tr, mid + 1, r, rs);
        return tl <= mid ? ask(tl, tr, l, mid, ls) : ask(tl, tr, mid + 1, r, rs);
    }
} sgt;

node dp[N];
vector<pair<int, int>> vec[N];
void solve(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    solve(l, mid);
    for (int i = mid + 1; i <= r; i++) vec[i].clear();
    for (int i = mid, cl = 1, cr = n; i >= l; i--) {
        if (cl > cr || i + cr <= mid) break;
        if (i + cl <= r) {
            vec[max(mid + 1, i + cl)].emplace_back(i, 1);
            vec[min(r + 1, i + cr + 1)].emplace_back(i, -1);
        }
        cl = max(cl, a[i]), cr = min(cr, b[i]);
    }
    tot = mid - l + 1, sgt.build();
    for (int i = mid + 1, cl = 1, cr = n; i <= r; i++) {
        for (auto& [x, op] : vec[i]) {
            if (op == 1) sgt.change(x - l + 1, dp[x]);
            else sgt.change(x - l + 1, node(-inf, 0));
        }
        cl = max(cl, a[i]), cr = min(cr, b[i]);
        if (cl > cr || i - cr > mid) break;
        int ql = max(l, i - cr) - l + 1, qr = min(mid, i - cl) - l + 1;
        if (ql > qr) continue;
        node u = sgt.ask(ql, qr);
        dp[i] = dp[i] + node(u.first + 1, u.second);
    }
    solve(mid + 1, r);
}

void _main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    fill(dp + 1, dp + n + 1, node(-inf, 0));
    dp[0] = node(0, 1), solve(0, n);
    auto [f, g] = dp[n];
    if (g.val == 0) cout << "NIE";
    else cout << f << ' ' << g;
} 

:::::

P4169 [Violet] 天使玩偶/SJY摆棋子

二维平面上初始有 n 个点 (x_i,y_i),进行 q 次操作:

  1. 加入一个新点。
  2. 给出 (x_0,y_0),求当前点中,与 (x_0,y_0) 最近的点到它的曼哈顿距离。

:::::success[题解]

考虑不带修的做法,相当于求如下式子:

\min_{i=1}^n (|x_0-x_i|+|y_0-y_i|)

带绝对值的式子考虑拆掉绝对值。以 x_0 \ge x_i \land y_0 \ge y_i 为例,所求为

x_0+y_0-\max_{i=1}^n (x_i+y_i)

将 x_i+y_i 视为一个点的权值,则问题变成单点加、矩形求 max,可以 CDQ 分治套扫描线解决。

另外三个方向类似,取一个相反数再跑 CDQ 即可。细节上注意树状数组初始化为负无穷。视 n,q 同阶复杂度 O(n \log n \log V)。

:::::

:::::info[代码]

const int N = 1e6 + 5, inf = 1e9;
struct node {
    int x, y, id, type;
} a[N], b[N];
int ans[N];

struct BIT {
    int tr[N];
    void init() {fill(tr, tr + N, -inf);}
    void add(int x, int c) {
        for (; x < N; x += lowbit(x)) tr[x] = max(tr[x], c);
    }
    int ask(int x) {
        int res = -inf;
        for (; x >= 1; x -= lowbit(x)) res = max(res, tr[x]);
        return res;
    }
    void clear(int x) {
        for (; x < N; x += lowbit(x)) tr[x] = -inf;
    }
} B;

int n, q;

void cdq(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    int i = l, j = mid + 1;
    for (; j <= r; j++) {
        for (; i <= mid && b[i].x <= b[j].x; i++) {
            if (b[i].type == 1) B.add(b[i].y, b[i].x + b[i].y);
        }
        if (b[j].type == 2) ans[b[j].id] = min(ans[b[j].id], b[j].x + b[j].y - B.ask(b[j].y));
    }
    for (int k = l; k < i; k++) {
        if (b[k].type == 1) B.clear(b[k].y);
    }
    inplace_merge(b + l, b + mid + 1, b + r + 1, [](const node& a, const node& b) -> bool {
        return a.x < b.x;
    });
}
void solve(int tx, int ty) {
    for (int i = 1; i <= n + q; i++) {
        b[i] = a[i];
        if (tx) b[i].x = 1e6 - b[i].x + 1;
        if (ty) b[i].y = 1e6 - b[i].y + 1;
    }
    B.init(), cdq(1, n + q);
}

void _main() {
    cin >> n >> q;
    for (int i = 1, x, y; i <= n; i++) {
        cin >> x >> y, x++, y++;
        a[i] = {x, y, 0, 1};
    }
    for (int i = 1, opt, x, y; i <= q; i++) {
        cin >> opt >> x >> y; x++, y++;
        a[i + n] = {x, y, i, opt};
    }
    fill(ans + 1, ans + q + 1, inf);
    solve(0, 0), solve(0, 1), solve(1, 0), solve(1, 1);
    for (int i = 1; i <= q; i++) {
        if (ans[i] != inf) cout << ans[i] << '\n';
    }
}

:::::

P4690 [Ynoi Easy Round 2016] 镜中的昆虫

维护一个长为 n 的序列 a_i,q 次操作,支持区间覆盖、区间数颜色。

:::::success[题解]

静态区间数颜色是经典题 HH 的项链,做法为离散化后维护 p_i 表示第 i 种颜色最后出现的位置,做一个二维数点。

如果本题是单点修改,可以直接上一个 CDQ 分治,将动态问题静态化。此时相当于解决一个单点加矩形求和问题,用扫描线即可处理好所有的修改—询问关系。

考虑区间修改怎么做,发现难以解决的原因是对 p 数组产生了 O(n^2) 次修改。仔细分析一下,如果一个区间 [l,r] 同色,对其做区间覆盖就只会有 p_l 改变,而 p_{l+1},p_{l+2},\cdots,p_r 不变。

基于此,考虑用 ODT 维护序列 a,每一步最坏只会新增 O(1) 个点,视 n,q 同阶,所有修改的总数只有 O(n) 个。在 ODT 分裂合并颜色段时,我们同时维护单点修改。

这样本题复杂度做到 O(n \log^2 n) 且空间线性。代码细节较多。

:::::

:::::info[代码]

const int N = 1e5 + 5, M = 1.4e6 + 5;
using query = tuple<int, int, int>;   // {x, l, r}
struct info {
    int x, y, id, v;
    bool operator< (const info& a) const {return x < a.x;}
};

int n, m, v, tot, cnt, a[N], d[N << 1], ans[N];
query q[N << 1];
info op[M];

struct node {
    int l, r; 
    mutable int v;
    node(int a = 0, int b = 0, int c = 0) : l(a), r(b), v(c) {}
    bool operator< (const node& a) const {return l < a.l;}
};
set<node> odt;
using IT = set<node>::iterator;
set<int> col[N << 1];
int to[N << 1];

vector<info> vec;
void P(int x, int y, int v) {op[++cnt] = info{x, y, -1, v};}
void Q(int x, int y, int id, int v) {op[++cnt] = info{x, y, id, v};}
IT add(int l, int r, int v) {
    to[l] = r;
    auto it = col[v].emplace(l).first;
    int pre = (it != col[v].begin()) ? *prev(it) : 0;
    it++; int nxt = (it != col[v].end()) ? *it : 0;
    int u = to[pre] + 1;
    P(l, u, 1);
    if (nxt) P(nxt, u, -1), P(nxt, r + 1, 1);
    return odt.emplace(l, r, v).first;
} 
void del(int l, int r, int v, bool keep = 0) {
    auto it = col[v].find(l);
    int pre = (it != col[v].begin()) ? *prev(it) : 0;
    it++; int nxt = (it != col[v].end()) ? *it : 0;
    int u = to[pre] + 1;
    P(l, u, -1);
    if (nxt) P(nxt, u, 1), P(nxt, r + 1, -1);
    col[v].erase(col[v].find(l)); 
    if (!keep) odt.erase(odt.find(node(l, r, v)));
}
void del(IT it, bool keep = 0) {del(it->l, it->r, it->v, keep);}

IT split(int x) {
    IT it = odt.lower_bound(node(x, 0, 0));
    if (it != odt.end() && it->l == x) return it;
    auto [l, r, v] = *prev(it);
    return del(l, r, v), add(l, x - 1, v), add(x, r, v);
}
void assign(int l, int r, int v) {
    IT itr = split(r + 1), itl = split(l);
    for (IT it = itl; it != itr; it++) del(it, 1);
    odt.erase(itl, itr);
    IT pre = odt.lower_bound(node(l, 0, 0));
    if (pre != odt.begin() && prev(pre)->v == v) pre--, l = pre->l, del(pre);
    IT nxt = odt.upper_bound(node(r, 0, 0));
    if (nxt != odt.end() && nxt->v == v) r = nxt->r, del(nxt);
    add(l, r, v);
}

struct BIT {
    int tr[N];
    void add(int x, int c) {
        for (; x <= n; x += lowbit(x)) tr[x] += c;
    }
    int ask(int x) {
        int res = 0;
        for (; x >= 1; x -= lowbit(x)) res += tr[x];
        return res;
    }
} B;
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;
    for (; j <= r; j++) {
        for (; i <= mid && op[i].x <= op[j].x; i++) {
            if (op[i].id == -1) B.add(op[i].y, op[i].v);
        }
        if (op[j].id != -1) ans[op[j].id] += op[j].v * B.ask(op[j].y);
    }
    for (int k = l; k < i; k++) {
        if (op[k].id == -1) B.add(op[k].y, -op[k].v);
    }
    inplace_merge(op + l, op + mid + 1, op + r + 1);
}

void _main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i], d[++v] = a[i];
    for (int i = 1, opt, l, r, x; i <= m; i++) {
        cin >> opt >> l >> r;
        if (opt == 1) cin >> x, q[i] = {x, l, r}, d[++v] = x;
        else q[i] = {-1, l, r};
    }
    sort(d + 1, d + v + 1), v = unique(d + 1, d + v + 1) - d - 1;
    for (int i = 1; i <= n; i++) a[i] = lower_bound(d + 1, d + v + 1, a[i]) - d;
    for (int i = 1; i <= m; i++) {
        int& c = get<0>(q[i]);
        if (c != -1) c = lower_bound(d + 1, d + v + 1, c) - d;
    }
    for (int i = 1; i <= n; ) {
        int l = i;
        while (i <= n && a[i] == a[l]) i++;
        add(l, i - 1, a[l]);
    }
    for (int i = 1; i <= m; i++) {
        auto [x, l, r] = q[i];
        if (x != -1) {
            assign(l, r, x);
        } else {
            ans[++tot] = 1;
            if (l < r) Q(r, l, tot, 1), Q(l, l, tot, -1);
        }
    }
    solve(1, cnt);
    for (int i = 1; i <= tot; i++) cout << ans[i] << '\n'; 
}

:::::

P5331 [SNOI2019] 通信

给定 n 个节点,每个点有点权 a_i。每个节点必须选择下列之一:

  1. 连接到汇点,代价为 w。
  2. 连接到前面的节点 j,满足 j<i,代价为 |a_i-a_j|。要求节点入度不超过 1。

求最小代价。

:::::success[题解]

由于只有 j<i 才可能连边,本题形成了一个拓扑序结构。如果将所有可行的连边建出,就是一张 DAG。

考虑节点之间的连接形成的结构,由于题目强制入度出度必须为 1,故节点一定形成若干不交路径,终点为汇点。

经过上述讨论,本题是一个最小权 DAG 路径覆盖问题。可以使用拆点 + 费用流解决。我们将节点拆成入点 i_0 和出点 i_1,如下连边:

这样得到一张 O(n) 个节点,O(n^2) 条边的图,在实践中可以获得 80 分。

瓶颈在第四步连边,考虑 CDQ 分治优化建图。对于分治区间 [l,r],我们处理 (m,r] \to [l,m] 的连边,此时自然满足 j<i 的条件。

本题比较精妙的地方在于处理 |a_i-a_j| 这个边权。我们将它视为数轴上距离,将当前 [l,r] 区间内所有 a_i 排序并去重,然后在数轴上每个 a_i 的位置建虚点。

将相邻的虚点用双向边连接,容量设为 +\infty,费用为物理距离,形成一条虚点链。这样实点只要找到对应虚点连边即可。

这样形成一个 O(n \log n) 条边的图,实践中可以通过。

:::::

:::::info[代码]

const int N = 1e5 + 5;
int n, w, a[N], cnt;
mincost_flow<N, N> G;

void solve(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    solve(l, mid), solve(mid + 1, r);
    vector<int> vec(a + l, a + r + 1);
    sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end());
    int m = vec.size();
    for (int i = 1; i < m; i++) {
        G.add(i - 1 + cnt, i + cnt, G.INF, vec[i] - vec[i - 1]);
        G.add(i + cnt, i - 1 + cnt, G.INF, vec[i] - vec[i - 1]);
    }
    for (int i = l; i <= mid; i++) {
        int x = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
        G.add(x + cnt, i + n, 1, 0);
    }
    for (int i = mid + 1; i <= r; i++) {
        int x = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
        G.add(i, x + cnt, 1, 0);
    }
    cnt += m;
}

void _main() {
    cin >> n >> w;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int s = 0, t = 2 * n + 1; cnt = 2 * n + 2;
    for (int i = 1; i <= n; i++) G.add(s, i, 1, 0), G.add(i + n, t, 1, 0), G.add(i, t, 1, w);
    solve(1, n);
    cout << G(s, t).second;
}

:::::

P14638 [NOIP2025] 序列询问

给你一个长为 n 的整数序列 a。q 次询问给出 L,R,对每个 i 求出:

\max_{i \in [l,r],r-l+1 \in [L,R]} \sum_{j=l}^r a_j

:::::warning[注意]{open} 做法不是正解,仅供参考。 :::::

:::::success[题解]

注意到特殊性质 D & E,这只能说明一个事实:合法的区间一定跨过序列的中点或四等分点。这启示我们使用序列分治解决本题。

设当前分治区间 [l,r],中点为 m。我们只处理左端点位于 [l,m] 中,右端点位于 (m,r] 中的合法区间。而处理的思想则类似于 CDQ 分治,通过计算一侧对另一侧的影响来更新答案。

设 f_i 为以 i 为左端点,跨过中点的区间中,区间和的最大值。枚举 i \in [l,m],根据 j-i+1 \in [L,R] 得 j \in [i+L-1,i+R-1],与 (m,r] 取交集即得 j 的取值范围。将 a_i 变成前缀和后相当于查询 a_j-a_{i-1} 的最大值,由于 a_{i-1} 固定,用 ST 表做一个区间 max 即可。

设 g_j 为以 j 为右端点,跨过中点的区间中,区间和的最大值。同理枚举 j \in (m,r],得到 i 的范围,然后用 ST 表做区间 min。

分治结构的好处在于我们钦定合法区间跨过 m。考虑一个形如 y....x....m....r 的结构,我们发现 f_y 所代表的区间一定包含了 x。于是 x 在该层分治的答案即 \max\limits_{l \le y \le x} f_y。

综上,对 f 做一个前缀 max 就得到答案,g 则同理做后缀 max。复杂度 O(nq \log n),我的朴素实现获得了 40 分。

开始卡常。先做如下两个优化:

经过卡常的代码在洛谷 3s 时限下直接获得了 100 分。在 QOJ 上获得了 75 分。

::::info[代码]

const int N = 5e4 + 5;
const i64 inf = 1e18;

static int n, q, L, R;
static i64 a[N], ans[N], mn[18][N], mx[18][N];

static constexpr i64 max(i64 a, i64 b) {return a > b ? a : b;}
static constexpr i64 qmax(int l, int r) {
    if (l > r) return -inf;
    r++; int k = lg(r - l);
    return max(mx[k][l], mx[k][r - (1 << k)]);
}
static constexpr i64 qmin(int l, int r) {
    if (l > r) return inf;
    r++; int k = lg(r - l);
    return min(mn[k][l], mn[k][r - (1 << k)]);
}

static void solve(int l, int r) {
    if (r - l + 1 < L) return;
    if (l == r) {
        if (L == 1) ans[l] = max(ans[l], a[l] - a[l - 1]);
        return;
    }
    int mid = (l + r) >> 1;
    solve(l, mid), solve(mid + 1, r);
    auto lval = [&](int i) -> i64 {
        return qmax(max(mid + 1, i + L - 1), min(r, i + R - 1)) - a[i - 1];
    };
    auto rval = [&](int i) -> i64 {
        return a[i] - qmin(max(l - 1, i - R), min(mid - 1, i - L));
    };
    i64 pre = lval(l), suf = rval(r);
    ans[l] = max(ans[l], pre), ans[r] = max(ans[r], suf);
    for (int i = l + 1; i <= mid; i++) pre = max(pre, lval(i)), ans[i] = max(ans[i], pre);
    for (int i = r - 1; i > mid; i--) suf = max(suf, rval(i)), ans[i] = max(ans[i], suf);
}

static void _main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1];
    copy(a, a + n + 1, mx[0]), copy(a, a + n + 1, mn[0]);
    for (int i = 1; (1 << i) <= n; i++) {
        for (int j = 0; j + (1 << i) - 1 <= n; j++) {
            mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]);
            mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
        }
    }
    for (cin >> q; q--; ) {
        cin >> L >> R;
        fill(ans + 1, ans + n + 1, -inf);
        solve(1, n);
        u64 res = 0;
        for (int i = 1; i <= n; i++) res ^= (u64)i * (u64)ans[i];
        cout << res << '\n';
    }
} 

::::

我们将 ST 表手动内联,并且优化循环范围,使得每次查询有效。

较为关键的优化是,我们可以设定一个阈值 B,若分治区间长度 \le B,则在局部直接预处理 ST 表,在每次查询前,将小区间直接用预处理结果更新,大区间分治处理,并且在分治时不用处理长度 \le B 的区间。

这个做法的执行次数大概是 nB^2+nq \log \dfrac{n}{B},实践中取 B=64 比较优秀。

此代码在洛谷评测机上获得了最慢点 1.93s 的速度,可以在 QOJ 无压力通过。

:::::

:::::info[代码]

const int N = 5e4 + 5, B = 64;
const i64 inf = 1e18;

static int n, q, L, R, len[N];
static i64 a[N], ans[N], mn[16][N], mx[16][N], st[7][B + 5][N];

static void build(int l, int r) {
    if (r - l + 1 <= B) {
        fill(len + l, len + r + 1, r - l + 1);
        for (int i = l; i <= r; i++) {
            for (int k = 1; k <= r - l + 1; k++) {
                i64 mx = -inf;
                for (int x = max(l, i - k + 1); x <= min(r - k + 1, i); x++) {
                    i64 val = a[x + k - 1] - a[x - 1];
                    if (val > mx) mx = val;
                }
                st[0][k][i] = mx;
            }
        } return;
    }
    int mid = (l + r) >> 1;
    build(l, mid), build(mid + 1, r);
}
static void prework() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; (1 << j) <= len[i]; j++) {
            for (int k = 1; k + (1 << j) - 1 <= len[i]; k++) {
                st[j][k][i] = max(st[j - 1][k][i], st[j - 1][k + (1 << (j - 1))][i]);
            }
        }
    }
}

static void solve(int l, int r) {
    if (r - l + 1 < L) return;
    if (r - l + 1 <= B) return;
    if (l == r) {
        if (L == 1) ans[l] = max(ans[l], a[l] - a[l - 1]);
        return;
    }
    int mid = (l + r) >> 1, ql, qr, k;
    solve(l, mid), solve(mid + 1, r);

    int il = max(l, mid - R + 2), ir = min(mid, r - L + 1);
    if (il <= ir) {
        i64 pre = -inf;
        for (int i = il; i <= ir; i++) {
            ql = max(mid + 1, i + L - 1), qr = min(r, i + R - 1);
            i64 val = -inf;
            if (ql <= qr) k = __lg(qr - ql + 1), val = max(mx[k][ql], mx[k][qr - (1 << k) + 1]) - a[i - 1];
            if (val > pre) pre = val;
            if (pre > ans[i]) ans[i] = pre;
        }
        if (pre != -inf)
            for (int i = ir + 1; i <= mid; i++) ans[i] = max(ans[i], pre);
    }
    int jl = max(mid + 1, l + L - 1), jr = min(r, mid + R - 1);
    if (jl <= jr) {
        i64 suf = -inf;
        for (int i = jr; i >= jl; i--) {
            ql = max(l - 1, i - R), qr = min(mid - 1, i - L);
            i64 val = -inf;
            if (ql <= qr) k = __lg(qr - ql + 1), val = a[i] - min(mn[k][ql], mn[k][qr - (1 << k) + 1]);
            if (val > suf) suf = val;
            if (suf > ans[i]) ans[i] = suf;
        }
        if (suf != -inf)
            for (int i = jl - 1; i > mid; i--) ans[i] = max(ans[i], suf);
    }
}

static void _main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1];
    copy(a, a + n + 1, mx[0]), copy(a, a + n + 1, mn[0]);
    for (int i = 1; (1 << i) <= n; i++) {
        for (int j = 0; j + (1 << i) - 1 <= n; j++) {
            mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]);
            mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
        }
    }
    build(1, n), prework();
    for (cin >> q; q--; ) {
        cin >> L >> R;
        for (int i = 1; i <= n; i++) {
            int mk = min(R, len[i]);
            if (L > mk) {
                ans[i] = -inf;
            } else {
                int k = __lg(mk - L + 1);
                ans[i] = max(st[k][L][i], st[k][mk - (1 << k) + 1][i]);
            }
        }
        solve(1, n);
        u64 res = 0;
        for (int i = 1; i <= n; i++) res ^= (u64)i * (u64)ans[i];
        cout << res << '\n';
    }
}

:::::

P4948 数列求和

求

S_{n}(k)=\sum_{i=1}^k i^n x^i

:::::success[题解]

考虑用分治来进行求和,按照 k 的奇偶性讨论:

  1. 当 k 为奇数时,有
\begin{aligned} S_{n}(k)&=\sum_{i=1}^k i^n x^i\\ &=x +\sum_{i=2}^{k} i^n x^i\\ &=x+x\sum_{i=1}^{k-1} (i+1)^n x^i \\ &=x+x\sum_{i=1}^{k-1}x^i \sum_{j=0}^n \binom{n}{j} i^j\\ &=x+x\sum_{j=0}^n \binom{n}{j} \sum_{i=1}^{k-1} i^j x^i \\ &= x+x\sum_{j=0}^n \binom{n}{j} S_{j}(k-1) \end{aligned}
  1. 当 k 为偶数时,有
\begin{aligned} S_{n}(k)&=\sum_{i=1}^k i^n x^i\\ &=\sum_{i=1}^{k/2} i^n x^i+\sum_{i=k/2+1}^{k} i^n x^i \\ &=S_n(k/2)+x^{k/2} \sum_{i=1}^{k/2} (i+k/2)^n x^i\\ &=S_n(k/2)+x^{k/2} \sum_{i=1}^{k/2} x^i \sum_{j=0}^n \binom{n}{j} i^j (k/2)^{n-j}\\ &=S_n(k/2)+x^{k/2} \sum_{j=0}^n \binom{n}{j} (k/2)^{n-j}\sum_{i=1}^{k/2} i^j x^i \\ &=S_n(k/2)+x^{k/2} \sum_{j=0}^n \binom{n}{j} (k/2)^{n-j} S_j(k/2) \end{aligned}

递归求解即可,边界为 k=1,此时 S_n(1)=x。

注意:偶数情况中 (k/2)^{n-j} 不能对每个 j 单独快速幂计算,否则复杂度会退化为 O(n^2 \log^2 k)。只需倒序枚举 j,并维护 k/2 的幂次,即可将复杂度优化至 O(n^2 \log k)。

如果使用杨辉三角递推组合数,该做法支持任意模数。

:::::

:::::info[代码]

const int N = 2005;
long long n, k;
mint x, c[N][N];

void prework() {
    for (int i = 0; i <= n; i++) c[i][0] = c[i][i] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
    }
}

vector<mint> solve(long long k) {
    if (k == 1) return vector<mint>(n + 1, x);
    vector<mint> S(n + 1);
    if (k & 1) {
        auto T = solve(k - 1);
        for (int i = 0; i <= n; i++) {
            mint cur = 0;
            for (int j = 0; j <= i; j++) cur += c[i][j] * T[j];
            S[i] = x + x * cur;
        }
        return S;
    } else {
        auto T = solve(k >> 1);
        mint p = x.pow(k >> 1);
        for (int i = 0; i <= n; i++) {
            mint cur = 0, b = k >> 1, pw = 1;
            for (int j = i; j >= 0; j--, pw *= b) cur += c[i][j] * T[j] * pw;
            S[i] = T[i] + p * cur;
        }
        return S;
    }
}

void _main() {
    cin >> k >> x >> n;
    prework();
    auto S = solve(k);
    cout << S[n];
}

:::::

AT_ttpc2022_i XOR Reachable

给你一个 n 个点 m 条边的无向图,边带权 w_i。再给定一个 k,回答 q 次询问,给出 d,查询仅保留 (w_i \oplus d) < k 的边的情况下,可达点对的数目。

:::::success[题解]

先考虑一个暴力,每次询问使用并查集求连通块,设连通块有 p 个且大小为 s_1,s_2,\cdots,s_p,答案即 \sum\limits_{i=1}^p \frac{s_i(s_i-1)}{2}。复杂度 O(qm \alpha(n)) 无法通过。

这个过程可以用可撤销并查集维护,每次合并时减去原本的贡献,加上新连通块的贡献。撤销做这个操作的逆操作。这启示我们使用线段树分治等方法维护。

线段树分治适合于处理时间轴上连续段的问题,而本题相当于是有关位运算的连续段问题。考虑建立 01-Trie,利用 01-Trie 的结构分治。

从高位向低位建立 01-Trie,将询问的 d 拆到 01-Trie 上,并且在节点中插入询问编号。建树完成以后进行自顶向下计算答案。

在当前节点,记录一个边集 E,并根据 w_i 在当前位的取值分为两个边集 E_0,E_1。讨论 k 在这一位的取值:

这个做法可以被称为 01-Trie 分治。视 n,q,m 同阶,复杂度 O(n \log n \log V),可以通过。

:::::

:::::info[代码]

const int N = 1e5 + 5;
using edge = tuple<int, int, int>;

i64 cur, ans[N];
struct unionfind {
    int fa[N], sz[N];
    static i64 C(i64 x) {return x * (x - 1) / 2;}
    stack<int> st;
    unionfind() {iota(fa, fa + N, 0), fill(sz, sz + N, 1);}
    int find(int x) {return x == fa[x] ? x : find(fa[x]);}
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        cur -= C(sz[x]) + C(sz[y]);
        fa[x] = y, sz[y] += sz[x], st.emplace(x);
        cur += C(sz[y]);
    }
    void undo(int x) {
        while ((int)st.size() > x) {
            int u = st.top(), p = fa[u]; st.pop();
            if (u == p) continue;
            cur -= C(sz[p]);
            sz[p] -= sz[u], fa[u] = u;
            cur += C(sz[p]) + C(sz[u]);
        }
    }
} dsu;

int n, m, k, q;
#define ls son[0][u]
#define rs son[1][u]
int cnt = 1, son[2][N << 5];
vector<int> val[N << 5];

void insert(int x, int id) {
    int u = 1;
    val[u].emplace_back(id);
    for (int d = 30; d >= 0; d--) {
        if (!son[x >> d & 1][u]) son[x >> d & 1][u] = ++cnt;
        u = son[x >> d & 1][u];
        val[u].emplace_back(id);
    }
}

void solve(int u, int dep, vector<edge>& e) {
    if (e.empty() || dep < 0) {
        for (int id : val[u]) ans[id] = cur;
        return;
    }
    vector<edge> e0, e1;
    for (auto& [u, v, w] : e) {
        if (w >> dep & 1) e1.emplace_back(u, v, w);
        else e0.emplace_back(u, v, w);
    }
    if (k >> dep & 1) {
        if (ls) {
            int step = dsu.st.size();
            for (auto& [u, v, w] : e0) dsu.unite(u, v);
            solve(ls, dep - 1, e1), dsu.undo(step);
        }
        if (rs) {
            int step = dsu.st.size();
            for (auto& [u, v, w] : e1) dsu.unite(u, v);
            solve(rs, dep - 1, e0), dsu.undo(step);
        }
    } else {
        if (ls) solve(ls, dep - 1, e0);
        if (rs) solve(rs, dep - 1, e1);
    }
}

void _main() {
    cin >> n >> m >> k;
    vector<edge> e;
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        e.emplace_back(u, v, w);
    }
    cin >> q;
    for (int i = 1, v; i <= q; i++) cin >> v, insert(v, i);
    solve(1, 30, e);
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
} 

:::::