Statement
维护一棵树,边权 \(\in\{\texttt a,\texttt b,\texttt c\}\),根为 \(1\),定义这棵树的子串为从 \(1\) 走到所有点构成的字符串的所有后缀,需要支持以下操作:
- 问当前树的本质不同子串数
- 给一个点添加一棵子树
- 问一个串在当前树中作为子串的出现次数
Solution
直接广义 SAM + LCT
考虑如何减小常数。
离线,先把最后的 trie 对应的广义 SAM、parent 树建出来
操作 2 相当于把一些点由未出现变成出现,单点加
操作 1 相当于求出现过的点的 \(\sum \text{len}(u)-\text{len}(\text{link}(u))\)
操作 3 相当于求子树和
于是直接树状数组,单点加、区间和,再维护一下 \(\sum\text{len}(u)-\text{len}(\text{link}(u))\) 即可
Code 1
广义 SAM + LCT
#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)
typedef long long ll;
const int N = 4e5 + 10;
namespace LCT {
int fa[N], ch[N][2], All[N], MyXu[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) {
All[u] = All[ch[u][0]] + All[ch[u][1]] + MyXu[u] + val[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 (; nrt(u); rot(u)) if (nrt(fa[u])) rot(get(u) == get(fa[u]) ? fa[u] : u);
}
void access(int u) {
for (int v = 0; u; v = u, u = fa[u])
splay(u), MyXu[u] = MyXu[u] - All[v] + All[ch[u][1]], ch[u][1] = v, up(u);
}
void Add(int u, int v) {
access(u), splay(u), All[u] += v, val[u] += v;
}
void link(int u, int v) {
access(v), splay(v), fa[u] = v, MyXu[v] += All[u];
}
void cut(int u, int v) {
access(u), splay(v), All[v] -= All[u], ch[v][1] = fa[u] = 0;
}
int qry(int u) {
return access(u), splay(u), MyXu[u] + val[u];
}
#undef get
#undef nrt
}
namespace SAM {
int sz, cur, len[N], link[N], nxt[N][3];
ll sum;
void init() {
link[0] = -1;
}
int extend(int ch, int last) {
if (nxt[last][ch]) {
if (len[last] + 1 == len[nxt[last][ch]]) return LCT::Add(nxt[last][ch] + 1, 1), nxt[last][ch];
else {
int p = last, q = nxt[last][ch], copy = ++sz;
LCT::cut(q + 1, link[q] + 1), LCT::link(copy + 1, link[q] + 1), LCT::link(q + 1, copy + 1);
link[copy] = link[q], link[q] = copy, len[copy] = len[p] + 1;
rep(i, 0, 2) nxt[copy][i] = nxt[q][i];
for (; ~p; p = link[p])
if (nxt[p][ch] == q) nxt[p][ch] = copy;
else break;
LCT::Add(copy + 1, 1);
return copy;
}
}
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, LCT::link(cur + 1, 1);
} else {
int q = nxt[p][ch];
if (len[p] + 1 == len[q]) {
link[cur] = q, LCT::link(cur + 1, q + 1);
} else {
int copy = ++sz;
LCT::cut(q + 1, link[q] + 1);
LCT::link(copy + 1, link[q] + 1);
LCT::link(q + 1, copy + 1);
LCT::link(cur + 1, copy + 1);
link[copy] = link[q], link[q] = copy, link[cur] = copy, len[copy] = len[p] + 1;
rep(i, 0, 2) nxt[copy][i] = nxt[q][i];
for (; ~p; p = link[p])
if (nxt[p][ch] == q) nxt[p][ch] = copy;
else break;
}
}
sum += len[cur] - len[link[cur]];
LCT::Add(cur + 1, 1);
return cur;
}
}
struct Edge {
int t, n, w;
} E[N << 1];
int tot, h[N];
void Add(int u, int v, int w) {
E[++tot] = (Edge){v, h[u], w}, h[u] = tot;
}
int pos[N], vis[N];
void BFS(int rt) {
queue<int> q;
q.push(rt);
while (!q.empty()) {
int u = q.front();
q.pop();
vis[u] = 1;
int p = pos[u];
for (int i = h[u]; i; i = E[i].n) {
int v = E[i].t, w = E[i].w;
if (!vis[v]) {
pos[v] = SAM::extend(w, p), q.push(v);
}
}
}
}
int n0, m;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int id;
cin >> id >> n0;
SAM::init();
rep(i, 1, n0 - 1) {
int u, v;
char c;
cin >> u >> v >> c, Add(u, v, c - 'a'), Add(v, u, c - 'a');
}
BFS(1);
cin >> m;
while (m--) {
int opt;
cin >> opt;
if (opt == 1) {
cout << SAM::sum << '\n';
}
if (opt == 2) {
int rt, s;
cin >> rt >> s;
rep(i, 1, s - 1) {
int u, v;
char c;
cin >> u >> v >> c, Add(u, v, c - 'a'), Add(v, u, c - 'a');
}
BFS(rt);
}
if (opt == 3) {
string s;
cin >> s;
int len = s.length(), p = 0, ok = 1;
rep(i, 0, len - 1) {
int now = s[i] - 'a';
if (SAM::nxt[p][now]) {
p = SAM::nxt[p][now];
} else {
ok = 0;
break;
}
}
if (ok) {
cout << LCT::qry(p + 1) << '\n';
} else {
cout << "0\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)
typedef long long ll;
const int N = 4e5 + 10;
struct Edge {
int t, n, w;
} e[N << 1];
int tot, h[N];
void Add(int u, int v, int w) {
e[++tot] = (Edge){v, h[u], w}, h[u] = tot;
}
int n0, m;
struct Oper {
int opt, rt, s;
string S;
} Ops[N];
int sz, cur, len[N], link[N], nxt[N][3];
void init() {
link[0] = -1;
}
int extend(int ch, int last) {
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, 2) nxt[copy][i] = nxt[q][i];
for (; ~p; p = link[p])
if (nxt[p][ch] == q) nxt[p][ch] = copy;
else break;
}
}
return cur;
}
int pos[N];
void BFS(int be) {
queue<int> q;
q.push(be);
while (!q.empty()) {
int u = q.front(), p = pos[u];
q.pop();
for (int i = h[u]; i; i = e[i].n) {
int v = e[i].t, w = e[i].w;
if (!~pos[v]) {
if (!nxt[p][w]) {
pos[v] = extend(w, p);
} else {
pos[v] = nxt[p][w];
}
q.push(v);
}
}
}
}
vector<int> G[N];
int tim, siz[N], dfn[N];
void DFS(int u) {
dfn[u] = ++tim, siz[u] = 1;
for (int v : G[u]) DFS(v), siz[u] += siz[v];
}
void BuildLinkTree() {
rep(i, 1, sz) G[link[i]].push_back(i);
DFS(0);
}
struct BIT {
ll sum[N];
void init() {
rep(i, 1, tim) sum[i] = 0;
}
void upd(int x, int v) {
for (; x <= tim; x += x & -x) sum[x] += v;
}
ll qry(int x) {
ll res = 0;
for (; x; x -= x & -x) res += sum[x];
return res;
}
ll qry(int l, int r) {
return qry(r) - qry(l - 1);
}
} bit;
int vis[N];
ll sum;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int id;
cin >> id >> n0;
rep(i, 1, n0 - 1) {
int u, v;
char c;
cin >> u >> v >> c, Add(u, v, c - 'a'), Add(v, u, c - 'a');
}
cin >> m;
rep(i, 1, m) {
cin >> Ops[i].opt;
if (Ops[i].opt == 2) {
cin >> Ops[i].rt >> Ops[i].s;
rep(p, 1, Ops[i].s - 1) {
int u, v;
char c;
cin >> u >> v >> c, Add(u, v, c - 'a'), Add(v, u, c - 'a');
}
}
if (Ops[i].opt == 3) cin >> Ops[i].S;
}
memset(pos, -1, sizeof(pos));
init(), pos[1] = 0, BFS(1), BuildLinkTree(), bit.init();
int cnt = n0;
auto update = [&](int x) {
x = pos[x];
bit.upd(dfn[x], 1);
while (x && !vis[x]) sum += len[x] - len[link[x]], vis[x] = 1, x = link[x];
};
rep(i, 1, cnt) update(i);
rep(i, 1, m) {
int opt = Ops[i].opt;
if (opt == 1) {
cout << sum << '\n';
}
if (opt == 2) {
rep(p, cnt + 1, cnt + Ops[i].s - 1) update(p);
cnt += Ops[i].s - 1;
}
if (opt == 3) {
string S = Ops[i].S;
int u = 0, Slen = S.length(), ok = 1;
rep(p, 0, Slen - 1) {
if (nxt[u][S[p] - 'a']) {
u = nxt[u][S[p] - 'a'];
} else {
ok = 0;
break;
}
}
if (ok) {
cout << bit.qry(dfn[u], dfn[u] + siz[u] - 1) << '\n';
} else {
cout << "0\n";
}
}
}
return 0;
}
标签:nxt,ch,DQS,trie,题解,len,int,link,copy
From: https://www.cnblogs.com/laijinyi/p/18425937