题目链接
昨天晚上yy出了一个做法后，感觉...好难打啊...，于是先回去休息。今天来打时，还是感觉细节好多，于是就打了两个小时。打完过了编译后，居然过了样例，直接交，尼玛居然过了???......还好自己没有犯什么错误，不然就调死了...
进入正题
询问(x,y)时，就相当于在fail树中问x这个单词节点的子树中有多少个是y的前缀。
先建AC自动机，显然暴力一个词一个词的插入是不行的，可以慢慢的把trie树建出来，就是与别的单词重复的节点就不去建了，直接从以前从没出现的地方开始建(记一下是从trie上的哪个节点进入"空节点"的即可)，删除就往父亲跳，加入就往对应的儿子跳。
询问操作让我们想到线段树合并(若节点o是y的前缀，则o这棵线段树上的y处要+1)，把询问离线，挂在x对应的单词节点即可完成询问，现在的问题是如何处理"y的所有前缀"这一信息。
我的做法是对于AC自动机上的一个节点，所有以它作为前缀的串是若干个区间组成的，我们把这个修改区间挂在它对应的fail树节点上，然后若要使这个节点多一个修改区间，那么就要有一个删除操作，因此所有挂的修改区间是O(n)级别的，这样就解决了这个问题。
最后就很简单了，直接对fail树dfs一遍，对于节点o，把它的儿子合并给它，然后把要改的区间改了，直接把贡献加到对应的答案里就可以啦。
细节好像有点复杂，为什么别人都2KB AC，而我打了4KB??? 想复杂了以及代码太丑
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#define P puts("lala")
#define cp cerr<<"lala"<<endl
#define ln putchar('\n')
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
inline int read()
{
char ch=getchar();int g=1,re=0;
while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();}
while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+(ch^48),ch=getchar();
return re*g;
}
typedef long long ll;
typedef pair<int,int> pii; const int N=100050;
int son[N][26],fail[N],rt=1,sz=1,now=1,dep[N],from=1,father[N],tot=0,fnl[N];
int End[N],st[N];
vector<pii>ve[N],ask[N]; //ac-automation begin:
void insert(int o,char *s,int l,int r) //[l,r)
{
tot++;
for(int i=l;i<r;++i)
{
int x=s[i]-'a';
if(!son[o][x]) son[o][x]=++sz,dep[sz]=dep[o]+1,father[sz]=o;
o=son[o][x];
st[o]=tot;
}
from=0; now=o; fnl[tot]=o; End[o]++;
}
queue<int>q;
void buildfail()
{
q.push(rt);
while(!q.empty())
{
int o=q.front(); q.pop();
for(int i=0;i<26;++i)
{
int v=son[o][i];
if(!v) continue;
if(o==rt) fail[v]=rt;
else
{
int p=fail[o];
while(p)
{
if(son[p][i]) {fail[v]=son[p][i];break;}
p=fail[p];
}
if(!p) fail[v]=rt;
}
q.push(v);
}
}
}
//ac-automation end. //Segment tree
int root[N],ch[N*40][2],add[N*40],cnt=0; //need to modify
vector<int>stk;
inline int newnode()
{
if(stk.size())
{
int x=stk[stk.size()-1];
stk.pop_back();
ch[x][0]=ch[x][1]=add[x]=0;
return x;
}
else {cnt++;return cnt;}
}
void update(int &o,int l,int r,int x,int y) //[x,y]++
{
if(!o) o=newnode();
if(x<=l&&r<=y) {add[o]++;return ;}
int mid=l+r>>1;
if(x<=mid) update(ch[o][0],l,mid,x,y);
if(y>mid) update(ch[o][1],mid+1,r,x,y);
}
int query(int o,int l,int r,int x)
{
if(!o) return 0;
if(l==r) return add[o];
int mid=l+r>>1;
if(x<=mid) return query(ch[o][0],l,mid,x)+add[o];
else return query(ch[o][1],mid+1,r,x)+add[o];
}
int merge(int x1,int x2,int l,int r)
{
if(!x1) return x2;if(!x2) return x1;
add[x1]+=add[x2];
if(l==r) {stk.pb(x2);return x1;}
int mid=l+r>>1;
ch[x1][0]=merge(ch[x1][0],ch[x2][0],l,mid);
ch[x1][1]=merge(ch[x1][1],ch[x2][1],mid+1,r);
stk.pb(x2); return x1;
} //fail tree and answer
int ans[N];
vector<int>G[N];
void dfs(int u,int fa)
{
for(int i=0,siz=G[u].size();i<siz;++i)
{
int v=G[u][i];
if(v==fa) continue;
dfs(v,u);
root[u]=merge(root[u],root[v],1,tot);
}
for(int i=0,siz=ve[u].size();i<siz;++i)
{
int l=ve[u][i].fi,r=ve[u][i].se;
if(l<=r) update(root[u],1,tot,l,r);
}
for(int i=0,siz=ask[u].size();i<siz;++i)
ans[ask[u][i].fi]+=query(root[u],1,tot,ask[u][i].se);
} int slen=0;
char in[N],s[N]; //to check
struct CHK
{
int len;
void dfs(int o)
{
if(o==rt) len=0;
if(End[o]) for(int cas=1;cas<=End[o];++cas)
{
for(int i=0;i<len;++i) putchar(s[i]);ln;
}
for(int i=0;i<26;++i) if(son[o][i])
{
s[len++]=i+'a';
dfs(son[o][i]);
len--;
}
}
}chk; int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);freopen("1.out","w",stdout);
#endif
int i,j,opt,T;
scanf("%s",in);
int len=strlen(in);
dep[rt]=0;
for(i=0;i<len;++i)
{
if('a'<=in[i]&&in[i]<='z') //add a letter
{
s[slen++]=in[i];
if(!now) ;
else if(!son[now][in[i]-'a']) from=now,now=0;
else now=son[now][in[i]-'a'],st[now]=tot+1;
}
else if(in[i]=='B') //delete the last letter
{
slen--;
if(!now&&slen>dep[from]) ;
else if(!now&&slen==dep[from]) now=from,from=0;
else
{
ve[now].pb(mkp(st[now],tot));
//if(!st[now]) P;//
st[now]=0;
now=father[now];
}
}
else if(in[i]=='P') //print
{
if(now) tot++,fnl[tot]=now,End[now]++;
else insert(from,s,dep[from],slen);
}
} for(i=1;i<=sz;++i) if(st[i]) ve[i].pb(mkp(st[i],tot));
buildfail();
//chk.dfs(rt);
for(i=1;i<=sz;++i) if(fail[i]) G[fail[i]].pb(i);
//build fail-tree T=read();
for(i=1;i<=T;++i)
{
int x=read(),y=read();
ask[fnl[x]].pb(mkp(i,y));
}
dfs(rt,0);
for(i=1;i<=T;++i) printf("%d\n",ans[i]);
return 0;
}
/* */
