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)\)。
- \({abc}\) 表示拼接 \(a, b, c\) 三个字符串。
- \(a^n\) 表示 \(n\) 个 \(a\) 拼接在一起。e.g. \({a^2b} = {aab}\)
- \(\epsilon\) 表示空串。
- 我们定义字符集为 \(\Sigma\)，组成的字符串为 \(\Sigma^*\)，\(\Sigma^+ = \Sigma^* \setminus \{\epsilon\}\)
- \(\operatorname{pref}(a)\) 表示所有 \(a\) 的前缀的集合，\(\operatorname{suf}(a)\) 表示所有 \(a\) 的后缀的集合（包含 \(a\) 和 \(\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\)。
\(\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<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 开始的。