区间本质不同子串数 题解
题目大意
给定一个长度为 \(n\) 的小写字母字符串 \(S\)，以及 \(m\) 次询问，每次询问区间 \([l, r]\) 中本质不同的非空子串个数。
数据范围 \(n \le 10^5, m \le 2\times 10^5\)。
解题思路
1. 扫描线
对于一个固定的 \(r\)，假设我们已经知道所有本质不同子串的「最后出现位置」，那么对于询问 \((l, r)\)，答案就是所有最后出现位置落在 \([l, r]\) 内的本质不同子串个数。因为若一个子串的最后一次出现在 \(r\) 之前，它就不会再被当前区间包含；若最后出现位置 \(p \ge l\)，则该子串必然出现在 \(S[l..r]\) 中。
因此，如果我们在扫描线向右移动 \(r\) 时，能够动态维护一个数组 ans[l] 表示以 \(l\) 为左端点、以当前 \(r\) 为右端点的区间内本质不同子串数，那么询问 \((l, r)\) 的答案就是扫描到该 \(r\) 时 ans[l] 的值。
2. 后缀自动机
SAM 的每一个状态 \(v\) 代表了一组 endpos 相同的子串，它们的长度在 \([\text{minlen}(v), \text{maxlen}(v)]\) 之间，且 minlen(v) = len(link(v)) + 1。对于该状态，我们关心它当前最后出现位置 last(v)。显然，当我们在 \(S\) 末尾加入字符，新状态以及其在 parent 树上的所有祖先的 last 都会变成当前的 \(r\)。
对于状态 \(v\)，它包含的每个子串长度 \(len\) 都对应一个唯一子串，其起始位置为 \(last(v) - len + 1\)。给定左端点 \(l\)，该状态对 ans[l] 的贡献就是满足以下条件的长度个数：
- \(\text{minlen}(v) \le len \le \text{maxlen}(v)\)
- \(last(v) - len + 1 \ge l \quad \Rightarrow \quad len \le last(v) - l + 1\)
这等价于求 len 的范围：\([\text{minlen}(v), \ \min(\text{maxlen}(v), \ last(v) - l + 1)]\)。
分类讨论可得贡献函数 \(f_v(l)\)：
- 若 \(l \le L = last - maxlen + 1\)，则所有
C = maxlen - minlen + 1种长度都满足，贡献为常数 \(C\)。 - 若 \(L < l \le R = last - minlen + 1\)，则满足的长度有 \(R - l + 1\) 个，线性递减。
- 若 \(l > R\)，贡献为 0。
这样，每个状态在 last 固定的情况下，会对答案数组产生一个分段贡献：前面常数值，中间一次函数，后面为零。
3. 树状数组维护一次函数
既然我们要在扫描线过程中不断将某些状态的 last 从旧值改为新值（当前 \(r\)），就需要一种方法能快速撤销旧贡献、添加新贡献。
对于区间加「一次函数 \(a\cdot x + b\)」的操作，我们可以用两个树状数组（BIT）维护差分：
BITa维护一次项系数 \(a\) 的差分BITb维护常数项 \(b\) 的差分
区间 \([L, R]\) 加 \(a\cdot x + b\) 只需在 BIT 上做4次更新，单点查询直接计算即可。
于是，对一个状态段的贡献可以用 apply_state(last, minlen, maxlen, sign) 函数实现，sign=+1 加贡献，sign=-1 减贡献：
- 在 \([1, L-1]\) 加常数 \(C\)（即加 \(0\cdot x + C\)）
- 在 \([L, R]\) 加函数 \(-x + (R+1)\)（即 \(a=-1, b=R+1\)）
注意，上述过程只处理非空子串，状态1（代表空串）的 minlen=0, maxlen=0 会被跳过。
4. 树链剖分
现在问题变成：每次加入一个字符后，当前前缀对应的状态 cur 到根节点路径上的所有状态的 last 都要更新为当前 \(r\)。如果暴力跳 parent 树，总复杂度 \(O(n^2)\)，不可接受。
观察 parent 树的结构，我们希望对路径上的一段连续区间进行整体赋值。利用重链剖分将树剖分成若干条链，每条链上的 dfn 序连续，并且长度范围 [minlen, maxlen] 是单调的（实际上一条重链从浅到深 maxlen 严格递增，且 minlen 与父节点 maxlen+1 衔接）。因此，我们可以把一条重链上的一段连续节点看作一个整体，它们覆盖的子串长度区间拼接成 [总minlen, 总maxlen]。
用线段树维护 dfn 序上的区间，每个节点存储：
minlen和maxlen：该区间内状态合并后的长度范围lazy_last：区间整体的last值（初始为0，-1表示不统一）
区间赋值 update(ql, qr, new_last) 时，若当前节点区间被完全覆盖且标记统一（lazy_last != -1），则直接调用 apply_state 减去旧贡献、加上新贡献，并更新标记；否则下推标记递归处理，最后尝试将子区间标记合并。
路径更新函数 path_set_last(x, r) 只需从节点 x 出发，每次取 top[x]，在线段树上对区间 [dfn[top[x]], dfn[x]] 赋值 r，然后跳到 link[top[x]] 继续。
这样每次更新均摊 \(O(\log^2 n)\)，整个过程总复杂度 \(O(n \log^2 n)\)。
6. 复杂度
- 时间：\(O((n+m)\log^2 n)\)，可以平稳通过。
- 空间：\(O(n)\) 级别的若干数组。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10, K = N * 2, Q = 2e5 + 10;
string s; int n, q; ll ans[Q]; int pos[N];
vector <pair <int, int>> qL[N]; vector <int> e[K];
namespace Sam {int ch[K][26], len[K], fa[K], tot = 1, last = 1;void insert(int c) {int u = last, v = ++tot; len[v] = len[last] + 1;for (; u && !ch[u][c]; u = fa[u]) ch[u][c] = v;if (!u) return fa[v] = 1, last = v, void();int p = ch[u][c];if (len[p] == len[u] + 1) return fa[v] = p, last = v, void();int np = ++tot; len[np] = len[u] + 1;for (int i = 0; i < 26; i++) ch[np][i] = ch[p][i]; fa[np] = fa[p], fa[p] = fa[v] = np;for (; ch[u][c] == p; u = fa[u]) ch[u][c] = np;last = v;}
}
struct BIT {ll t[N];int lowbit(int x) {return x & -x;}void upd(int x, ll v) {for (int i = x; i <= n; i += lowbit(i)) t[i] += v;}ll gets(int x) {ll s = 0; for (int i = x; i >= 1; i -= lowbit(i)) s += t[i]; return s;}
};
namespace Func {BIT ta, tb;void upd(int l, int r, ll a, ll b) {ta.upd(l, a); ta.upd(r + 1, -a); tb.upd(l, b); tb.upd(r + 1, -b);}ll query(int x) {ll a = ta.gets(x), b = tb.gets(x); return a * x + b; }void addseg(int last, int minlen, int maxlen, int sign) {if (last == 0 || minlen > maxlen) return;int C = maxlen - minlen + 1, L = last - maxlen + 1, R = last - minlen + 1; L = max(L, 1);if (L <= R) {if (L > 1) upd(1, L - 1, 0, (ll)C * sign);upd(L, R, -sign, (ll)sign * (R + 1));}}
}
namespace HLD {int fath[K], dep[K], siz[K], son[K], dfn[K], tot = 0, top[K], rdfn[K];struct Sgt {int last[K << 2], minlen[K << 2], maxlen[K << 2];#define mid (l + r >> 1)#define ls p << 1#define rs p << 1 | 1void build(int p, int l, int r) {last[p] = 0; if (l == r) {int u = rdfn[l]; minlen[p] = (u == 1 ? 0 : Sam::len[Sam::fa[u]] + 1); maxlen[p] = Sam::len[u]; return;}build(ls, l, mid); build(rs, mid + 1, r); minlen[p] = minlen[ls], maxlen[p] = maxlen[rs];}void pushdown(int p) {if (last[p] == -1) return; last[ls] = last[p], last[rs] = last[p], last[p] = -1;}void upd(int p, int l, int r, int ql, int qr, int val) {if (ql <= l && r <= qr && last[p] != -1) return Func::addseg(last[p], minlen[p], maxlen[p], -1), last[p] = val, Func::addseg(last[p], minlen[p], maxlen[p], 1), void();if (r < ql || qr < l) return; pushdown(p); upd(ls, l, mid, ql, qr, val), upd(rs, mid + 1, r, ql, qr, val);if (last[ls] == last[rs] && last[ls] != -1) last[p] = last[ls]; else last[p] = -1;}} seg;void dfs_pre(int u, int fa) {fath[u] = fa, dep[u] = dep[fa] + 1, siz[u] = 1; for (auto v : e[u]) {dfs_pre(v, u); siz[u] += siz[v]; if (siz[v] > siz[son[u]]) son[u] = v;}}void dfs(int u, int head) {top[u] = head, dfn[u] = ++tot, rdfn[tot] = u; if (son[u]) dfs(son[u], head);for (auto v : e[u]) if (v != son[u]) dfs(v, v);}void change(int u, int val) { while (u != 0) { int tp = top[u]; seg.upd(1, 1, tot, dfn[tp], dfn[u], val); u = fath[tp]; } }
}
int main() {cin.tie(0) -> ios::sync_with_stdio(0);cin >> s; n = s.size(); s = ' ' + s; cin >> q;for (int l, r, i = 1; i <= q; i++) cin >> l >> r, qL[r].emplace_back(l, i);for (int i = 1; i <= n; i++) Sam::insert(s[i] - 'a'), pos[i] = Sam::last;for (int i = 1; i <= Sam::tot; i++) e[Sam::fa[i]].emplace_back(i);HLD::dfs_pre(1, 0); HLD::dfs(1, 1); HLD::seg.build(1, 1, HLD::tot);for (int r = 1; r <= n; r++) {HLD::change(pos[r], r);for (auto [l, id] : qL[r]) ans[id] = Func::query(l);}for (int i = 1; i <= q; i++) cout << ans[i] - 1 << '\n';return 0;
}