P2414 [NOI2011]阿狸的打字机

时间:2023-03-10 04:19:43
P2414 [NOI2011]阿狸的打字机

P2414 [NOI2011]阿狸的打字机

AC自动机+树状数组

优质题解 <------题目分析

先AC自动机搞出Trie图

然后根据fail指针建一只新树

把树映射(拍扁)到一个序列上,用树状数组加速优化

在新树上处理时间戳,用于树状数组维护

在原Trie树上跑dfs查询答案。

因为Trie下标从0开始,树状数组从1开始

所以所有有关的下标都要注意

attention:树状数组上限一定要+1!(就是它卡了我1天TAT)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
inline int max(int &a,int &b) {return a>b ?a:b;}
const int N=1e5+;
struct Trie{int nxt_[],nxt[],fail,end,fa;}a[N];
int n,tot,cnt,word[N],ans[N];
struct AC_automaton{ //AC自动机
char q[N];
void Trie_build(){
scanf("%s",q);
int u=,len=strlen(q),st=;
while(q[st]=='B'||q[st]=='P') ++st;
for(int i=st;i<len;++i){
if(q[i]=='B') u=a[u].fa; //删除一位
else if(q[i]=='P') word[++tot]=u,a[u].end=tot; //加入新单词
else{
int p=q[i]-'a';
if(!a[u].nxt[p]) a[u].nxt[p]=++cnt,a[cnt].fa=u;
u=a[u].nxt[p];
}
}
}
void AC_build(){
queue <int> h;
for(int i=;i<;++i) if(a[].nxt[i]) h.push(a[].nxt[i]);
while(!h.empty()){
int x=h.front(); h.pop();
for(int i=;i<;++i){
int &to=a[x].nxt[i];
if(to){
a[to].fail=a[a[x].fail].nxt[i];
h.push(to);
}else to=a[a[x].fail].nxt[i];
}
}
}
void backup(){ //对Trie树的nxt进行备份由于下面的遍历(AC自动机会改变nxt)
for(int i=;i<=cnt;++i)
for(int j=;j<;++j)
a[i].nxt_[j]=a[i].nxt[j];
}
}mo1;
struct tree_array{ //树状数组
int c[N];
inline void add(int x,int k) {for(;x<=cnt+;x+=x&-x) c[x]+=k;} //上限要+1!
inline int sum(int x){int res=; for(;x;x-=x&-x) res+=c[x]; return res;}
}mo2;
int cnt1,hd1[N],nxt1[N],ed1[N],poi1[N];
int cnt2,hd2[N],nxt2[N],ed2[N],poi2[N],id[N];
inline void add_edge1(int x,int y){ //fail树邻接表
nxt1[ed1[x]]=++cnt1; hd1[x]= hd1[x] ? hd1[x]:cnt1;
ed1[x]=cnt1; poi1[cnt1]=y;
}
inline void add_edge2(int x,int y,int _id){ //存询问邻接表
nxt2[ed2[x]]=++cnt2; hd2[x]= hd2[x] ? hd2[x]:cnt2;
ed2[x]=cnt2; poi2[cnt2]=y; id[cnt2]=_id;
}
struct new_tree{
int dfs_clock,dfn[N],low[N];
inline void dfs1(int x){ //fail树遍历
dfn[x]=++dfs_clock; //时间戳
for(int i=hd1[x];i;i=nxt1[i]) dfs1(poi1[i]);
low[x]=dfs_clock; //size[x]=low[x]-dfn[x]
}
inline void dfs2(int x){ //Trie树遍历
mo2.add(dfn[x],); //保证只有该条路径上
if(a[x].end) //该点是某个单词的结尾
{
for(int i=hd2[a[x].end];i;i=nxt2[i]){
int e=word[poi2[i]];
ans[id[i]]=mo2.sum(low[e])-mo2.sum(dfn[e]-);
}
}
for(int i=;i<;++i) if(a[x].nxt_[i]) dfs2(a[x].nxt_[i]); //沿原树遍历
mo2.add(dfn[x],-);
}
}mo3;
int main(){
mo1.Trie_build(); mo1.backup(); mo1.AC_build();
for(int i=;i<=cnt;++i) add_edge1(a[i].fail,i); //fail树连边
scanf("%d",&n); int q1,q2;
for(int i=;i<=n;++i) scanf("%d%d",&q1,&q2),add_edge2(q2,q1,i); //把询问存到邻接表上
mo3.dfs1(); mo3.dfs2();
for(int i=;i<=n;++i) printf("%d\n",ans[i]);
return ;
}