前言
题目链接：HDU。
题意简述
定义字符串可重集 \(T=\{s_i\}_{i=1}^k\) 的价值为 \(\sum\limits_{1\leq i\lt j\leq k}\operatorname{LCP}(s_i,s_j)\)。
给你长度为 \(n\) 的字符串 \(S\)，和初始为空的字符串可重集 \(T\)。
\(m\) 次操作，给定 \(l,r\)，你需要将 \(S[l,r]\) 的所有非空前缀插入 \(T\)。并在操作后求出 \(T\) 的价值，对 \(10^9+7\) 取模。
\(n,m\leq10^5\)，\(\Sigma\) 为小写字母。
题目分析
考虑把 \(\operatorname{LCP}(s_i,s_j)\) 转化掉。
在最原始的时候，我们还只会哈希倍增在 \(\mathcal{O}(\log n)\) 的时间求出两个字符串的 LCP，这个扩展性显然不高。
再后来，我们学了 SA，学会了求 height，然后可以 \(\mathcal{O}(n\log n)\sim \mathcal{O}(1)\) 地求字符串两个子串的 LCP。令 \(rk_{l_1}\leq rk_{l_2}\)，那么 \(\operatorname{LCP}(S[l_1,r_1],S[l_2,r_2])=\min\Bigg\{r_1-l_1+1,r_2-l_2+1,\min\limits_{i=rk_{l_1}+1}^{rk_{l_2}}\mathrm{height}_i\Bigg\}\)。考虑建出 height 的笛卡尔树，那么 \(\min\limits_{i=rk_{l_1}+1}^{rk_{l_2}}\mathrm{height}_i=\mathrm{height}_{\operatorname{LCA}(rk_{l_1}+1,rk_{l_2})}\)。如果每次加入的仅是一个子串，而非一个子串的所有前缀，并且没有 \(r_1-l_1+1,r_2-l_2+1\)，这个树上问题很简单了，可以参考link，于是我们只需要到根的链加链求和。如果需要考虑子串长度怎么办？由于笛卡尔树 \(\mathrm{height}\) 往根走是单调递减的，所以考虑在修改的时候，二分出一个祖先，使得上方节点的 \(\mathrm{height}\) 小于 \(r_1-l_1+1\)，那么下方贡献为 \(r_1-l_1+1\)，上方正常做即可。称这个祖先为断点。下方的贡献可以仅放在那个祖先上，这样总是会被统计到。此时还剩下 \(r_2-l_2+1\) 的限制，同样考虑二分找断点，上方直接查询即可，下方我们还要考虑 \(r_1-l_1+1\) 和 \(r_2-l_2+1\) 的大小关系。笛卡尔树子树相当于序列区间，区间数一数，树套树即可。那如果每次加入的是一个子串的所有前缀怎么办？先考虑插入操作。显然不能 \(\mathcal{O}(n)\) 枚举前缀。记 \(len=r_1-l_1+1\)，每次要操作的都形如 \(1\sim len\) 的前缀，是不是可以预处理？显然可以。考虑查询，断点上面的节点好处理，主要考虑怎么处理 \(\mathcal{O}(n)\) 个处在断点下方的区间。但是作者太菜了，想了一中午想不明白，就放弃了。
再再后来，我们学了 SAM，学会了反串建立 SAM，使得 endpos 实为 beginpos。于是对于求两个字符串后缀的 LCP，直接在 parent 树上找到 LCA 即可。但是还是遇到了子串这个问题，我们发现，此时对应 LCA 的一部分，而不是整个结点，于是想到可以拆点。剩下的问题也是一个类似的树上问题。操作都可以用树剖写。时间复杂度 \(\mathcal{O}(n\log n)\) 或 \(\mathcal{O}(n\log^2n)\)。
代码
代码比较好些，各部分功能基本解耦了。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
#include <vector>
using namespace std;using ull = unsigned long long;const int N = 1e5 + 10;
const int M = 26;
const int mod = 1e9 + 7;inline int add(int a, int b) { return a += b, a >= mod ? a - mod : a; }
inline int sub(int a, int b) { return a -= b, a < 0 ? a + mod : a; }
inline int mul(int a, int b) { return (ull)a * b % mod; }
inline int f(int k) { return (((ull)(1 + k) * k) >> 1) % mod; }
inline int g(int n) { return ((ull)n * (n + 1) >> 1) * (n - 1) / 3 % mod; }
inline int h(int n) { return ((ull)n * (n + 1) >> 1) * (2 * n + 1) / 3 % mod; }namespace seg {const int _N = (N * 2 + N) << 2;#define ls (u << 1)
#define rs (u << 1 | 1)struct {int f0, f1, f2;int s1, s2;int t1, t2;
} t[_N];int _rn;void _build(int u, int l, int r, int dfn[], int L[], int R[]) {t[u] = { 0, 0, 0, 0, 0, 0, 0 };if (l == r) {int a = L[dfn[l]] - 1, b = R[dfn[l]];t[u].f0 = b - a;t[u].f1 = sub(f(b), f(a));t[u].f2 = sub(h(b), h(a));return;}int mid = (l + r) >> 1;_build(ls, l, mid, dfn, L, R);_build(rs, mid + 1, r, dfn, L, R);t[u].f0 = add(t[ls].f0, t[rs].f0);t[u].f1 = add(t[ls].f1, t[rs].f1);t[u].f2 = add(t[ls].f2, t[rs].f2);
}inline void ptag(int u, int t1, int t2) {t[u].s1 = add(t[u].s1, add(mul(t1, t[u].f1), mul(t2, t[u].f0)));t[u].s2 = add(t[u].s2, add(mul(t1, t[u].f2), mul(t2, t[u].f1)));t[u].t1 = add(t[u].t1, t1);t[u].t2 = add(t[u].t2, t2);
}inline void pdown(int u) {if (!t[u].t1 && !t[u].t2) return;ptag(ls, t[u].t1, t[u].t2);ptag(rs, t[u].t1, t[u].t2);t[u].t1 = t[u].t2 = 0;
}void _modify(int u, int trl, int trr, int l, int r, int v1, int v2) {if (l <= trl && trr <= r) return ptag(u, v1, v2);pdown(u);int mid = (trl + trr) >> 1;if (l <= mid) _modify(ls, trl, mid, l, r, v1, v2);if (r > mid) _modify(rs, mid + 1, trr, l, r, v1, v2);t[u].s1 = add(t[ls].s1, t[rs].s1);t[u].s2 = add(t[ls].s2, t[rs].s2);
}pair<int, int> _query(int u, int trl, int trr, int l, int r) {if (l <= trl && trr <= r) return { t[u].s1, t[u].s2 };pdown(u);int mid = (trl + trr) >> 1;if (r <= mid) return _query(ls, trl, mid, l, r);if (l > mid) return _query(rs, mid + 1, trr, l, r);pair<int, int> a = _query(ls, trl, mid, l, r),b = _query(rs, mid + 1, trr, l, r);return { add(a.first, b.first), add(a.second, b.second) };
}void build(int n, int dfn[], int L[], int R[]) {_rn = n;_build(1, 1, n, dfn, L, R);
}void modify(int l, int r, int v1, int v2) {_modify(1, 1, _rn, l, r, v1, v2);
}pair<int, int> query(int l, int r) {return _query(1, 1, _rn, l, r);
}#undef ls
#undef rs}namespace tree {const int _N = N * 2 + N;struct {int v, nxt;
} e[_N];
int head[_N], eid;
int L[_N], R[_N];inline void add(int u, int v) {e[++eid] = { v, head[u] };head[u] = eid;
}void clear(int n) {memset(head + 1, 0x00, sizeof(int[n]));eid = 1;
}int dfn[_N], idx[_N], tim;
int fa[_N], dpt[_N];
int siz[_N], son[_N], top[_N];
void dfs(int u) {siz[u] = 1, son[u] = 0;for (int i = head[u]; i; i = e[i].nxt) {int v = e[i].v;fa[v] = u;dpt[v] = dpt[u] + 1;dfs(v);siz[u] += siz[v];if (siz[v] > siz[son[u]]) {son[u] = v;}}
}
void redfs(int u, int tp) {dfn[idx[u] = ++tim] = u;top[u] = tp;if (son[u]) redfs(son[u], tp);for (int i = head[u]; i; i = e[i].nxt) {int v = e[i].v;if (v == son[u]) continue;redfs(v, v);}
}int ans;void build() {tim = 0;dfs(1);redfs(1, 1);seg::build(tim, dfn, L, R);ans = 0;
}void upd(int u, int l, int r) {int lu = R[u];ans = ::add(ans, g(r - l + 1));int s1 = 0, s2 = 0;for (; u; u = fa[top[u]]) {auto r = seg::query(idx[top[u]], idx[u]);s1 = ::add(s1, r.first);s2 = ::add(s2, r.second);seg::modify(idx[top[u]], idx[u], mod - 1, lu + 1);}ans = ::add(ans, sub(mul(lu + 1, s1), s2));
}}namespace sam {const int _N = N << 1;
const int lg_N = __lg(_N) + 1;int tr[_N][M], len[_N], fa[_N];
int pos[N];
int tot, tail;map<int, int> mp[_N];
vector<int> e[_N];inline int G() {int u = ++tot;memset(tr[u], 0x00, sizeof(*tr));len[u] = fa[u] = 0;mp[u].clear();e[u].clear();return u;
}void init() {tot = 0, tail = G();
}void append(int x, int i) {int w = G(), p = tail;len[w] = len[p] + 1;pos[i] = w;for (; p && !tr[p][x]; p = fa[p]) tr[p][x] = w;if (!p) {fa[w] = 1;} else {int q = tr[p][x];if (len[q] == len[p] + 1) {fa[w] = q;} else {int o = G();memcpy(tr[o], tr[q], sizeof(*tr));fa[o] = fa[q], len[o] = len[p] + 1;for (; p && tr[p][x] == q; p = fa[p]) tr[p][x] = o;fa[w] = fa[q] = o;}}tail = w;
}int _fa[lg_N][_N];
void build() {for (int i = 1; i <= tot; ++i) {_fa[0][i] = fa[i];mp[i][len[i]] = 0;e[i].clear();}for (int i = 2; i <= tot; ++i) {e[fa[i]].emplace_back(i);}for (int k = 1; k < lg_N; ++k)for (int i = 1; i <= tot; ++i) {_fa[k][i] = _fa[k - 1][_fa[k - 1][i]];}
}
inline int find(int l, int r) {int p = pos[l];for (int k = lg_N - 1; ~k; --k)if (_fa[k][p] && len[_fa[k][p]] >= r - l + 1) {p = _fa[k][p];}return p;
}int _id;
inline void insQ(int p, int len) {mp[p][len] = 114514;
}
void dfs(int u, int ls) {for (auto &[k, v] : mp[u]) {v = ++_id;tree::L[v] = tree::R[ls] + 1;tree::R[v] = k;tree::add(ls, v);ls = v;}for (int v : e[u]) {dfs(v, ls);}
}
void rebuild() {_id = 0;dfs(1, 0);
}}int n, m;
string s;struct {int l, r, p;
} q[N];void rebuild() {tree::clear(sam::tot + m);sam::rebuild();tree::build();
}void solve() {cin >> n >> m >> s, s = " " + s;sam::init();for (int i = n; i; --i) {sam::append(s[i] - 'a', i);}sam::build();for (int i = 1, l, r; i <= m; ++i) {cin >> l >> r;q[i].l = l, q[i].r = r;q[i].p = sam::find(l, r);sam::insQ(q[i].p, r - l + 1);}rebuild();for (int i = 1; i <= m; ++i) {int l = q[i].l, r = q[i].r;int p = sam::mp[q[i].p][r - l + 1];tree::upd(p, l, r);cout << tree::ans << '\n';}
}int main() {ios::sync_with_stdio(false); // because of HDUcin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}