自动搬运

查看原文

来自洛谷，原作者为

	hegm 此身为薪，炬成灰亦照大汉长明。

搬运于2025-08-24 22:21:46，当前版本为作者最后更新于2023-06-10 11:04:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P6544 [CEOI2014] Cake

比较有意思，先不考虑修改操作，只看询问。

非常简单，对于 $b$ 到 $a$（不包含）的区间找到最大值 $mx$，然后找反方向第一个比这个值大的点 $c$ 那么答案就是区间 $(b,c)$ 的长度。

证明：

考虑现在先把 $a$ 删掉了，那么想要删掉 $b$，就必须要删掉 $a\sim b$ 之间的全部蛋糕，删掉他们的条件是另一侧出现了大于这个区间最大值的与元素，所以区间另一侧就是 $c$。

首先这个东西可以用线段树简单解决。

考虑修改操作，如果我们线段树存贮的是排名那么修改相当于对在 $[e,w_i)$ 的权值区间的位置进行 $+1$ 操作，这是不好做的，但是我们似乎不太能存贮权值，因为修改是将某个元素变为某个排名，如果是将 $i$ 插入 $3,4$ 两个权值之间，那么就需要小数了，精度容易爆炸。

考虑特殊性质：

这块蛋糕的美味度会变成所有蛋糕中前 $10$ 大的。

我们不妨记录相对权值，那么在修改的时候，将前 $e-1$ 大的 $+1$ ，然后将 $w_i$ 变为之前第 $e$ 大的多 $1$。

容易发现，这样的话每次最多修改 $10$ 个数，复杂度可以接受。