再谈铲雪

· · 算法·理论

本文将采用启发式的题解模式，引导读者一步步自己想出做法。

Fun Fact: 这篇文章编写时，BJ 正在下雪，并且 rdfz 的一些同学严肃进行了铲雪，铲出了若干非平凡图案（

1. 铲雪模型

“铲雪”这个名字来源于一场校内模拟赛。下面是基本的铲雪模型：

给你无向图 G，点带权，一次操作将一个特定子图 G' 上所有点的点权减去 1，问元素全变成 0 的最少操作数。

在铲雪题中，G,G' 以及操作形式都会有变化。

2. 连续铲雪

2.1 链上铲雪

::::info[提示 1] 考虑一个“顺带”的思想，用较大的 a_i 的“顺带”铲掉较小的 a_{i-1}。 ::::

::::info[提示 2] 考虑差分转化。尝试构造一个方案，使得最优解可以取到。 ::::

:::::success[题解]

我们记 n 为序列长度，a 为序列，并且约定 a_0=0。

可以证明答案就是所有正差分之和，即

\sum_{i=1}^n \max(0,a_i-a_{i-1})

::::info[感性理解]{open} 根据提示 1，用较大的 a_i 的“顺带”铲掉较小的 a_{i-1}。

于是较小的 a_{i-1} 会被铲没，较大的 a_i 减小 a_i-a_{i-1} 的高度。

无论什么策略，必然要花费 a_{i-1} 的代价（因为这个位置铲没以后，接下来的区间不能跨过 i-1）。而 a_i-a_{i-1} 的代价是免费的。因此贪心是正确的。 ::::

::::info[严格证明] 用差分刻画一下这个操作。

记 d_i=a_i-a_{i-1}。

:::info[必要性]{open} 一次操作至多让一个大于 0 的 d_i 减 1，故最优解不小于 \sum \limits_{i=1}^n \max(0,d_i)。 :::

:::info[充分性]{open} 只需给出一个最优解的构造。先给出两个观察：

可以按如下方法得到最优解：

不难发现操作次数就是 \sum \limits_{i=1}^n \max(0,d_i)。 ::: :::: :::::

2.2 环上铲雪

::::info[提示 1] 考虑答案的下界。 ::::

::::info[提示 2] 环和序列很像，可以参考上一题。 ::::

::::info[提示 3] 序列中的最大值也对答案下界有贡献。 ::::

::::info[提示 4] 可能你得到了一个比较离谱的结论，能否尝试证明？ ::::

:::::success[题解] 我们记 n 为环长，a 为序列。

可以发现答案有两个下界，即 M=\max \limits_{i=1}^n a_i 和 D=a_1-a_n+\sum \limits_{i=2}^n \max(0, |a_i-a_{i-1}|)。D 其实就是上一题的答案变成环上差分。

答案就是 \max(M,D)。

::::info[严格证明] :::info[必要性]{open} 一次操作至多让 D,M 减少 1，故最优解不小于 \max(M,D)。 :::

:::info[充分性]{open} 只需给出一个最优解的构造。下分三种情况讨论：

  1. 当 M=D 时，只需使用上一题的方法即可得到最优解。

对于 M \ne D 的情况，考虑规约到 M=D。

  1. 当 M>D 时，有引理：环中没有 0。故直接整体减去 1 即可令 M \gets M-1，重复操作至 M=D。
    引理的证明：显然 D \ge \max \limits_{i=1}^n a_i-\min \limits_{i=1}^n a_i，当环中有 0 时得 D \ge M，与前提矛盾。
  2. 当 M<D 时，选择一个全为最大值的极长区间减去 1，则 D \gets D-1，而 M 至多减去 1，重复操作至 M=D。 ::: :::: :::::

2.3 树上铲雪

我们会先给出两个前置题目。

2.3.1 链上双点铲雪

::::info[提示 1] 去看环上铲雪。你是否得到了一些必要条件？ ::::

::::info[提示 2] 能否通过构造说明这些条件是充分的？ ::::

:::::success[题解] 我们记 n 为序列长度，a 为序列。

设 S=\sum \limits_{i=1}^n a_i,M=\max \limits_{i=1}^n a_i。当且仅当 S 为偶数且 2M \le S 时可行。

::::info[严格证明] :::info[必要性]{open} 首先 S 为奇数显然不可行。

若 M > \dfrac{1}{2} S，则最大值无法被其他数字消去。

由此证明 S 为偶数和 2M \le S 为可行的必要条件。 :::

:::info[充分性]{open} 进行归纳构造。首先容易验证 n \le 2 可行。

仿照环上铲雪的证明，只需重复操作至 0 在序列中。由于 2M \le S，一定可以构造出这种情况，于是忽略 0 后得到了若干规模在 [0,n-1] 中的子问题，归纳即可。 ::: :::: :::::

2.3.2 树上双叶铲雪

::::info[提示 1] 先找到一个根，自底向上求一些信息。 ::::

::::info[提示 2] 如果我们得到了儿子到父亲的一条路径，这条路径有几种选择？ ::::

::::info[提示 3] 去看链上双点铲雪的结论。尝试用数学语言刻画合法的充要条件。 ::::

:::::success[题解] 特判 n=2。然后选择一个度数不为 1 的点为根。

定义“线头”为一条可以从儿子到父亲的路径。

记 f_u 为 u 作儿子的线头数目，然后设 s_u=\sum \limits_{v \in \operatorname{son}(u)} f_v，即 u 作父亲的线头数目。

线头有两种选择：继续向上延伸，或者拐向另一个儿子（我们称这是两个线头合并）。二者的数目分别为 f_u 和 \dfrac{s_u-f_u}{2}。容易在 u 处列出方程：

a_u=f_u+\dfrac{s_u-f_u}{2}

移项得

f_u=2a_u-s_u

直接自底向上统计 f,s 即可。考虑可行的必要条件：

最终还要求根节点没有线头，即 f_{\operatorname{root}}=0。充分性照搬链上双点铲雪的构造即可。

有一些处理细节，给出代码。

:::info[代码]

constexpr int N = 1e5 + 86;
int tot = 0, head[N];
struct Edge {int next, to;} edge[N << 1];
void add_edge(int u, int v) {edge[++tot].next = head[u], edge[tot].to = v, head[u] = tot;}

int n, a[N], d[N];
long long f[N], s[N];
bool dfs(int u, int fa) {
    if (d[u] == 1) return f[u] = a[u], true;
    long long mx = 0;
    for (int j = head[u]; j != 0; j = edge[j].next) {
        int v = edge[j].to;
        if (v == fa) continue;
        if (!dfs(v, u)) return false;
        s[u] += f[v], mx = max(mx, f[v]);
    } 
    f[u] = 2 * a[u] - s[u];
    return 0 <= f[u] && f[u] <= a[u] && mx <= a[u];
}

void _main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n == 2) return cout << (a[1] == a[2] ? "YES" : "NO"), void();
    for (int i = 1, u, v; i < n; i++) cin >> u >> v, add_edge(u, v), add_edge(v, u), d[u]++, d[v]++;
    int rt = 1;
    for (int i = 1; i <= n; i++) if (d[i] > 1) rt = i; 
    cout << (dfs(rt, -1) && f[rt] == 0 ? "YES" : "NO");
}

::: :::::

2.3.3 真·树上铲雪

::::info[提示 1] 拓展一下树上双叶铲雪的线头思想。 ::::

::::info[提示 2] 考虑刻画每个节点的线头合并次数。 ::::

:::::success[题解] 仍然记 f_u 为 u 作儿子的线头数目，且 s_u=\sum \limits_{v \in \operatorname{son}(u)} f_v。但是由于不要求路径端点为叶子，因此它不满足树上双叶铲雪的递推式。

设 c_u 为 u 节点处线头合并次数，则它对答案的贡献为 \max(0,a_u-s_u+c_u)-c_u。结论为 c_u 取到上界时，答案最小。我们考虑求出 c_u。

综合以上四条我们得到：

\begin{aligned} f_u&=a_u-c_u\\ c_u&=\max(0,\min(a_u,\sum f_v-a_u, \lfloor \dfrac{\sum f_v}{2} \rfloor, \sum f_v -\max f_v)) \end{aligned}

得到 c 以后，f,s 自底向上计算即可。给出代码。

::::info[代码]

int opt, n, seed, a[N], u[N], v[N];
int tot = 0, head[N];
struct Edge {
    int next, to;
} edge[N << 1];
inline void add_edge(int u, int v) {
    edge[++tot].next = head[u], edge[tot].to = v, head[u] = tot;
}
long long f[N], s[N], c[N], ans;
void dfs(int u, int fa) {
    long long mx = 0;
    for (int j = head[u]; j != 0; j = edge[j].next) {
        int v = edge[j].to;
        if (v == fa) continue;
        dfs(v, u), s[u] += f[v], mx = max(mx, f[v]);
    }
    c[u] = max(0LL, min<long long>({a[u], s[u] - a[u], s[u] / 2, s[u] - mx}));
    ans += max(0LL, a[u] - s[u] + c[u]) - c[u];
    f[u] = a[u] - c[u];
}

void _main() {
    cin >> opt;
    if (opt == 1) {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i < n; i++) cin >> u[0] >> v[0], add_edge(u[0], v[0]), add_edge(v[0], u[0]);
    } else {
        cin >> seed >> n;
        Generate::n = n, Generate::seed = seed, Generate::RS(a, u, v);
        for (int i = 1; i < n; i++) add_edge(u[i], v[i]), add_edge(v[i], u[i]);
    }
    dfs(1, -1);
    cout << ans;
}

::::

::::info[感性理解]{open} 把线头合并变成延伸的话，可以在当前位置减少一次操作，但会支付未来的两次操作，故一定不优。必要性已经证明。 ::::

::::info[严格证明] 必要性其实在分析的过程中已经证明了，我们需要说明充分性。

:::info[充分性]{open} 考虑调整法，即说明 c_u 减小不优。

设 S=\sum f_v。当 a_u > S 时，根据递推式知 c_u=0，无法调整。

而对于 a_u \le S，c_u \gets c_u-1 时 f_u \gets f_u+1,s_u \gets s_u+2，答案变化量为 -1+1+2=2>0。

因此 c_u \gets c_u-1 只会使得答案变大。 ::: :::: :::::

3. 跳跃铲雪

3.1 链上跳跃铲雪

::::info[提示 1] 每个位置应该被一些“直线”和“跳线”覆盖。 ::::

::::info[提示 2] 直线是否一定优于跳线？ ::::

::::info[提示 3] 按 a_i,a_{i+1} 与 0 的关系分类讨论，决策当前位置的覆盖线。 ::::

::::info[提示 4] 如果你不知道当前位置填什么，考虑延迟决策。 ::::

::::info[提示 5] 不要想的过于复杂，考虑一遍扫描出答案。 ::::

::::info[提示 6] 维护一个标记表示可以无代价决策几条线。 ::::

:::::success[题解] 称第一类操作为“直线”，二三类操作为“跳线”。

我们声称，一段从 1 开始的长度 \ge 2 的非 0 极长区间用直线覆盖不劣。于是可以按 a_i,a_i+1 分类讨论：

我们在扫描的过程中记录 A,B 表示延伸到当前位置的直线与跳线的数目。若 a_i \ge A+B，则 a_i \gets a_i-A-B。否则有 W=A+B-a_i 条线无法延伸。

记录下 W 并延迟决策，则考虑新位置 a_j，该位置有 W 条无代价的线。在讨论对答案的贡献时处理一下，一遍扫描即可出答案。

::::info[代码] 写法来自第一篇题解。

#define int long long
const int N = 1e5 + 5;
int n, a[N];   

void _main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int res = 0, A = 0, B = 0, nB = 0, W = 0;           // nB 维护不同奇偶性的跳线数目
    for (int i = 2; i <= n + 1; swap(B, nB), i++) {
        if (a[i] < A + B) {
            W = A + B - a[i];
            if (W > B) A -= W - B, W -= W - B;
            if (W > A) B -= W - A, W -= W - A;
            A -= W, B -= W, a[i] -= W;
        } 
        a[i] -= A + B;
        int C = min(a[i - 1], a[i]);                    // 新增直线数目
        res += C, a[i - 1] -= C, a[i] -= C, A += C;     // 直线
        res += a[i - 1], nB += a[i - 1], a[i - 1] = 0;  // 跳线
        if (W) a[i] += W, res -= W, W = 0;                     // 标记
    } cout << res << '\n';
}

::::

::::info[声称的证明] 设极长区间为 [l,r]，其满足 \forall i \in [l, r], a_i > 0，且 a_{l-1}=a_{r+1}=0。

考虑调整，显然不可向 r+1 连出直线，合法方案只可能由 r-1 开始延伸跳线。则此时代价至少为 2。而原方案的代价恰好为 2，故调整不优。 :::: :::::

4. 循环铲雪

给出 m，一次操作将点权变为 (a_i\pm 1) \bmod m。

4.1 链上循环铲雪

一个区间询问的版本：P4846。

4.1.1 全局询问

:::info[提示 1] 考虑差分转化。 :::

:::info[提示 2] 考虑目标状态的形态。 :::

:::info[提示 3] 取模是难刻画的，能否提前决策是否取模？ :::

:::info[提示 4] 考虑每个数取值对答案的影响，思考如何确定影响。 :::

:::::success[题解] 做一个差分转化，设 d_i=a_i-a_{i-1} 并且约定 a_0=a_{n+1}=0。

那么一次操作就是选择两个 i,j，使得 d_i \gets d_i \pm 1, d_j \gets d_j \mp 1。注意到目标态即 d_i \equiv 0 \pmod m。显然 |d_i| \ge 2m 不优，所以 d_i \in \{-m,0,m\}。

又因为 a_{n+1}=\sum \limits_{i=1}^{n+1} d_i=0，所以我们得到目标状态的刻画：d_i \in \{-m,0,m\}，且 m 与 -m 成对出现。

考虑链上铲雪的结论，\sum \limits_{i=1}^{n} \max(0,d_i) 这个东西不好计算，而根据 a_{n+1}=\sum \limits_{i=1}^{n+1} d_i=0，故正差分与负差分绝对值之和相等，可以改写为 \dfrac{1}{2}\sum \limits_{i=1}^{n+1} |d_i|。

取模这个东西难以处理。事实上，我们可以提前决策每个数的最终取值，即无代价地选择 i,j，令 d_i \gets d_i-m,d_j \gets d_j+m，目标态即 \forall i \in [1,n+1], d_i=1。

对于正差分 v，其减去 m 后的答案变化量为 2v-m。对于负差分 -v，其加上 m 后的答案变化量仍为 2v-m。

注意到 \pm m 成对出现，将答案变化量处理出来以后排序，做一个前缀和然后枚举分界点即可，整个做法的正确性显然。

::::info[代码]

long long solve(int m) {
    long long sum = 0;
    for (int i = 1; i <= n + 1; i++) d[i] = a[i] - a[i - 1], sum += abs(d[i]);
    vector<long long> p1, p2;
    for (int i = 1; i <= n + 1; i++) {
        if (d[i] < 0) p1.emplace_back(m + 2 * d[i]);
        else p2.emplace_back(m - 2 * d[i]);
    }
    sort(p1.begin(), p1.end()), sort(p2.begin(), p2.end());
    for (int i = 1; i < (int) p1.size(); i++) p1[i] += p1[i - 1];
    for (int i = 1; i < (int) p2.size(); i++) p2[i] += p2[i - 1];
    long long res = sum;
    for (int i = 0; i < min<int>(p1.size(), p2.size()); i++) res = min(res, sum + p1[i] + p2[i]);
    return res / 2;
}

:::: :::::

4.1.2 区间询问

::::info[提示 1] 考虑上面查询时，我们需要什么。能否用数据结构维护？ ::::

::::info[提示 2] 考察答案研究的对象，思考它的性质，或者打表观察。 ::::

:::::success[题解] 考虑我们实际上干了一个什么事情，可以发现我们需要的是 p1、p2 的前 k 小数的总和。

可以用可持久化权值线段树维护一个区间的前 k 小之和。

考虑省去枚举分界点的部分。对 p1[i] + p2[i] 打表，或者感性理解一下可以知道这是一个单谷函数，可以三分求出 i。

复杂度 O(q \log n \log V)。

::::info[单谷的证明] 我们设 p_1(k) 为满足 d_i<0 的 m+2d_i 的前 k 大数之和，p_2(k) 为满足 d_i>0 的 m-2d_i 的前 k 大数之和，然后令 f(k)=p_1(k)+p_2(k)。

设负的 d_i 共有 p 个，记为 x_1, x_2, \dots, x_p，满足 x_1 \leq x_2 \leq \cdots \leq x_p < 0。对应的 a_i = m + 2x_i，则有 a_1 \leq a_2 \leq \cdots \leq a_p。于是 p_1(k) = \sum\limits_{i=1}^k a_i。

同理设正的 d_i 共有 q 个，记为 y_1, y_2, \dots, y_q，满足 y_1 \geq y_2 \geq \cdots \geq y_q > 0。对应的 b_i = m - 2y_i，则有 b_1 \leq b_2 \leq \cdots \leq b_q。于是 p_2(k) = \sum \limits_{i=1}^k b_i。

令 K = \min(p, q)，则对于 k = 0, 1, \dots, K，有

f(k) = \sum_{i=1}^k (a_i + b_i) = \sum_{i=1}^k \left(2m + 2(x_i - y_i)\right) = 2mk + 2\sum_{i=1}^k (x_i - y_i)

其差分

\Delta f(k) = f(k+1) - f(k) = 2m + 2(x_{k+1} - y_{k+1})

由 x_i 单调递增，y_i 单调递减，则序列 x_i - y_i 单调递增。因此 \Delta f(k) 也单调递增。综上，f(k) 是一个凸序列。 :::: :::::

4.1.3 一道联考题

给出 q 次操作，每次操作对 a 中不小于 y 的数加上 x，然后查询以 m+x 为模数的链上循环铲雪。操作之间独立。

::::info[提示 1] 仍然考虑套用区间询问的做法。 ::::

::::info[提示 2] 你可能需要讨论正负差分的影响。是否可以统一为一种？ ::::

::::info[提示 3] 考虑离线，则每个 i 对哪些询问有影响？ ::::

:::::success[题解] 比较可惜的是笔者场上 All in 这个题，最后 48pts 遗憾离场。

仍然可以三分答案，考虑维护 p1、p2。

笔者的赛时做法是讨论 a_i,a_{i-1} 的四种大小关系，被出题人 lhx 大手子锐评这是“荒唐的”。

实际上考虑循环铲雪的本质，每个数在一个以 m 为长度的环上绕圈，那么对于负差分将其对 m 取模，处理一下代价就转化为正，故只需分有无影响讨论即可。

考虑将询问离线。则 i 对于 a_{i-1} < x \le a_i 的询问 (x,y) 有影响。自然地，对 x 排序扫描线，询问三分即可。需要实现一个动态维护前 k 大的数据结构，使用权值树状数组 / 权值线段树 / 01-Trie / FHQ-Treap 均能将本题做到 O(q \log^2 n)。

本题暂未找到单 \log 做法。 :::::

5. 总结

铲雪模型是一种比较灵活的思维题。一般要贪心或者推结论。

在证明中，一般考虑分为两步，先证必要再证充分，必要性一般是好证的，充分性需要有比较厉害的构造水平。

顺带一提，这种题的通用做法是线性规划。由于作者太菜，本文只介绍了贪心的思路。

6. 拓展

铲雪题远远没有被出完！

即使是本文提到的铲雪类型，也应当有链 / 环 / 树 上 连续 / 跳跃 / 循环 / 跳跃循环 铲雪共 3 \times 4=12 种题，并且还可以在其他图上铲雪（基环树等），或者带上区间查询 / 子树查询 / 树链查询 / 单点修改等。

然而本文中提及的本质不同的原题只有 5 种，这远少于应当铲雪题应当有的规模。

然而截止本文完成前，作者并不会任何其他类型的铲雪题。如果有大手子会了其中任何一种，欢迎在评论区交流或者搬到模拟赛里狙击别人（

所以基环树上铲雪怎么做？

笔者声称，先对树铲雪再对环铲雪可以得到最优答案。

具体地，对每棵树进行一次铲雪求出线头数目，则问题转化为一个带权环上铲雪，每次可以从环上一个点免费开启一条线，还可以以负代价合并两条线。

但是本人太菜了，做不出来这个东西。希望有大手子将其做完 / 证伪 / 证明 NPC。

单点清空的铲雪怎么做？

这是大手子 zzh 老师提出的。

考虑给铲雪增加一个操作：选择一个位置使之变为 0。

感觉最简单的序列清空铲雪都不会做了。