【CF163E 】e-Government

题目

两个\(log\)的树状数组套树剖？

我们对于给出的\(n\)个模式串建立\(AC\)自动机，之后对于每一个询问串直接丢上去匹配

如果这里是暴力的话，我们直接一路跳\(fail\)累加作为结束位置还没有被删除的点就好了

我们考虑一个快点的方式，树剖

把\(fail\)树建出来，直接在上面树剖维护就好了

由于只是单点修改，我们树状数组就好了

尽管是两个\(log\)，但毕竟树剖和树状数组都是出了名的小常数，还是能跑过\(1e6\)的

代码

#include<cstdio>

#include<queue>

#include<cstring>

#include<iostream>

#include<algorithm>

#define re register

#define lb(x) ((x)&(-x))

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

const int maxn=1e6+5;

struct E{int v,nxt;}e[maxn];

int n,m,cnt,__,num;

char S[maxn];

int c[maxn],dfn[maxn],sum[maxn],top[maxn],head[maxn];

int son[maxn][26],fa[maxn],pos[maxn],val[maxn],s[maxn];

inline void add_edge(int x,int y) {

	e[++num].v=y;e[num].nxt=head[x];head[x]=num;

}

inline void ins(int o) {

	scanf("%s",S+1);int len=strlen(S+1);

	int now=0;

	for(re int i=1;i<=len;i++) {

		if(!son[now][S[i]-'a']) son[now][S[i]-'a']=++cnt;

		now=son[now][S[i]-'a'];

	}

	pos[o]=now;

}

void dfs1(int x) {

	int maxx=-1;s[x]=-1,sum[x]=1;

	for(re int i=head[x];i;i=e[i].nxt) {

		dfs1(e[i].v);

		sum[x]+=sum[e[i].v];

		if(sum[e[i].v]>maxx) maxx=sum[e[i].v],s[x]=e[i].v;

	}

}

void dfs2(int x,int topf) {

	top[x]=topf,dfn[x]=++__;

	if(s[x]==-1) return;

	dfs2(s[x],topf);

	for(re int i=head[x];i;i=e[i].nxt)

	if(s[x]!=e[i].v) dfs2(e[i].v,e[i].v);

}

inline void Build() {

	std::queue<int> q;

	for(re int i=0;i<26;i++) if(son[0][i]) q.push(son[0][i]);

	while(!q.empty()) {

		int k=q.front();q.pop();

		for(re int i=0;i<26;i++)

		if(son[k][i]) fa[son[k][i]]=son[fa[k]][i],q.push(son[k][i]);

			else son[k][i]=son[fa[k]][i];

	}

}

inline void add(int x,int v) {for(re int i=x;i<=cnt;i+=lb(i)) c[i]+=v;}

inline int ask(int x) {

	int now=0;

	for(re int i=x;i;i-=lb(i)) now+=c[i];

	return now;

}

inline int query(int l,int r) {return ask(r)-ask(l-1);}

inline int Query(int x) {

	int tot=0;

	while(top[x]) {

		tot+=query(dfn[top[x]],dfn[x]);

		x=fa[top[x]];

	}

	tot+=query(dfn[0],dfn[x]);

	return tot;

}

int main() {

	scanf("%d%d",&m,&n);

	for(re int i=1;i<=n;i++) ins(i);

	Build();

	for(re int i=1;i<=cnt;i++) add_edge(fa[i],i);

	dfs1(0);dfs2(0,0);cnt++;

	for(re int i=1;i<=n;i++) val[i]=1,add(dfn[pos[i]],1);

	while(m--) {

		scanf("%s",S);int len=strlen(S);

		if(S[0]=='+') {

			int x=0;

			for(re int i=1;i<len;i++) x=(x<<3)+(x<<1)+S[i]-48;

			if(val[x]) continue;

			add(dfn[pos[x]],1);val[x]=1;

		}

		if(S[0]=='-') {

			int x=0;

			for(re int i=1;i<len;i++) x=(x<<3)+(x<<1)+S[i]-48;

			if(!val[x]) continue;

			add(dfn[pos[x]],-1);val[x]=0;

		}

		if(S[0]=='?') {

			int now=0;int ans=0;

			for(re int i=1;i<len;i++) {

				now=son[now][S[i]-'a'];

				ans+=Query(now);

			}

			printf("%d\n",ans);

		}

	}

	return 0;

}

巴特西

【CF163E 】e-Government

最新文章

热门文章