P6617 查找 Search 分析

· · 个人记录

非常毒瘤的分桃题。

维护每个数的补后继，记作 s(x)；再设 Q(x) 表示与 x 相同的数组成的下标集合。

对 Q(x)，只有最大的那个下标能得到 s(x)，其他的 s(x) 都是零，显然是正确的。

我们用 set 维护 Q(x) 即可。然后考虑点修。

点修 x 为 y 后会导致什么？设 x 上原来为 u，那么 Q(u) 中要删去 x，Q(y) 中加上 x。

上面那几把东西假了。

原来以 $x$ 为后继的？给 $Q(x)$ 中最小的大于原来以 $x$ 为后继的。 $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ 是最小的大于 $x$ 的。 以 $y$ 为后继的？找第一个大于其的。 --- -- upd 7.29 这个题看起来并没有那么难。 我们设一个数 $x$ 的前驱，为 $w - x$ 的位置，那么问题就转化为求区间前驱的最大值，看它是不是不小于 $l$。 我们考虑点修带来的变化。首先发现，对于两个有相同前驱的数，下标大的那个的前驱是不需要维护的。 那么这样，我们就只保留一堆数字中最靠前的那个数的前驱位置，其他的就扔掉不管。 现在考虑点修。 首先，如果有 $y$ 使得 $p(y) \ne x$ 且 $y \ne p(x)$ 的，那么 $y$ 是不会变的。 对于以 $x$ 为前驱的数，我们找和 $x$ 相同的，且最靠右的那个来替换。 然后，我们把 $x$ 原来的前驱让给和他相等的最靠左的那个。 这样，$x$ 就能大胆得变成别的数了。设 $x$ 变成了 $y$，那么如果 $x$ 的位置比 $y$ 里头最靠前的还要靠前（同时肯定要在它的前驱后头），那么就把原来 $y$ 的前驱抢过来； 如果以 $y$ 为前驱的数，这时候如果 $x$ 是最大的，我们就把原来前驱替换成 $x$。 这样之后，我们做区间最大值就可以了。线段树搞定。