Solution
与“区间本质不同回文子串个数”类似，但没有等差数列那样优美的性质了……下面是一个更通用的做法。
考虑移动一次右端点 \(r\)，就相当于把 parent 树上一条到根链的 last endpos 设为 \(r\). 把这个看成 access 操作.
考虑用 LCT 维护 parent 树的链，维护一个性质：一条实链的 last endpos 都相同。可以发现这条实链代表的字符串长度连续.
而做修改时，进行的是如下修改：
对于串 \(T\)，区间 \([\text{last\_endpos}(T)-|T|+2..r-|T|+1]\) 加一.
可以发现，当 last endpos 相同时，修改可以合并.
于是考虑一条一条实链的实施修改，于是我们就可以在 access 时进行线段树修改，由于 access 均摊 \(O(\log n)\)，故进行 \(O(n\log n)\) 次线段树区间修改，\(O(n\log^2n+m\log n)\).
考虑线段树如何做修改：
- 一种方法是直接讨论，做区间加等差数列、单点查. 能做.
- 更好写的方法是观察差分数组，发现形如区间 +1、-1、查前缀和，可以树状数组 / 线段树实现.
优化原理是，endpos 不同不代表 last endpos 不同.
如何强制在线？持久化一下即可.
Code
Code 1
// 离线
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
#define link Link
typedef long long ll;
const int N = 1e6 + 10;
vector<pair<int, int>> Queries[N];
int n, m;
string s;
namespace SegmentTree {
ll add[N << 2], sum[N << 2];
int len[N << 2];
#define lc (u << 1)
#define rc ((u << 1) | 1)
#define mid ((l + r) >> 1)
void up(int u) {
sum[u] = sum[lc] + sum[rc];
}
void Add(int u, ll x) {
add[u] += x, sum[u] += 1ll * len[u] * x;
}
void down(int u) {
if (add[u]) Add(lc, add[u]), Add(rc, add[u]), add[u] = 0;
}
void Build(int u, int l, int r) {
add[u] = sum[u] = 0, len[u] = r - l + 1;
if (l == r) return;
Build(lc, l, mid), Build(rc, mid + 1, r);
}
void Upd(int u, int l, int r, int x, int y, ll v) {
if (y < l || r < x || x > y) return;
if (x <= l && r <= y) return Add(u, v);
down(u), Upd(lc, l, mid, x, y, v), Upd(rc, mid + 1, r, x, y, v), up(u);
}
ll Qry(int u, int l, int r, int x, int y) {
if (y < l || r < x || x > y) return 0ll;
if (x <= l && r <= y) return sum[u];
return down(u), Qry(lc, l, mid, x, y) + Qry(rc, mid + 1, r, x, y);
}
#undef lc
#undef rc
#undef mid
}
namespace SAM {
int sz, cur, last, len[N], link[N], nxt[N][26];
void init() {
link[0] = -1;
}
void extend(int ch) {
cur = ++sz, len[cur] = len[last] + 1;
int p = last;
for (; ~p; p = link[p])
if (!nxt[p][ch]) nxt[p][ch] = cur;
else break;
if (!~p) {
link[cur] = 0;
} else {
int q = nxt[p][ch];
if (len[p] + 1 == len[q]) {
link[cur] = q;
} else {
int copy = ++sz;
link[copy] = link[q], link[q] = copy, link[cur] = copy, len[copy] = len[p] + 1;
rep(i, 0, 25) nxt[copy][i] = nxt[q][i];
for (; ~p; p = link[p])
if (nxt[p][ch] == q) nxt[p][ch] = copy;
else break;
}
}
last = cur;
}
}
int NowEndpos;
namespace LinkCutTree {
int fa[N], mn[N], ch[N][2], cov[N], val[N];
#define get(u) (u == ch[fa[u]][1])
#define nrt(u) (u == ch[fa[u]][0] || u == ch[fa[u]][1])
void up(int u) {
if (u > 1) mn[u] = SAM::len[SAM::link[u - 1]] + 1;
else mn[u] = 0;
if (ch[u][0] > 1) mn[u] = min(mn[u], mn[ch[u][0]]);
}
void Cov(int u, int v) {
cov[u] = val[u] = v;
}
void down(int u) {
if (cov[u]) Cov(ch[u][0], cov[u]), Cov(ch[u][1], cov[u]), cov[u] = 0;
}
void Down(int u) {
if (nrt(u)) Down(fa[u]);
down(u);
}
void rot(int u) {
int f = fa[u], g = fa[f], k = get(u);
if (nrt(f)) ch[g][get(f)] = u;
ch[f][k] = ch[u][!k];
if (ch[u][!k]) fa[ch[u][!k]] = f;
ch[u][!k] = f, fa[f] = u, fa[u] = g, up(f), up(u);
}
void splay(int u) {
for (Down(u); nrt(u); rot(u)) if (nrt(fa[u])) rot(get(u) == get(fa[u]) ? fa[u] : u);
}
void access(int u) {
using namespace SAM;
int v = 0;
for (; u; v = u, u = fa[u]) {
splay(u);
if (u > 1) {
int LastEndpos = val[u], p = u - 1;
if (LastEndpos) {
SegmentTree::Upd(1, 1, n, LastEndpos + 2 - len[p], LastEndpos + 2 - mn[u], 1);
SegmentTree::Upd(1, 1, n, NowEndpos + 2 - len[p], NowEndpos + 2 - mn[u], -1);
} else {
SegmentTree::Upd(1, 1, n, 1, 1, len[p] - mn[u] + 1);
SegmentTree::Upd(1, 1, n, NowEndpos + 2 - len[p], NowEndpos + 2 - mn[u], -1);
}
}
ch[u][1] = v, up(u);
}
Cov(v, NowEndpos);
}
#undef get
#undef nrt
}
ll ans[N];
void Solve() {
using namespace SAM;
using namespace LinkCutTree;
init();
rep(i, 0, n - 1) extend(s[i] - 'a');
SegmentTree::Build(1, 1, n);
rep(i, 1, sz) fa[i + 1] = link[i] + 1, mn[i + 1] = len[link[i]] + 1;
int cur = 0;
rep(i, 1, n) {
NowEndpos = i;
cur = nxt[cur][s[i - 1] - 'a'];
access(cur + 1);
for (auto qry : Queries[i])
ans[qry.second] = SegmentTree::Qry(1, 1, n, 1, qry.first);
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
cin >> s >> m, n = s.length();
rep(_, 1, m) {
int l, r;
cin >> l >> r;
Queries[r].push_back(make_pair(l, _));
}
Solve();
rep(i, 1, m) cout << ans[i] << '\n';
return 0;
}
Code 2
支持强制在线，但是由于可持久化线段树空间太大被送走。
// 在线
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
#define link Link
typedef long long ll;
const int N = 1e5 + 10, M = 4e7 + 10, P = 2e5 + 10;
int n, m;
string s;
namespace SegmentTree {
struct Node {
int lc, rc, len;
ll add, sum;
} f[M];
int tot, rt[N];
#define mid ((l + r) >> 1)
void Build(int &u, int l, int r) {
f[u = ++tot] = (Node){0, 0, r - l + 1, 0ll, 0ll};
if (l == r) return;
Build(f[u].lc, l, mid), Build(f[u].rc, mid + 1, r);
}
void Upd(int &u, int l, int r, int x, int y, ll v) {
if (y < l || r < x || x > y) return;
f[++tot] = f[u], u = tot, f[u].sum += 1ll * (min(r, y) - max(l, x) + 1) * v;
if (x <= l && r <= y) return (void)(f[u].add += v);
Upd(f[u].lc, l, mid, x, y, v), Upd(f[u].rc, mid + 1, r, x, y, v);
}
ll Qry(int u, int l, int r, int x, int y, ll ad) {
if (y < l || r < x || x > y) return 0ll;
if (x <= l && r <= y) return f[u].sum + 1ll * f[u].len * ad;
return ad += f[u].add, Qry(f[u].lc, l, mid, x, y, ad) + Qry(f[u].rc, mid + 1, r, x, y, ad);
}
#undef mid
}
namespace SAM {
int sz, cur, last, len[P], link[P], nxt[P][26];
void init() {
link[0] = -1;
}
void extend(int ch) {
cur = ++sz, len[cur] = len[last] + 1;
int p = last;
for (; ~p; p = link[p])
if (!nxt[p][ch]) nxt[p][ch] = cur;
else break;
if (!~p) {
link[cur] = 0;
} else {
int q = nxt[p][ch];
if (len[p] + 1 == len[q]) {
link[cur] = q;
} else {
int copy = ++sz;
link[copy] = link[q], link[q] = copy, link[cur] = copy, len[copy] = len[p] + 1;
rep(i, 0, 25) nxt[copy][i] = nxt[q][i];
for (; ~p; p = link[p])
if (nxt[p][ch] == q) nxt[p][ch] = copy;
else break;
}
}
last = cur;
}
}
int NowEndpos, ver;
namespace LinkCutTree {
int fa[P], mn[P], ch[P][2], cov[P], val[P];
#define get(u) (u == ch[fa[u]][1])
#define nrt(u) (u == ch[fa[u]][0] || u == ch[fa[u]][1])
void up(int u) {
if (u > 1) mn[u] = SAM::len[SAM::link[u - 1]] + 1;
else mn[u] = 0;
if (ch[u][0] > 1) mn[u] = min(mn[u], mn[ch[u][0]]);
}
void Cov(int u, int v) {
cov[u] = val[u] = v;
}
void down(int u) {
if (cov[u]) Cov(ch[u][0], cov[u]), Cov(ch[u][1], cov[u]), cov[u] = 0;
}
void Down(int u) {
if (nrt(u)) Down(fa[u]);
down(u);
}
void rot(int u) {
int f = fa[u], g = fa[f], k = get(u);
if (nrt(f)) ch[g][get(f)] = u;
ch[f][k] = ch[u][!k];
if (ch[u][!k]) fa[ch[u][!k]] = f;
ch[u][!k] = f, fa[f] = u, fa[u] = g, up(f), up(u);
}
void splay(int u) {
for (Down(u); nrt(u); rot(u)) if (nrt(fa[u])) rot(get(u) == get(fa[u]) ? fa[u] : u);
}
void access(int u) {
using namespace SAM;
using namespace SegmentTree;
int v = 0;
for (; u; v = u, u = fa[u]) {
splay(u);
if (u > 1) {
int LastEndpos = val[u], p = u - 1;
if (LastEndpos) {
Upd(rt[ver], 1, n, LastEndpos + 2 - len[p], LastEndpos + 2 - mn[u], 1);
Upd(rt[ver], 1, n, NowEndpos + 2 - len[p], NowEndpos + 2 - mn[u], -1);
} else {
Upd(rt[ver], 1, n, 1, 1, len[p] - mn[u] + 1);
Upd(rt[ver], 1, n, NowEndpos + 2 - len[p], NowEndpos + 2 - mn[u], -1);
}
}
ch[u][1] = v, up(u);
}
Cov(v, NowEndpos);
}
#undef get
#undef nrt
}
void Solve() {
using namespace SAM;
using namespace LinkCutTree;
using namespace SegmentTree;
init();
rep(i, 0, n - 1) extend(s[i] - 'a');
Build(rt[0], 1, n);
rep(i, 1, sz) fa[i + 1] = link[i] + 1, mn[i + 1] = len[link[i]] + 1;
int cur = 0;
rep(i, 1, n) {
NowEndpos = i, ++ver, rt[ver] = rt[ver - 1];
cur = nxt[cur][s[i - 1] - 'a'];
access(cur + 1);
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
cin >> s >> m, n = s.length(), Solve();
while (m--) {
using namespace SegmentTree;
int l, r;
cin >> l >> r;
cout << Qry(rt[r], 1, n, 1, l, 0ll) << '\n';
}
return 0;
}