SAM + 虛樹。

看起來可以重鏈剖分簡化 lca 代碼！ https://www.cnblogs.com/cjyyb/p/10185462.html

const int N = int(1e6) + 9, C = 26, LV = 21; int Q; namespace SAM { int trans[N][C], fail[N], len[N], tail, tot; VI adj[N]; int dfn[N], lfn[N], dep[N], fa[LV][N]; char str[N/2]; int pos[N/2], n; inline int new_node(){ RST(trans[tot]); tail = tot; return tot++; } inline int new_node(int u){ CPY(trans[tot], trans[u]); fail[tot] = fail[u]; return tot++; } inline int move_up(int x, int t){ for (int lv=0;t;++lv,t>>=1) if (t&1) x = fa[lv][x]; return x; } inline int lca(int x, int y) { if (dep[x]>dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) return x; DWN(lv, LV, 0) if (fa[lv][x]!=fa[lv][y]) x = fa[lv][x], y = fa[lv][y]; return fa[0][x]; } inline bool cmp(int a, int b) { return dfn[a] < dfn[b]; } #define v trans[u] #define f fail[u] #define ff fail[uu] int Ext(int c){ int u = tail, uu = new_node(); len[uu] = len[u] + 1; while (u && !v) v = uu, u = f; if (!u && !v) v = uu, ff = 0; else{ if (len[v] == len[u] + 1) ff = v; else{ int _v = v, vv = new_node(_v); len[vv] = len[u] + 1; fail[_v] = ff = vv; while (v == _v) v = vv, u = f; } } return tail; } #undef v #define v (*it) void dfs(int u = 0) { dfn[u] = ++n; ECH(it, adj[u]) { dep[v] = dep[u] + 1; fa[0][v] = u; for (int lv=0;fa[lv+1][v]=fa[lv][fa[lv][v]];++lv); dfs(v); } lfn[u] = n; } void Init(){ tot = 0, tail = new_node(); RD(n, Q); RS(str); DWN(i, n, 0) pos[i+1] = Ext(str[i]-'a'); FOR(u, 1, tot) adj[f].PB(u); n = 0; dfs(); } #undef f #undef ff } // using namespace SAM; namespace VT { VI adj[N]; VI T; int sta[N], top; int f[N]; LL z; void dfs(int u = T[0]) { ECH(it, adj[u]) { dfs(v); z += (LL) f[u] * f[v] * SAM::len[u]; f[u] += f[v]; } } void clean(int u = T[0]) { ECH(it, adj[u]) { clean(v); } f[u] = 0; adj[u].clear(); } void Gao() { Rush { int t = SAM::pos[RD()]; f[t] = 1; T.PB(t); } UNQ(T, SAM::cmp); DWN(i, SZ(T)-1, 0) T.PB(SAM::lca(T[i], T[i+1])); UNQ(T, SAM::cmp); top = 0; ECH(it, T) {//for (auto u: T) { int u = *it; while (top && SAM::lfn[sta[top]] < SAM::dfn[u]) --top; if (top) adj[sta[top]].PB(u); sta[++top] = u; } z = 0; dfs(); printf("%lld\n", z); clean(); T.clear(); } } // using namespace VT; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif SAM::Init(); DO(Q) VT::Gao(); }