BZOJ 3881[COCI2015]Divljak (AC自动机+dfs序+lca+BIT)
2024-09-03 21:33:07
显然是用AC自动机
先构建好AC自动机,当B中插入新的串时就在trie上跑,对于当前点,首先这个点所代表的串一定出现过,然后这个点指向的fail也一定出现过.那么我们把每个点fail当作父亲,建一棵fail树,那么到一个点一定会让fail树中这个点到根的路径所有点的答案+1.然后因为在同一个串中多次出现只算一次,那么就需要求这些到根的路径的并集.可以用树链剖分求区间交集做.
但这道题我们只用单点查询,区间修改,可以用树状数组做.因为是求交集,这里有一个trick就是把所有的点按dfs序排序,然后每个点到根+1,相邻的点的lca到根-1,就简单的求出了并集.
我们将区间修改单点查询转化为单点修改区间查询.那么一个点就只用查子树内的就行了.
具体可以看代码.修改的总点数不超过询问的串的总长,所以时间复杂度是O(nlogn)O(nlogn)O(nlogn)
lca是用树剖求的
CODE
#include<bits/stdc++.h>
using namespace std;
char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
template<class T>inline void read(T &res) {
char ch; int flg = 1; while(!isdigit(ch=getchar()))if(ch=='-')flg=-flg;
for(res=ch-'0';isdigit(ch=getchar());res=res*10+ch-'0'); res*=flg;
}
const int MAXN = 2000005;
const int C = 26;
int n, m, node[MAXN];
int tmr, dfn[MAXN], seq[MAXN], dep[MAXN], son[MAXN], sz[MAXN], top[MAXN], fa[MAXN];
int fir[MAXN], to[MAXN], nxt[MAXN], cnt;
inline void link(int u, int v) { to[cnt] = v; nxt[cnt] = fir[u]; fir[u] = cnt++; }
void dfs1(int x) {
dep[x] = dep[fa[x]] + 1; sz[x] = 1;
for(int v, i = fir[x]; ~i; i = nxt[i]) {
dfs1(v=to[i]), sz[x] += sz[v];
if(!(~son[x]) || sz[son[x]] < sz[v])
son[x] = v;
}
}
void dfs2(int x, int tp) {
top[x] = tp; seq[dfn[x]=++tmr] = x;
if(~son[x]) dfs2(son[x], tp);
for(int v, i = fir[x]; ~i; i = nxt[i])
if((v=to[i]) != son[x]) dfs2(v, v);
}
inline int lca(int x, int y) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
x = fa[top[x]];
}
return dep[x] < dep[y] ? x : y;
}
struct Aho_Corasick {
int ch[MAXN][C], fail[MAXN], tot, q[MAXN];
inline int insert(char *s) {
int r = 0, i = 0, indx;
while(*s) {
if(!ch[r][indx=(*s++)-'a'])
ch[r][indx] = ++tot;
r = ch[r][indx];
}
return r;
}
inline void build() {
int r = 0, head = 0, tail = 0;
fail[q[tail++]=r] = -1;
while(head < tail) {
r = q[head++];
for(int v, indx = 0; indx < C; ++indx)
if((v=ch[r][indx])) {
q[tail++] = v;
fail[v] = (r == 0 ? 0 : ch[fail[r]][indx]);
}
else ch[r][indx] = (r == 0 ? 0 : ch[fail[r]][indx]);
}
memset(fir, -1, sizeof fir);
memset(son, -1, sizeof son);
for(int i = 1; i <= tot; ++i) link(fa[i]=fail[i], i);
dfs1(0); dfs2(0, 0);
}
int T[MAXN];
inline void upd(int x, int val) {
while(x <= tmr) T[x] += val, x += x&-x;
}
inline int qsum(int x) { int re = 0;
while(x) re += T[x], x -= x&-x;
return re;
}
void modify(char *s) {
int r = 0, i = 0, indx, cur = 0;
while(*s) {
r = ch[r][indx=(*s++)-'a'];
q[++cur] = dfn[r];
}
sort(q + 1, q + cur + 1);
cur = unique(q + 1, q + cur + 1) - q - 1;
for(int i = 1; i <= cur; ++i) {
upd(q[i], 1);
if(i > 1) upd(dfn[lca(seq[q[i]], seq[q[i-1]])], -1);
}
}
}trie;
char s[MAXN];
int main() {
read(n);
for(int i = 1; i <= n; ++i)
scanf("%s", s), node[i] = trie.insert(s);
trie.build();
read(m);
int op, x;
while(m--) {
read(op);
if(op == 1) scanf("%s", s), trie.modify(s);
else read(x), x = node[x], printf("%d\n", trie.qsum(dfn[x]+sz[x]-1)-trie.qsum(dfn[x]-1));
}
}
最新文章
- WCF基础知识
- composer -vvv
- C语言 goto, return等跳转
- PAT_1016 部分A+B
- PHP读取CSV大文件导入数据库的示例
- .NET应用架构设计—四色原型模式(色彩造型、域无关的模型)(概念版)
- Java+XSL合并多个XML文件
- python[error] - mysql_config not found
- GetSystemInfo()
- 【每日一题】 UVA - 1589 Xiangqi 函数+模拟 wa了两天
- P4008 [NOI2003]文本编辑器
- python 引入本地module
- 谷歌算法研究员:我为什么钟爱PyTorch?
- 使用Axure RP原型设计实践02,自定义部件以及熟悉与部件相关面板
- In R, how to split/subset a data frame by factors in one column?
- 用Ant给Unity3D导出Eclipse工程打包APK
- JDBC的介绍
- 10.numpy基本用法
- django-模板,过滤器
- Django Managers管理器