题解：P9083 [PA 2018] Ryki

lalaouye · 2025-05-11 22:12:17 · 题解

下文称每个吼不出来的熊叫特殊熊。

首先独立变成两个一维问题，然后放在数轴上做，自然地，我们会考虑这个过程的性质，不难观察到以下几点：

1. 相对位置不变。
2. 只有合并在一起的点才不会对对方产生影响，否则必定会产生相对位置带来的影响。
3. 叫一次对于两侧点之间的距离不会改变，除了自己与两侧点和两侧点之间。
4. 合并的点在原顺序上对应着一个区间。

这些都是必须意识到且注意到的性质，但是单次维护这个东西总是要 \mathcal{O}(n\log n) 的，然而每次只删掉一个点，我们不妨考虑其与原本每只熊都叫一次的答案关系。从感觉上变化是不大的。首先考虑到少叫一次相当于有些点少移动了一格子，但是有可能就是因为少叫了一次导致一只熊可以被另一侧多拉 1 到 2 次，总之每只熊顶多只会产生 1 的距离变化量。

有经验的你不难猜到，变化量为 -1,0,1 的熊在相对位置上构成了三个区间，这是不难证明的，感受一下发现越靠中间越可能受到阻挡，越靠左或越靠右的就越能因为多叫这一次而移动，那么我们只需要对于每只熊处理出属于它的 [l_i,r_i]，表示这个区间内的熊的位置不变，于是我们就能二维数点了。

然后我们又能发现一个比较显然的结论，一只熊因为特殊熊多吼一次而受到额外阻挡时，必然已经跟特殊的那只熊合并了。

下面我们考虑对于每只熊处理出它的 [l_i,r_i]，注意了，以下讨论的情况都是钦定第 i 只熊吼了，在它吼的情况找出 [l_i,r_i]。

这个东西很抽象，必须要从过程去找到它，因为它跟过程是紧密相关的。那么我们考虑当第 i 只熊开始吼的时候，吼了跟没吼都一样的那些熊显然是之前已经跟 i 合并在一起的熊。而对于之后的一只熊 j，如果它在吼之前不与 i 合并在一起，显然是不会影响 [l_i,r_i] 的，根据之前的结论可以发现，他们不论怎样都会一起移动一格。也不会有新增加的，因为新增加的显然得与 i 合并在一起，而当前 j 都没跟 i 合并在一起，又怎么去影响别人呢？

下文称第 i 只熊为相对位置意义下的第 i 只，至于说原顺序的我们称其为编号第 i 只熊。

如果 j 跟 i 合并在了一起就需要好好考虑了，设当前 [L,R] 里的熊合并在了一起，满足 i,j\in[L,R]，那么首先显然 [l_i,r_i]\subseteq[L,R]，我们考虑 [l_i,r_i] 的意义，对于第 r_i+1 这只熊，i 操作了的情况下他们合并在了一起，而若没操作则意味着 r_i 并没有与 r_i+1 合并在了一起！此时的 r_i+1 在没吼的情况下的坐标是要加一的，于是当 j>r_i 时，[l_i,r_i] 都将移动，而 [L,l_i-1] 这些熊回到了原位。若 j<l_i 同理，而若 j\in[l_i,r_i] 时，当前 [L,R] 的熊都将回到原位。

于是我们可以 \mathcal{O}(n^2) 完成这道题了。考虑这个东西是能一起做的，这也是我们优化它的方向。我们维护合并到了一起的区间，称他们为 A 区间，但是除了公用 A 区间以外看起来各个 [l_i,r_i] 之间没有什么关系，貌似没办法一起做。

但是我们注意到一次操作后，被改变的所有 [l_i,r_i] 区间都满足要么 l_i=L，要么 r_i=R，不难证明任意时刻我们都可以用若干个极长不交的区间表示出这些区间，里面嵌套了一些要么 l_i=L 要么 r_i=R 的区间，我们记所有这样的区间为 B 区间，我们需要记录三个集合信息 S_L,S_R,id，分别表示左端点在 L 的区间集合，右端点在 R 的区间集合，注意到我们可以将相同区间放到一个并查集中，集合中的元素是个二元组，分别表示它的另一个端点和它的编号，因为它代表的是一个等价类，然而对于刚好是该区间的集合我们会额外分到 id，id 也只用放这些区间等价类并查集中的根。

然后我们每次操作会找到 [L,R] 中所有 B 区间，并把他们放到自己新建的 B 区间中。我们还是得讨论位置，当前 B 区间为 [L',R']，那么若 R'<j 的话，直接将 (L'-1,id') 丢进 S_L，然后将 S_{L'} 也丢尽 S_L，对于 S_{R'} 我们需要将每个二元组的第一个元减一再丢进去，对于 j<L' 类似的讨论，而对于 j\in[L',R'] 的情况，首先将 id' 进入新的 id，然后对于 S_{L'} 中的信息如果包含了 j 也会并入 id，否则我们会把他们搞在 [L,L'-1] 中，S_{R'} 类似，注意到直接暴力枚举复杂度均摊是对的，因为我们顶多会新增 3 个本质不同的信息，所以均摊下来对完了。

特别的我们发现有一种操作需要给每个信息的第一个元减一，但是我们可以利用一个小 trick，把区间变为左闭右开区间，这样我们便无需额外减一了！因为注意到我们涉及到整体左端点右端点互换都只有一个规则，直接变成左闭右开即可。

利用启发式合并可以做到 \mathcal{O}(n\log n)，但是实际上可以更优秀，我们注意到对集合的操作相当于把它分到两个集合中并删除，或者整体合并，这个东西可以链表直接做，于是可以线性完成这个过程。

考虑算出答案，由于答案式子是个没什么道理的乘积式，不妨直接写出答案式子：