当前位置：首页 > news >正文

8.22 万灵药（SAM + Trie + 树剖 + 线段树）

news 来源：原创 2024/9/20 9:38:22

http://cplusoj.com/d/senior/p/479?tid=66c55d60c098fe0f6786d470

考虑如何求两个前缀的最长后缀

我们建一个SAM，把这两个前缀找出来，他们的公共后缀集合为这两个点在fail树上的公共祖先

那么最长后缀就是它们lca对应的最长串

接下来我们要统计这些串的前缀，首先肯定要拿一个trie来维护

直接建trie是 $O(n^2)$ 的，但是这里有一个重要的性质，就是我们发现SAM节点和trie树节点是一一对应的

具体的，当前SAM节点在trie树上的父亲必然是某个走到当前节点的节点。我们只需要判断符合条件的len就行

因此我们现在把trie建出来了

我们现在要实现的功能是什么？

对于trie树，我们要查询一个点到根路径上所有值的权值，并对这条路径所有点的权值±1

这个东西直接剖就行

后面维护理论上要拿zkw或者树状数组才行，但我线段树冲过去了，复杂度是双log的

如果改成全局平衡二叉树，那就可以优化成单log了，黄队好像打了

my code：

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL#define debug(...) fprintf(stdout, ##__VA_ARGS__)#define debag(...) fprintf(stderr, ##__VA_ARGS__)
#else#define debug(...) void(0)#define debag(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 1000010
int n, m, i, j, k, T, ans; struct Binary_tree {int cnt[N]; void add(int x, int y) { if(x == 0) return cnt[x] += y, void(); while(x < N) cnt[x] += y, x += x & -x; }int qry(int x) {int ans = cnt[0]; while(x) ans += cnt[x], x -= x & -x; return ans; }
}Bin1, Bin2;struct Segment_tree {
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mid ((l + r) >> 1)int tag[N << 2], s[N << 2]; void push_down(int k, int l, int r) {tag[ls] += tag[k]; tag[rs] += tag[k]; s[ls] += tag[k] * (mid - l + 1); s[rs] += tag[k] * (r - mid); assert(s[ls] + s[rs] == s[k]); tag[k] = 0; }void push_up(int k) { s[k] = s[ls] + s[rs]; }void add(int k, int l, int r, int x, int y, int v) {if(l >= x && r <= y) return tag[k] += v, s[k] += v * (r - l + 1), void(); push_down(k, l, r); if(x <= mid) add(ls, l, mid, x, y, v); if(y >= mid + 1) add(rs, mid + 1, r, x, y, v); push_up(k); }int qry(int k, int l, int r, int x, int y) {if(l >= x && r <= y) return s[k]; push_down(k, l, r); int ans = 0; if(x <= mid) ans += qry(ls, l, mid, x, y); if(y >= mid + 1) ans += qry(rs, mid + 1, r, x, y); 
//		debug("qry[%lld %lld] is %lld\n", )return ans; }
}Seg;struct Big_Binary_tree {void add(int x, int v) {Bin1.add(x, v); Bin2.add(x, v * x); }void add(int l, int r, int v) {l = max(2ll, l); debug("[%lld %lld] += %lld\n", l, r, v); Seg.add(1, 1, 2 * n, l, r, v); 
//		add(r, v); add(l - 1, -v); }int qry(int x) {int s1 = Bin1.qry(x), s2 = Bin2.qry(x); return (x + 1) * s1 - s2; }int qry(int l, int r) {l = max(2ll, l); 
//		debug("qry[%lld %lld] is %lld\n", l, r, Seg.qry(1, 1, 2 * n, l, r)); return Seg.qry(1, 1, 2 * n, l, r); 
//		return qry(r) - qry(l - 1); }
}Bin;struct Trie_tree {int tot = 0; int w[N], son[N], f[N], top[N], cnt[N]; int dfn[N]; vector<int>G[N]; void add_edge(int x, int y, int c) { G[x].pb(y); f[y] = x; }void dfs1(int x) {w[x] = 1; for(int y : G[x]) {dfs1(y); w[x] += w[y]; if(w[y] > w[son[x]]) son[x] = y; } }void dfs2(int x, int Top) {top[x] = Top; dfn[x] = ++tot; debug("Pou %lld [%lld]\n", x, Top); if(son[x]) dfs2(son[x], Top); for(int y : G[x]) if(y != son[x]) dfs2(y, y); }void work() {dfs1(1); dfs2(1, 1); }void calc_add(int x, int v) {while(x) {int l = dfn[top[x]], r = dfn[x]; if(v == -1) Bin.add(l, r, v); ans += Bin.qry(l, r) * v; if(v == 1) Bin.add(l, r, v); x = f[top[x]]; }}void modify(int x) {calc_add(x, cnt[x] ? -1 : 1); cnt[x] ^= 1; }
}Trie;struct Sam {int i, j, k, tot, lst; int len[N], fail[N], nxt[N][6]; vector<int>G[N]; void init() { tot = lst = 1; }int ins(int x) {int u = ++tot, p, q, cq; p = lst; lst = u; len[u] = len[p] + 1; while(p && !nxt[p][x]) nxt[p][x] = u, p = fail[p]; if(!p) return fail[u] = 1, u; q = nxt[p][x]; if(len[p] + 1 == len[q]) fail[u] = q; else {cq = ++tot; fail[cq] = fail[q]; fail[q] = fail[u] = cq; len[cq] = len[p] + 1; memcpy(nxt[cq], nxt[q], sizeof(nxt[q])); while(p && nxt[p][x] == q) nxt[p][x] = cq, p = fail[p]; }return u; }int dep[N], f[N][22]; void dfs(int x, int fa) {dep[x] = dep[fa] + 1; for(int y : G[x]) dfs(y, x); }void work() {for(i = 1; i <= tot; ++i) {for(j = 1; j <= 4; ++j) {k = nxt[i][j]; if(k) debug("%lld --%c--> %lld\n", i, (char)(j + 'a' - 1), k); if(len[i] + 1 == len[k]) {Trie.add_edge(i, k, j); debug("%lld --> %lld\n", i, k);  }}}for(i = 1; i <= tot; ++i) debug("%lld ", fail[i]); debug("\n"); for(i = 2; i <= tot; ++i) G[fail[i]].pb(i), f[i][0] = fail[i]; for(k = 1; k <= 20; ++k) for(i = 1; i <= tot; ++i) f[i][k] = f[f[i][k - 1]][k - 1]; dfs(1, 0); }int lca(int x, int y) {if(x == y) return x; if(dep[x] < dep[y]) swap(x, y); for(int k = 20; k >= 0; --k)if(dep[f[x][k]] >= dep[y]) x = f[x][k]; if(x == y) return x; for(int k = 20; k >= 0; --k)if(f[x][k] != f[y][k]) x = f[x][k], y = f[y][k]; return f[x][0]; }}SAM;char s[N]; 
int point[N]; signed main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}scanf("%s", s + 1); n = strlen(s + 1); SAM.init(); for(i = 1; i <= n; ++i) point[i] = SAM.ins(s[i] - 'a' + 1); SAM.work(); Trie.work(); int Q = read(); while(Q--) {int x, y, z; x = read(); y = read(); z = SAM.lca(point[x], point[y]); debug("max(%lld %lld) = %lld\n", x, y, z); Trie.modify(z); printf("%lld\n", ans); }return 0;
}