Educational Codeforces Round 16 F - String Set Queries （CDQ分治+AC自动机）

题目链接：

http://codeforces.com/contest/710/problem/F

题意：

1. 集合加入一个串

2. 集合删除一个串

3. 问集合中的串在给定串中出现的次数和（可重复）

要求强制在线

思路：

如果是离线的话，直接cdq分治，每次求左半边的AC自动机去更新右半边

强制在线的话，只要保存一下log个左半边的AC自动机就好了

复杂度：O（(n+s)log(n))

#include<bits/stdc++.h>
using namespace std;

const int N=900005;

int ch[N][26],fail[N],cnt[N],f[N];
int tot;
int newnode(){
	tot++;
	for (int i=0;i<26;i++) ch[tot][i]=0;
	fail[tot]=0;  cnt[tot]=0;
	return tot;
}
int merge(int x,int y){
	if (!x||!y) return x+y;
	cnt[x]+=cnt[y];
	for (int i=0;i<26;i++)
		ch[x][i]=merge(ch[x][i],ch[y][i]);
	return x;
}

int root[20];
void insert(int root,char *s,int y){
	int now=root;
	for (int i=0;s[i];i++){
		int w=s[i]-'a';
		if (!ch[now][w]) ch[now][w]=newnode();
		now=ch[now][w];
	}
	cnt[now]+=y;
}
int go(int root,int u,int w){
	while(u!=root&&!ch[u][w]) u=fail[u];
	if (ch[u][w]) return ch[u][w];
	return u;
}
void build(int root){
	queue<int>Q;
	fail[root]=root;
	for (int i=0;i<26;i++){
		int v=ch[root][i];
		if (v){
			fail[v]=root;
			Q.push(v);
		}
	}
	while(!Q.empty()){
		int u=Q.front(); Q.pop();
		f[u]=f[fail[u]]+cnt[u];
		for (int i=0;i<26;i++){
			int v=ch[u][i];
			if (v){
				fail[v]=go(root,fail[u],i);
				Q.push(v);
			}
		}
	}
}
int query(int root,char *s){
	int ret=0;
	int now=root;
	for (int i=0;s[i];i++){
		int w=s[i]-'a';
		now=go(root,now,w);
		ret+=f[now];
	}
	return ret;
}
void init(int &root){
	root=newnode();
	build(root);
}

int tp;
char s[N];
int solve(int l,int r,int deep){
	if (l==r){
		cin>>tp>>s;
		init(root[deep]);
		if (tp<3){
			int y;
			if (tp==1) y=1; else y=-1;
			insert(root[deep],s,y);
		}
		else{
			long long ans=0;
			for (int d=1;d<deep;d++) ans+=query(root[d],s);
			cout<<ans<<endl;
			fflush(stdout);
		}
		return root[deep];
	}
	init(root[deep]);
	int mid=(l+r)/2;
	int rtl=solve(l,mid,deep+1);
	root[deep]=merge(root[deep],rtl);
	build(root[deep]);
	int rtr=solve(mid+1,r,deep+1);
	root[deep]=merge(root[deep],rtr);
	build(root[deep]);
	return root[deep];
}
int main(){
	ios::sync_with_stdio(false);
	int n; cin>>n;
	solve(1,n,1);
}