P6544 [CEOI2014] Cake 题解

hegm · 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 个数，复杂度可以接受。