首页 > 其他分享 >BZOJ 4545 DQS 的 trie 题解

BZOJ 4545 DQS 的 trie 题解

时间：2024-09-22 21:34:54浏览次数：13  
标签：nxt ch DQS trie 题解 len int link copy

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

相关文章

  • 力扣72-编辑距离（Java详细题解）
    题目链接：力扣72-编辑距离前情提要：因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。dp五部曲。1.确定dp数组和i下标的含义。2.确定递推公式。3.dp初始化。4.确定dp的遍历顺序。5.如果没有ac打印dp数组利于debug。每一个dp题目如果都用这五步分析清楚，那么......
  • ABC372 F 题解
    F-TeleportingTakahashi2先把问题转化一下：把环断开成链，复制\((K+1)\)层，每走一步就相当于前进一层：可以想到一个简单的dp：设\(f(i,j)\)表示走到第\(i\)层第\(j\)个位置的方案数。初始化：\(f(0,1)=1\)，其它均为\(0\)，表示Takahashi从第\(0\)层的\(1\)位置......
  • 【题解】「Public NOIP Round #2」找零
    【题解】「PublicNOIPRound#2」找零[官解](PublicNOIPRound#2题解-博客-Qingyu的博客(pjudge.ac))Tag：背包、dp凸优化决策点单调触碰到知识点盲区了，所以来写几笔。首先，由于我们只关心最终状态下\(1\)的最多个数，其实有用的面值只有\(5,1\)（其她的可以当成若干......
  • U389139 至少有一位重复的数字-题解
    题目传送门一、举例说明以\(654923\)为例要判断在\([0,654923]\)区间至少有一位重复的数值的数，可以考虑其补集，即\(\color{red}所有位数均不重复的数\)，用\(N\)减去补集即为结果。首先可以将其分为两种情况。情况一，位数小于\(6\)位。所有位数均不重复的有\(9\time......
  • 【洛谷】P10417 [蓝桥杯 2023 国 A] 第 K 小的和 的题解
    【洛谷】P10417[蓝桥杯2023国A]第K小的和的题解题目传送门题解CSP-S1补全程序，致敬全A的答案，和神奇的预言家。写一下这篇的题解说不定能加CSP2024的RP代码#include<bits/stdc++.h>#definelowbit(x)x&(-x)#defineendl"\n"usingnamespacestd......
  • 【题解】【枚举】—— [NOIP2014 普及组] 比例简化
    【题解】【枚举】——[NOIP2014普及组]比例简化[NOIP2014普及组]比例简化题目背景题目描述输入格式输出格式输入输出样例输入#1输出#1提示1.思路解析2.AC代码[NOIP2014普及组]比例简化通往洛谷的传送门题目背景NOIP2014普及组T2题目描述在社交媒体......
  • 题解：AT_abc372_f [ABC372F] Teleporting Takahashi 2
    题意给出一个\(n\)个点的有向图，点\(i\)连向点\((i+1)\)，点\(n\)连向点\(1\)。再给你\(m\)条额外边。你的初始位置为\(1\)，问你移动\(k\)步的不同方案数（仅当路径不同时两个方案不同）。思路先想怎样暴力转移，显然移动\(k\)步到达一个点的方案数为所有跟这个点连边的移......
  • 题解：AT_abc372_e [ABC372E] K-th Largest Connected Components
    博客内食用更佳这道题的\(k\le10\)其实没什么用，代码区别仅在于手写平衡树和使用内置容器。这道题让查询与一个节点相连的所有点的信息，所以不难想到并查集。又因为让查询第\(k\)大，所以不难想到平衡树和线段树启发式合并。至此思路明显。我们对并查集中的每个节点开一个平......
  • 题解：AT_abc372_c [ABC372C] Count ABC Again
    博客内食用更佳乍一看好像是数据结构。我们结合题目所求内容考虑。对于每次修改，能对答案产生影响的最多只能是当前字符向前和向后延伸\(2\)个元素所构成的长为\(5\)的子串。那么我们先\(\mathcal{O}(n)\)计算出来初始答案。每次修改的时候，不妨先把\(i-2\simi\)和\(i-......
  • Anthropic介绍Contextual Retrieval
    人工智能模型要想在特定环境中发挥作用，往往需要获取背景知识。例如，客户支持聊天机器人需要了解具体的业务，而法律分析机器人则需要了解大量的过往案例。开发人员通常使用检索增强生成（RAG）来增强人工智能模型的知识。RAG是一种从知识库中检索相关信息并将其附加到用户提示......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99