CF217E 题解

· · 题解

提供一个 O(n\log k + k) 的解法。

首先我们将时间倒流，从后往前考虑每次操作对最终的前 k 个字符造成的影响。

设当前没有被确定的位置构成一个序列 p_1 < p_2 < \dots < p_m。

对于一次操作 [l,r]，p_{r+1},p_{r+2},\dots,p_{r+(r-l)} 的字符是由 p_l,p_{l+1},\dots,p_{r} 复制过来的。我们忽略其中超过 m 的下标。我们将 p_{r+1},p_{r+2},\dots,p_{r+(r-l)} 中的每个 p_i 向 p_l,p_{l+1},\dots,p_{r} 中对应的 p_j 连边，表示 p_i 由 p_j 复制过来。然后把 p_{r+1},p_{r+2},\dots,p_{r+(r-l)} 全部删去。用链表维护即可。

所有操作考虑完以后，对于剩余的 p_i，其上的字符即为原字符串 s 的第 i 个字符 s_i。

我们对建出来的图搜索，即可确定所有字符。因为我们从后往前连边，所以我们其实不需要搜索，从前往后遍历一遍就行。

容易发现边数是 O(k) 的，找到 p_l 之后连边的总复杂度也是 O(k)。

现在的问题是，我们每次都需要找到链表中第 l 个数的位置，而链表不支持二分，暴力找总复杂度 O(nk)，不能接受。

我们使用线段树维护 [1,k] 区间中每个位置是否在链表里。当删除节点 p_{r+1},p_{r+2},\dots,p_{r+(r-l)} 时，我们在线段树上将 [p_{r+1},p_{r+(r-l)}] 修改为 0。查询第 l 个数的位置在线段树上二分即可。

时间复杂度 O(n\log k+k)。但是实际效率不如用树状数组实现的 O((n+k)\log k)。

O(n\log k+k) 代码

O((n+k)\log k) 代码