自动搬运

查看原文

来自洛谷，原作者为

	zghtyarecrenj 心亦天天的了 夢天天的了 雖也未能料

搬运于2025-08-24 22:08:17，当前版本为作者最后更新于2020-04-13 07:48:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

ZJOI2017 字符串

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

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

0 Marks & Facts

1. 我们定义两个字符串 $a$ 和 $b$，如果 $a$ 的字典序 $<b$，则我们称 $a < b$。
2. 如果 $a$ 是 $b$ 的前缀且 $a \ne b$，则我们称 $a \sqsubset b$。
3. 如果 $a$ 是 $b$ 的前缀，则我们称 $a \sqsubseteq b$。
4. 如果 $a < b$ 且 $a$ 不是 $b$ 的前缀，则我们称 $a \triangleleft b$。即 $a \triangleleft b \Longleftrightarrow (a < b) \wedge (a \not\sqsubseteq b)$。
5. ${abc}$ 表示拼接 $a, b, c$ 三个字符串。
6. $a^n$ 表示 $n$ 个 $a$ 拼接在一起。e.g. ${a^2b} = {aab}$
7. $\epsilon$ 表示空串。
8. 我们定义字符集为 $\Sigma$，组成的字符串为 $\Sigma^*$，$\Sigma^+ = \Sigma^* \setminus \{\epsilon\}$
9. $\operatorname{pref}(a)$ 表示所有 $a$ 的前缀的集合，$\operatorname{suf}(a)$ 表示所有 $a$ 的后缀的集合（包含 $a$ 和 $\epsilon$）
10. $\operatorname{pref}^+(a) = \operatorname{pref}(a) \setminus \{a,\epsilon\},\ \operatorname{suf}^+(a) = \operatorname{suf}^+(a) \setminus \{a, \epsilon\}$

一些非常显然的 Fact:

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

1 Lyndon Words

1.1 Definition

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

$\mathcal L$ 表示 Lyndon Word 的集合。

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$ 是最长的 Lyndon 前缀且 $w_k$ 是最长的 Lyndon 后缀。

反证法，因为如果 $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}(s)$ 表示 S 字典序最小的后缀，且

由 $\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$。

$w_i \in \mathcal L \implies w_i \triangleleft b \implies s_i = {w_is_{i+1}} < {bs_{i+1}}$，矛盾。

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 {{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：

1. 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.
2. 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 开始的。