题解 P5211 【[ZJOI2017]字符串】

zghtyarecrenj · 2020-04-13 07:48:00 · 题解

Upd 2020/06/15：优化了 \overline 太丑的问题，添上代码。

ZJOI2017 字符串

前置芝士：Lyndon 分解，Significant Suffixes，线段树，字符串哈希，分块。

如果你会 Significant Suffixes 相关知识，请阅读 [0 Marks & Facts] 后直接跳到后面的 进入正题。

0 Marks & Facts

我们定义两个字符串 a 和 b，如果 a 的字典序 <b，则我们称 a < b。
如果 a 是 b 的前缀且 a \ne b，则我们称 a \sqsubset b。
如果 a 是 b 的前缀，则我们称 a \sqsubseteq b。
如果 a < b 且 a 不是 b 的前缀，则我们称 a \triangleleft b。即 a \triangleleft b \Longleftrightarrow (a < b) \wedge (a \not\sqsubseteq b)。
a^n$ 表示 $n$ 个 $a$ 拼接在一起。e.g. ${a^2b} = {aab}
我们定义字符集为 \Sigma，组成的字符串为 \Sigma^*，\Sigma^+ = \Sigma^* \setminus \{\epsilon\}
\operatorname{pref}^+(a) = \operatorname{pref}(a) \setminus \{a,\epsilon\},\ \operatorname{suf}^+(a) = \operatorname{suf}^+(a) \setminus \{a, \epsilon\}

一些非常显然的 Fact:

如果 a \triangleleft b，则 {au} < {bv}。

1 Lyndon Words

1.1 Definition

Lyndon Word：一个串是一个 Lyndon Word 当且仅当 \forall a 的后缀 b，有 a < b。

### 1.2 Chan-Fox-Lyndon Factorization 又称 Lyndon Decomposition。我们定义 $\operatorname{CFL}(s)$ 是一个对于 $s$ 串的划分，即划分成了 ${w_1w_2\cdots w_k} = s$，使得所有 $w_i$ 是 Lyndon Word，并且 $w_1 \ge w_2 \ge \cdots \ge w_n$。 #### Theory 1.2.1 Lyndon Concatanation 这是一个很显然的结论。 > 如果 $a, b \in \mathcal L$，且 $a < b$，则 $\overline {ab} \in \mathcal L$。由于 $a < b$，我们有 ${ab} < b$。接下来我们分两种情况讨论。 i) $a \not \sqsubseteq b$：根据 $a < b$，我们有 $a \triangleleft b$。所以 ${ab} \triangleleft b \implies {ab} < b$。 ii) $a \sqsubseteq b$：令 $b={ac}$，则 ${ab} = {a^2c}$。因为 $b \in \mathcal L$，所以 ${ab} < b \implies {a^2c} < {ac} \implies {ac} < c$，所以 $b < c$。所以，$\forall d \in \operatorname{suf}^+(b), \ {ab} < b < d \implies \forall c \in \operatorname{suf}^+(a),\ a \triangleleft e \implies {ab} \triangleleft {eb}$。$\blacksquare

Theory 1.2.2 Existence of CFL

这个结论和 [Theory 1.2.3] Uniqueness of CFL 是两个很有趣的结论。

对于任意的串 s，\operatorname{CFL}(s) 一定存在。

我们考虑，单个的字母一定是 Lyndon Word。

根据 [Theory 1.2.1 Lyndon Concatanation]，我们可以把字典序小的两个 Lyndon Word 并起来，所以我们把所有的字典序单增的序列都并起来，剩下的就是一个合法的 CFL。\blacksquare

Theory 1.2.3 Uniqueness of CFL

对于任意的串 s，\operatorname{CFL}(s) 一定唯一。

反证法，假设有两种方案。我们取第一个不同的位置，可以很容易地得到矛盾，因为这个和 CFL 的定义矛盾了。\blacksquare

Q: 为什么不写详细点呢…… A；~~因为我懒！！！~~

然后我们就得到了 CFL 存在且唯一。由此有两个推论：

Theory 1.2.4 Lyndon Suffixes and Lyndon Prefixes

好玩且显然的 Fact。

反证法，因为如果 w_1 不是最长，那么还能再拼，产生了两个合法的 CFL，和 [Theory 1.2.3 Uniqueness of CFL] 矛盾。所以 w_1 是最长的 Lyndon 前缀。

w_k$ 同理。$\blacksquare

Theory 1.2.5 Theory of Minsuf

其实这是一道题，要求 O(n) 的时间复杂度完成。

一个字符串 s 的最小后缀是 w_k。

反证法，假设最小后缀是 {xw_{i+1}w_{i+2}\cdots w_{k}} 而不是 w_k 且 |x| < |w_i|。

我们有 {x w_{i + 1} \dots w_k} \geq x > w_i \ge w_k，矛盾。\blacksquare

1.3 Duval's Algorithm

时间复杂度 O(n)，空间复杂度 O(1) 的算法，不会可以去看你谷的【模板】Lyndon 分解。

2 Significant Suffixes

2.1 Definition

我们令 \operatorname{minsuf}(u) 为 u 的最小后缀，且 \operatorname{minsuf}(u, v) = \min _{w \in \operatorname{suf}(u)} wv。

Significant Suffixes：\Lambda(u) = \arg\min_{w\in \operatorname{suf}(u)} wv。

由 $\operatorname{minsuf}$ 的性质可知，$\operatorname{minsuf}(u, \epsilon) = \operatorname{minsuf}(u)$。$\implies \operatorname{minsuf}(u) \in \Lambda(u)$。所以，显然 $\forall u \in \Lambda(u),\ \operatorname{minsuf}(u) \sqsubseteq u$。我们注意到一个 CFL 分解中的 Lyndon Words 是存在一定的循环的。因此，我们可以记一个 CFL 为次方的形式。 $$ \operatorname{CFL}(u) = \overline {{w_1}^{k_1}{w_2}^{k_2}\cdots {w_n}^{k_n}} $$ 我们记 $s_i$ 为一个后缀，即 $s_i = \overline {{w_i}^{k_i}{w_{i+1}}^{k_{i+1}}\cdots{w_n}^{k_n}}$。边界：$s_{n+1} = \epsilon$。 ### 2.2 Significant Theory 首先，我们需要一个引理。 #### Theory 2.2.1 Infinite Theory 一个十分显然的结论，和显然今天下大雨一样显然。在 **[Theory 2.2.2 Significant Suffixes Theory]** 里面会用到，建议先食用下一个 Theory。 > 如果 $u^\infty < v$，则 $v > {uv} > {u^2v} > \cdots$。 $u^\infty < v \implies u^\infty < {uv}$。令 $u = {xay}$，$v = {(xay)^k xbh}$，其中 $x,y,h\in\Sigma^*$，$a,b\in\Sigma$，$a<b$。我们有 $v \succ uv \Longleftrightarrow (xay)^{k - 1} xbh \succ (xay)^k xbh \Longleftrightarrow xbh \succ (xay) xbh$。 $v>{uv} \implies {u^iv} > u^{i+1} \implies \blacksquare

同理如果 u^\infty > v，则 v < {uv} < {u^2v} < \cdots。

Theory 2.2.2 Significant Suffixes Theory

\Lambda(u)\subseteq \{s_i | i \in [1,n]\}

反证法：如果这个命题不成立，则我们分类讨论

i) 假设有一个串 v = \overline {b{w_i}^ks_{i+1}} \in \Lambda(u)，|b| < |w_i|,\ 0 \le k < k_i。

**ii)** 假设有一个串 $v = {{w_i}^ks_{i+1}} \in \Lambda(u)$，$1 < k < k_i$。根据 **[Theory 2.2.1 Infinite Theory]**，如果 ${w_i}^\infty < s_{i+1}$，则 ${{w_i}^{k_i}s_{i+1}} < {{w_i}^{k_i - 1}s_{i+1}}<\cdots<s_{i+1}$，否则 ${{w_i}^{k_i}s_{i+1}} > {{w_i}^{k_i-1}s_{i+1}} > \cdots > s_{i+1}$。我们令 $\lambda = \min \{i : s_{i+1} \sqsubset s_i\}$。$\forall i \ge \lambda, \ w_i = {s_{i+1}y_i},\ x_i = {y_is_{i+1}}$。$\implies s_i = {{w_i}^{k_i}s_{i+1}}= {(s_{i+1}y_i)^{k_i}s_{i+1}} = {s_{i+1}{x_i}^{k_i}}$。根据 CFL 的性质，$s_{\lambda} \triangleleft w_{\lambda - 1}$。所以 $\Lambda(u)\subseteq \{s_i | i \in [1,n]\}$。$\blacksquare

2.3 Other Theories

Theory 2.3.1 Lambda Subset Theory

如果有 2 个串 u 和 v，满足 |u| \le |v|，则我们有
\begin{aligned}\Lambda(uv) &\subseteq \Lambda(v) \cup \{\operatorname{maxsuf}^R(u, v)\} \\&= \Lambda(u) \cup{\max _{s \in \Lambda(u)}}^R \{sv\}\end{aligned}

理由很简单，因为 \{\operatorname{maxsuf}^R(u, v)\} 也是一个 Significant Suffix，随意我们就可以把它展成第二行的式子的形式。\blacksquare

Theory 2.3.2 Significant Suffixes Log Theory

一个字符串 S 的 Significant Suffixes 至多有 \log n 个。

原命题可以很容易地转化为：（感谢 yhx 的证明）

如果两个 Significant Suffixes u，v 满足 |u| < |v|，那么 2|u| < |v|。

反证法。设存在 |u| < |v| < 2|u|。因为 u, v \in \operatorname{suf}^+(u)，所以 u \in \operatorname{suf}^+(v)。

所以我们可以非常容易地知道，u \triangleleft v。\implies v 有一个长度为 |v| - |u| < \frac {|v|} 2 的周期，记为 T。

所以，u = {Tw}, v = {T^2w}。

由于 u 是一个 Significant Suffix，因此存在串 t，满足 vt>ut，即 {T^2wt} > {Twt} \implies {Twt} > {wt}。

而 w \in \operatorname{suf}^+(s)，所以与 u 是 Significant Suffix 矛盾。\blacksquare

2.4 Facts

我们知道 \Lambda(S) 中有很多串，其中最短的是 \operatorname{minsuf}(S)，而最长的是 \operatorname{maxsuf}^R(S)。这里的 ^R 代表 reverse。

\Lambda(u) = \{s_{\lambda}, \cdots, s_{n+1}\}
\operatorname{minsuf}(u) = s_n
\operatorname{maxsuf}^R(u) = s_\lambda
{x_\lambda}^\infty > \cdots > {x_m}^\infty
我们有一个串 v，{x_i}^\infty > v > {x_{i+1}}^\infty。则 {s_\lambda v} > \cdots > {s_{i+1}v} < \cdots < {s_kv}。
对于两个串 u 和 v，有 |u|<|v|，\Lambda({uv}) \subseteq \{\operatorname{maxsuf}^R(u, v)\} \cup \Lambda(v) = \{\min_{w \in \Lambda(u)}{wv}\} \cup \Lambda(v)。

这里的 Proof 先咕着吧。贴个 Reference：

Tomohiro, I., Nakashima, Y., Inenaga, S., Bannai, H., & Takeda, M. (2016). Faster Lyndon factorization algorithms for SLP and LZ78 compressed text. Theor. Comput. Sci., 656, 215-224.
Kociumaka, T. (2016). Minimal Suffix and Rotation of a Substring in Optimal Time. ArXiv, abs/1601.08051

进入正题。

我们先考虑不带修的情况。

由 [Theory 2.3.1 Lambda Subset Theory]，我们可以很容易地想到考虑建一棵线段树来维护 Significant Suffixes。

细节：如果线段树的 mid = l + r >> 1，则左边的区间比右边长一些。但是上面的这个结论对于 |u| \le |v| 有效，所以我们需要调整一下，使得左儿子比右儿子要长一些（即：mid = l + r + 1 >> 1，使得左儿子总不比右儿子短）

可以存一下当前代表的串的所有 Significant Suffixes，然后直接考虑合并（把右边的所有的直接加进来，左边的都循环一遍，字典序最长的加进去）得到父节点的 Significant Suffixes 即可。（看不懂的看代码）

由 [Theory 2.3.2 Lambda Log Theory] 可知，每一个集合都是 O(\log n) 大小的。这样的话，我们求出了每一个线段树上的区间的 Significant Suffixes。然后查询就在这 O(\log n) 个区间内求 Significant Suffixes 的并，暴力比较即可。所以我们需要一个 O(1) 比较两个串的方法（否则复杂度就挂了）。所以如果不带修的话我们可以考虑 SA。

接下来考虑带修的情况。

我们需要快速地求两个串的 LCP，又有一个线段树，所以可以很自然地想到一个线段树+字符串哈希+二分LCP的算法。复杂度 O(q \log^4 n)，慢了点，我这种人傻常数大的就不用想了。

我们考虑分块维护一些哈希，分 \sqrt n 的块。我们维护一下每个点到块的末端的哈希值，然后维护一下每个块到串的末尾的哈希值。然后我们可以记一个块的全局的偏移量，就可以算了。每次查询的时候，我们只需要查 2 次即可，O(1) 查找。最终是 O(q \log ^3 n + q\sqrt n) 的复杂度。

Q: 道理我都懂，但是为什么我挂了？ A: 你是用了自然溢出哈希吧，换个双哈希试试。

code

const int N = 200000;
const int B = 450;

const int base1 = 233;
const int base2 = 5e8;
const int mod = 1e9 + 9;

int n, q, c[N];
std::vector<int> tree[N << 2];

namespace Block {
int bs, bdelta[B], power[N + 1], psum[B + 1], intrah[B][B], interh[B];

inline int getc(int i) { return c[i] + bdelta[i / bs]; }

inline int geth(int i) {
  if (i == -1)
    return 0;
  const int bid = i / bs;
  i = i % bs;
  return ((ll)interh[bid] * power[i + 1] + intrah[bid][i] + (ll)bdelta[bid] * psum[i + 1]) % mod;
}

void init() { // 初始化分块和哈希
  bs = ceil(sqrt(1.0 * n));
  power[0] = 1, psum[0] = 0;
  for (int i = 1; i <= n; ++i)
    power[i] = (ll)power[i - 1] * base1 % mod;
  for (int i = 1; i <= bs; ++i)
    psum[i] = (psum[i - 1] + power[i - 1]) % mod;
  for (int bid = 0, s = 0; s < n; ++bid, s += bs) {
    interh[bid] = geth(s - 1);
    int h = 0;
    for (int r = 0; r < bs && s + r < n; ++r) {
      h = ((ull)h * base1 + (c[s + r] + base2)) % mod;
      intrah[bid][r] = h;
    }
  }
}

void hadd(int a, int b, int d) { // 对哈希修改
  for (int bid = 0, s = 0; s < n; ++bid, s += bs) {
    interh[bid] = geth(s - 1);
    if (a <= s && s + bs <= b)
      bdelta[bid] += d;
    else if (s < b && a < s + bs) {
      int h = 0;
      for (int r = 0; r < bs && s + r < n; ++r) {
        c[s + r] += bdelta[bid] + (a <= s + r && s + r < b ? d : 0);
        h = ((ull)h * base1 + (c[s + r] + base2)) % mod;
        intrah[bid][r] = h;
      }
      bdelta[bid] = 0;
    }
  }
}

template <bool flag = 1> bool cmp(int i, int j, int r) { // 比较两个串
  int hi = geth(i - 1), hj = geth(j - 1);
  int low = 0, high = r - j + 1;
  while (low < high) {
    int middle = low + high + 1 >> 1;
    if (((ull)(hi + mod - hj) * power[middle] + geth(j + middle - 1) + mod - geth(i + middle - 1)) % mod == 0)
      low = middle;
    else
      high = middle - 1;
  }
  return j + low - 1 == r ? flag : getc(i + low) < getc(j + low);
}
} // namespace Block

namespace Sgt {
inline void pushup(int k, int l, int r) { // 合并子节点信息
  auto &sigsuf = tree[k] = tree[k * 2 + 1]; // 右子节点直接加进来
  int best = -1;
  for (int i : tree[k * 2]) // 左子节点遍历一遍
    if (best == -1 || Block::cmp(i, best, r)) best = i; // 最“重要”的一个加进来
  sigsuf.push_back(best);
}

void build(int k, int l, int r) {
  if (l == r) return (void)(tree[k] = {l});
  int mid = (l + r + 1) / 2; // 左边比右边大
  build(k * 2, l, mid - 1);
  build(k * 2 + 1, mid, r);
  pushup(k, l, r);
}

void modify(int k, int l, int r, int a, int b) {
  if (b < l || r < a || (a <= l && r <= b)) return;
  int mid = (l + r + 1) / 2;
  if (a < mid) modify(k * 2, l, mid - 1, a, b);
  if (b >= mid) modify(k * 2 + 1, mid, r, a, b);
  pushup(k, l, r);
}

void query(int k, int l, int r, int a, int b, int &best) {
  if (b < l || r < a) return;
  if (a <= l && r <= b) {
    for (int v : tree[k])
      if (best == -1 || Block::cmp<0>(v, best, b))
        best = v;
    return;
  }
  int mid = (l + r + 1) / 2;
  if (b >= mid) query(k * 2 + 1, mid, r, a, b, best);
  if (a < mid) query(k * 2, l, mid - 1, a, b, best);
}
} // namespace Sgt

主程序随便写，注意我的下标是从 0 开始的。