P5211 [ZJOI2017] 字符串

向日葵小班 · 2023-08-09 10:54:03 · 题解

题目大意：

  维护一个长度为 n 的动态字符串 s，字符集为 1 ∼ 10^9。支持下列操作：

• 区间加。

• 询问某个子串的最小后缀的开头位置。

    n\le 2\times 10^5,m\le 3\times 10^4。

这题要先学会一种东西: 最小后缀。

定义：

  记 \operatorname{suf(S)} 为 S 的后缀集合。

  记 \operatorname{minsuf(S)} 为 S 的最小后缀。

  记 \operatorname{Ssuf(S)} 为 \left\{V∈\operatorname{suf(S)}|T,VT=\operatorname{minsuf(ST)}\right\}，意思就是说，在 S 后面加一个串之后，可能成为最小后缀的后缀。即 Significant Suffixes，简称为 \operatorname{Ssuf}。

定理：

  1. 对于任意两个 \operatorname{Ssuf} U,V，|U|<|V|⇒U 是 V 的前缀。

  若 U 并非 V 的前缀，无论向串后面加怎样的 T，UT 和 VT 的大小关系还是由 U,V 的大小关系决定。

  所以 U,V 只有一者有可能是 \operatorname{Ssuf}，矛盾。

  注意，U 同时也是 V 的后缀，所以 U 是 V 的 \operatorname{Bd}。

  2. 若串 S 有两个 \operatorname{Ssuf}U,V 满足 |U|<|V|，则 2|U|<|V|。

  考虑反证。假设 |U| < |V| < 2|U|，由上一个定理可得 U 是 V 的 \operatorname{Bd}。

  即对应长度为 \left|V\right|-\left|U\right|<|U|<2|U| 的周期。记一个周期为 T，有U=T^kC,V=T^{k+1}C。

由最小后缀，存在R (可空)使得UR<VR⇒T^kCR<T^{k+1}CR⇒CR<TCR⇒CR<UR，注意到 CR 也是后缀，故 UR 注定不可能是最小后缀，矛盾。

推论：|\operatorname{Ssuf(S)}|=O(\log|S|)。

回到这题上，我们来讲讲这个题目的解法：

  先写个分块，支持 O(\sqrt{n}) 区间加，O(1) 查询区间 Hash 值。

  考虑使用线段树维护 \operatorname{Ssuf} 集合。查询时，答案只可能是拆出来的 O(\log n) 个节点的 \operatorname{Ssuf} 集合的元素，共 O(\log^2n) 个，大力比较，复杂度 O(\log^3n)。

  修改时，只有被修改区间部分包含的 O(\log_n) 个点（即在线段树上拆区间时访问的点）的 \operatorname{Ssuf} 受到影响。

  合并两个儿子的信息时，设左侧的串为 S_1，右侧的串为 S_2。我们要通过 \operatorname{Ssuf(S_1)},\operatorname{Ssuf(S_2)} 得到 \operatorname{Ssuf(S_1,S_2)}。

  由于在线段树上有 |S_2|≤|S_1|≤|S_2|+1 （两侧长度相近），由倍长定理得至多有一个 \operatorname{Ssuf(S_1)} 中的元素被保留到 \operatorname{Ssuf(S_1,S_2)} 中。如何挑出那个元素？

  对于 U,V∈\operatorname{Ssuf(S_1)}，不妨设 US_2<VS_2，若 US_2 不是 VS_2 的前缀，则 VS_2 可以排除（显然），若 US_2 是 VS_2 的前缀 \operatorname{Bd}，则 US_2 可以排除（证明同前文定理）。

  根据这一规则可以 \operatorname{Ssuf(S_1)} 排除到只剩一个元素 X，记 P=XS_2。

  初始时令集合 \operatorname{Ssuf(S_2)}，然后枚举其中的串 V 进行如下操作：

• 若 V 是 P 的前缀，不做任何操作。

• 若 V 不是 P 的前缀，且 V < P，抛弃 P。停止。

• 若 V 不是 P 的前缀，且 V > P ，抛弃 V。

  若最终 P 未被抛弃，则将其加入 S。得到的 S 就是 \operatorname{Ssuf(S_1,S_2)}。（实际上，直接令 S=\operatorname{Ssuf(S_2)}∪{P} 复杂度也是对的） 总复杂度 O(\log^2n+m\log^3n+m\sqrt{n})。