[题目链接](https://codeforces.com/contest/2176/problem/E) 一道很妙的贪心题 先考虑不存在修改时怎么做 对于一个元素 $i$，它如果被元素 $j$ （可以是 $i$ 自己）消除，一定满足 $a_j\ge a_i$ 并且在元素 $i$ 和元素 $j$ 之间的任意一个元素 $k$，一定需要 $a_k\le a_j$，这是因为如果 $a_k>a_j$ 的话，元素 $j$ 就不可能跨过 $k$ 去消除 $i$ 那么，从贪心的角度考虑，答案的下限一定是每个元素都被满足条件的 $j$ 中 $c_j$ 最小的那个元素消除 假设这个下限真的可以取到，现在需要找到每个 $i$ 可能被哪些 $j$ 消除 很容易发现上面的要求实际上就是一棵笛卡尔树，每个元素只可能被它自己或者某个祖先消除，**那么消除它的最小代价就是根节点到它路径上 $c$ 的最小值**。 但当两个元素的 $a$ 相同时，这就会产生问题，它们没有严格的上下级关系，在没有更大的 $a$ 阻挡时它们可消除的范围是相同的，也就是说它们是等价的！ 那就需要换一种方式构造这个类似笛卡尔树的东西： - 整个区间的根节点是 $a_i$ 最大的元素，因为它们是等价的，可以让它们都是根节点，$c$ 只要取最小的一个即可 - 它们会把区间分成多段，多段间无法跨过这个最大的 $a_i$，每一段都是这个根节点的一个子节点，这就转化成了一个子问题 计算代价的方式还和刚才的相同 而这时，加入修改操作也变得很简单了，把一个 $c_i$ 变成 $0$，它子树中的元素都可以由它消除，即消除代价都为 $0$，只需要把子树中原有的代价减去即可（加个标记使每个节点只被减一次可以保证线性复杂度） 那么为什么贪心的下限一定可以取到呢？ 其实在刚刚计算答案的过程中已经可以构造出来了，从叶子往根按照要求消除恰好可以取到！ [CODE](https://codeforces.com/contest/2176/submission/356698501) Loading... [题目链接](https://codeforces.com/contest/2176/problem/E) 一道很妙的贪心题 先考虑不存在修改时怎么做 对于一个元素 $i$，它如果被元素 $j$ （可以是 $i$ 自己）消除，一定满足 $a_j\ge a_i$ 并且在元素 $i$ 和元素 $j$ 之间的任意一个元素 $k$，一定需要 $a_k\le a_j$，这是因为如果 $a_k>a_j$ 的话，元素 $j$ 就不可能跨过 $k$ 去消除 $i$ 那么，从贪心的角度考虑，答案的下限一定是每个元素都被满足条件的 $j$ 中 $c_j$ 最小的那个元素消除 假设这个下限真的可以取到，现在需要找到每个 $i$ 可能被哪些 $j$ 消除 很容易发现上面的要求实际上就是一棵笛卡尔树，每个元素只可能被它自己或者某个祖先消除，**那么消除它的最小代价就是根节点到它路径上 $c$ 的最小值**。 但当两个元素的 $a$ 相同时，这就会产生问题，它们没有严格的上下级关系，在没有更大的 $a$ 阻挡时它们可消除的范围是相同的，也就是说它们是等价的！ 那就需要换一种方式构造这个类似笛卡尔树的东西： - 整个区间的根节点是 $a_i$ 最大的元素，因为它们是等价的，可以让它们都是根节点，$c$ 只要取最小的一个即可 - 它们会把区间分成多段，多段间无法跨过这个最大的 $a_i$，每一段都是这个根节点的一个子节点，这就转化成了一个子问题 计算代价的方式还和刚才的相同 而这时，加入修改操作也变得很简单了，把一个 $c_i$ 变成 $0$，它子树中的元素都可以由它消除，即消除代价都为 $0$，只需要把子树中原有的代价减去即可（加个标记使每个节点只被减一次可以保证线性复杂度） 那么为什么贪心的下限一定可以取到呢？ 其实在刚刚计算答案的过程中已经可以构造出来了，从叶子往根按照要求消除恰好可以取到！ [CODE](https://codeforces.com/contest/2176/submission/356698501) 最后修改：2026 年 01 月 07 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏