题目链接：
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);
}
