本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-10 14:43:58

非常毒瘤的分桃题。

维护每个数的补后继，记作 $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$ 原来是 $Q$ 中最大的，那么更新其等前驱的补后继

• 如果 $x$ 是现在 $Q$ 中最小的，那么将以 $y$ 为补后继的数的补后继更新为 $x$

• 如果 $x$ 是现在 $Q$ 中最大的，那么从其等前驱抢来补后继

上面那几把东西假了。

$x$ 原来的后继？要给比 $x$ 大的且比 $x$ 原来后继小的，即最大的小于 $x$ 原后继的在 $Q$ 中的。

原来以 $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$。

这样之后，我们做区间最大值就可以了。线段树搞定。