「2025 杭电多校 2」1004. 子串的故事(2)
对于一个包含字符串 s_1, s_2, \dots, s_k 的字符串可重集 T,定义 T 的价值为
给出一个长度为 n 的字符串 S,下标从 1 到 n。有一个初始为空的字符串集合 T。
有 m 次操作,每次操作给出两个正整数 l, r (1 \leq l \leq r \leq n),你需要将字符串 S[l : r] 的所有前缀都加入集合 T。形式化地,对于所有 l \leq i \leq r,你需要将 S[l : i] 加入集合 T。
每次操作过后,你都需要求出此刻集合 T 的价值。答案对 10^9 + 7 取模。
数据范围:1 \leq n, m \leq 10^5。
时空限制:8s / 512MiB。
Solution
考虑一个最简单的想法:建出后缀 trie,则两个子串 s_1, s_2 的 \mathrm{LCP} 就转化为了 \mathrm{dep}[\mathrm{LCA}(p_1, p_2)]。可以套用 [LNOI2014] LCA 的 trick。但本题是要将一个字符串的所有前缀都加入,则相当于是链加等差数列,链乘等差数列求和。维护区间的 0/1/2 次项之和即可。
进一步优化,建出反串的 SAM。对于 SAM 上的每个节点,维护深度在 \mathrm{minl} \sim \mathrm{maxl} 的辅助数组 a 信息。但注意到,询问串在 SAM 上的状态可能不完全覆盖 \mathrm{minl} \sim \mathrm{maxl}(为该区间的一个前缀)。
记录一个 SAM 上离线拆节点的 trick:离线将所有询问子串在 SAM 上的状态找出来,然后将状态划分,建立有关询问串的虚拟节点(补充有关询问串的虚树结构)。此时所有询问串一定完整地覆盖从当前状态到根的路径,且总节点数不超过 2n + m。
还有一个粗暴的想法是:不新建节点,只不过对于不完全覆盖时多算或少算的贡献,还要进行打补丁。
设 n, m 同阶,时间复杂度 \mathcal{O}(n \log^2 n)。
#include <bits/stdc++.h>
using s64 = long long;
template <class T>
inline void chmin(T &x, const T &y) {
if (x > y) {
x = y;
}
}
template <class T>
inline void chmax(T &x, const T &y) {
if (x < y) {
x = y;
}
}
/* ----- ----- ----- 正文 ----- ----- ----- */
const int N = 100100, M = 100100;
const int NewN = N * 2 + M;
const int mod = 1e9 + 7;
int n, m;
std::string str;
struct Graph {
std::vector< std::vector<int> > table;
void init(int _n) {
table.assign(_n + 1, {});
}
void add_edge(int u, int v) {
table[u].push_back(v);
}
} G;
int ptr;
int minl[NewN], maxl[NewN];
namespace SAM {
const int SIZE = N * 2;
int NodeCount, Last;
struct node {
int trans[26];
int link, maxl;
} t[SIZE];
std::vector<int> son[SIZE];
int anc[18][SIZE];
int create() {
int p = ++ NodeCount;
for (int c = 0; c < 26; c ++) {
t[p].trans[c] = 0;
}
t[p].link = t[p].maxl = 0;
return p;
}
void init() {
NodeCount = 0, Last = create();
}
int location[N];
std::map<int, int> buc[SIZE];
void extend(int c, int i) {
int p = Last,
np = Last = create();
t[np].maxl = t[p].maxl + 1;
for (; p && t[p].trans[c] == 0; p = t[p].link) {
t[p].trans[c] = np;
}
if (!p) {
t[np].link = 1;
} else {
int q = t[p].trans[c];
if (t[q].maxl == t[p].maxl + 1) {
t[np].link = q;
} else {
int nq = ++ NodeCount; t[nq] = t[q];
t[nq].maxl = t[p].maxl + 1;
t[np].link = t[q].link = nq;
for (; p && t[p].trans[c] == q; p = t[p].link) {
t[p].trans[c] = nq;
}
}
}
location[i] = np;
}
void build_tree() {
for (int i = 1; i <= NodeCount; i ++) {
son[i].clear();
buc[i].clear();
}
for (int i = 2; i <= NodeCount; i ++) {
son[t[i].link].push_back(i);
}
for (int i = 1; i <= NodeCount; i ++) {
buc[i][t[i].maxl] = 1;
anc[0][i] = t[i].link;
}
for (int j = 1; j <= 17; j ++) {
for (int i = 1; i <= NodeCount; i ++) {
anc[j][i] = anc[j - 1][anc[j - 1][i]];
}
}
}
/* 子串定位 */
int find(int l, int r) {
int p = location[l];
for (int i = 17; i >= 0; i --) {
if (t[anc[i][p]].maxl >= r - l + 1) {
p = anc[i][p];
}
}
return p;
}
void dfs(int u, int fu) {
for (auto &[L, p] : buc[u]) {
p = ++ ptr;
minl[p] = maxl[fu] + 1, maxl[p] = L;
G.add_edge(fu, p);
fu = p;
}
for (int v : son[u]) {
dfs(v, fu);
}
}
void build_newtree() {
G.init(2 * n + m);
ptr = 0;
dfs(1, 0);
}
}
std::pair<int, int> range[M];
int match[M];
int dep[NewN], sze[NewN], Fa[NewN], son[NewN];
void dfs1(int u, int fu) {
dep[u] = dep[fu] + 1;
sze[u] = 1;
Fa[u] = fu;
son[u] = 0;
for (int v : G.table[u]) {
dfs1(v, u);
sze[u] += sze[v];
if (sze[v] > sze[son[u]]) {
son[u] = v;
}
}
}
int dfsClock, dfn[NewN], idx[NewN];
int Top[NewN];
void dfs2(int u, int P) {
dfsClock ++;
dfn[u] = dfsClock, idx[dfsClock] = u;
Top[u] = P;
if (son[u]) dfs2(son[u], P);
for (int v : G.table[u]) {
if (v == son[u]) continue;
dfs2(v, v);
}
}
int f1(int n) {
return (1ll * n * (n + 1) / 2) % mod;
}
int f1(int l, int r) {
return f1(r) - f1(l - 1);
}
int f2(int n) {
return (1ll * n * (n + 1) * (2 * n + 1) / 6) % mod;
}
int f2(int l, int r) {
return f2(r) - f2(l - 1);
}
int g(int n) {
return (1ll * n * (n + 1) * (n - 1) / 6) % mod;
}
namespace SGT {
struct node {
int l, r;
int s1, s2;
int addk, addb;
void mk_add(int k, int b) {
int L = minl[idx[l]], R = maxl[idx[r]];
s1 = (s1 + 1ll * k * f1(L, R) + 1ll * b * (R - L + 1)) % mod;
s2 = (s2 + 1ll * k * f2(L, R) + 1ll * b * f1(L, R)) % mod;
addk = (addk + k) % mod, addb = (addb + b) % mod;
}
} t[NewN * 4];
void upd(int p) {
t[p].s1 = (t[p * 2].s1 + t[p * 2 + 1].s1) % mod;
t[p].s2 = (t[p * 2].s2 + t[p * 2 + 1].s2) % mod;
}
void spread(int p) {
if (!t[p].addk && !t[p].addb) return;
t[p * 2].mk_add(t[p].addk, t[p].addb), t[p * 2 + 1].mk_add(t[p].addk, t[p].addb);
t[p].addk = t[p].addb = 0;
}
void build(int p, int l, int r) {
t[p].l = l, t[p].r = r, t[p].s1 = t[p].s2 = t[p].addk = t[p].addb = 0;
if (l == r) return;
int mid = (l + r) >> 1;
build(p * 2, l, mid), build(p * 2 + 1, mid + 1, r);
}
void addRange(int p, int s, int e, int k, int b) {
if (s <= t[p].l && t[p].r <= e) {
t[p].mk_add(k, b);
return;
}
spread(p);
int mid = (t[p].l + t[p].r) >> 1;
if (s <= mid) {
addRange(p * 2, s, e, k, b);
}
if (mid < e) {
addRange(p * 2 + 1, s, e, k, b);
}
upd(p);
}
int ask1(int p, int s, int e) {
if (s <= t[p].l && t[p].r <= e) {
return t[p].s1;
}
spread(p);
int mid = (t[p].l + t[p].r) >> 1;
if (s <= mid && mid < e) {
return (ask1(p * 2, s, e) + ask1(p * 2 + 1, s, e)) % mod;
}
if (s <= mid) {
return ask1(p * 2, s, e);
} else {
return ask1(p * 2 + 1, s, e);
}
}
int ask2(int p, int s, int e) {
if (s <= t[p].l && t[p].r <= e) {
return t[p].s2;
}
spread(p);
int mid = (t[p].l + t[p].r) >> 1;
if (s <= mid && mid < e) {
return (ask2(p * 2, s, e) + ask2(p * 2 + 1, s, e)) % mod;
}
if (s <= mid) {
return ask2(p * 2, s, e);
} else {
return ask2(p * 2 + 1, s, e);
}
}
}
int ans;
void solve(int p) {
int x, s1 = 0, s2 = 0;
x = p;
while (x) {
s1 = (s1 + SGT::ask1(1, dfn[Top[x]], dfn[x])) % mod;
s2 = (s2 + SGT::ask2(1, dfn[Top[x]], dfn[x])) % mod;
x = Fa[Top[x]];
}
ans = (ans + 1ll * (maxl[p] + 1) * s1) % mod;
ans = (ans - s2) % mod;
x = p;
while (x) {
SGT::addRange(1, dfn[Top[x]], dfn[x], -1, maxl[p] + 1);
x = Fa[Top[x]];
}
}
void work() {
std::cin >> n >> m;
std::cin >> str, str = " " + str;
SAM::init();
for (int i = n; i >= 1; i --) {
SAM::extend(str[i] - 'a', i);
}
SAM::build_tree();
for (int i = 1; i <= m; i ++) {
int l, r;
std::cin >> l >> r;
range[i] = {l, r};
int p = SAM::find(l, r);
SAM::buc[p][r - l + 1] = 1;
match[i] = p;
}
SAM::build_newtree();
dfsClock = 0;
dfs1(1, 0);
dfs2(1, 1);
SGT::build(1, 1, dfsClock);
ans = 0;
for (int i = 1; i <= m; i ++) {
auto [l, r] = range[i];
solve(SAM::buc[match[i]][r - l + 1]);
ans = (ans + g(r - l + 1)) % mod;
ans = (ans + mod) % mod;
std::cout << ans << '\n';
}
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int T;
std::cin >> T;
while (T --) {
work();
}
return 0;
}
/**
* 心中无女人
* 比赛自然神
* 模板第一页
* 忘掉心上人
**/在线版的代码就不放了 …