【题解】[NOI2011]阿狸的打字机

阿狸的打字机

\(\text{Solution:}\)

首先观察三种操作：一种是插入一个字符，一种是退回上一步(回到父亲节点)。

所以，我们可以对操作串进行模拟，并处理出每一个串在树上的位置。

接下来，我们考虑如何处理询问。\(y\)是需要跑的串，于是我们应按照\(y\)排序以保证在处理这个\(y\)之前，它本身或者其他的东西没有加进树上过。

考虑同样的模板处理方法：对于一个串出现了几次，我只需要统计这个串结尾编号在\(fail\)树子树中的\(cnt\)个数。

于是自然想到维护子树和的有利武器：\(dfs\)序和树状数组。

于是，我们可以预先处理掉\(dfs\)序，并直接模拟在\(opt\)串上进行的移动操作即可。

这里解释模板的处理思路：首先，既然我们跳到了这个\(fail\)指针，说明我们一定匹配完过当前这整个\(fail\)指针（参考定义）。

观察\(fail\)树上的结构，我们结合上面所述可以知道，所有直接或间接指向\(x\)这个节点的\(fail\)指针，只要跳到了，就一定匹配到过整个串\(x\).

于是，我们可以统计\(fail\)树上\(x\)子树中的\(cnt\),注意每匹配到一个点，应该在\(fail\)树上把从它到根节点的路径上全部加\(1.\)但实际上我们只需要在匹配到的时候对它单点\(+1,\)再\(dfs\)一下\(fail\)树就可以了。

#include<bits/stdc++.h>

using namespace std;

const int MAXN=2000100;

int tot,tr[MAXN],fa[MAXN];

int pos[MAXN],num;

struct Tree{

	int ch[26],fail;

}T[MAXN];

vector<int>to[MAXN];

struct Qu{

	int x,y,id;

}Q[MAXN];

inline bool cmp(Qu a,Qu b){return a.y<b.y;}

char opt[MAXN];

void Build(char *s,int L){

	int u=0;

	for(int i=0;i<L;++i){

		if(opt[i]=='B')u=fa[u];

		else if(opt[i]=='P')pos[++num]=u;

		else if(T[u].ch[s[i]-'a'])u=T[u].ch[s[i]-'a'];

		else T[u].ch[s[i]-'a']=++tot,fa[tot]=u,u=tot;//介于本题需要有跳回上一步的操作，所以需要记录一下fa

	}

	//对操作串进行处理，并记录下每一个询问串在树上的位置

}

void bfs(){

	queue<int>q;

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

		if(T[0].ch[i]){

			int v=T[0].ch[i];

			T[v].fail=0;

			q.push(v);

		}

	}

	while(!q.empty()){

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

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

			if(T[u].ch[i]){

				int v=T[u].ch[i];

				T[v].fail=T[T[u].fail].ch[i];

				q.push(v);

			}

			else T[u].ch[i]=T[T[u].fail].ch[i];

		}

		to[T[u].fail].push_back(u);

	}

	//建立AC自动机并建立fail树

}

int dfn[MAXN],I,ed[MAXN];

void dfs(int u){

	dfn[u]=++I;

	for(int i=0;i<to[u].size();++i)dfs(to[u][i]);

	ed[u]=I;

	//处理出每一个树上节点的dfs序列，注意是树上的

}

inline int lowbit(int x){return (x&(-x));}

inline void add(int x,int v){for(;x<=I;x+=lowbit(x))tr[x]+=v;}

inline int query(int x){int res=0;for(;x;x-=lowbit(x))res+=tr[x];return res;}

//树状数组不解释

int ans[MAXN],m;

int main(){

	scanf("%s",opt);

	int len=strlen(opt);

	Build(opt,len);

	bfs();dfs(0);

	//预处理

	scanf("%d",&m);

	for(int i=1;i<=m;++i)scanf("%d%d",&Q[i].x,&Q[i].y),Q[i].id=i;

	sort(Q+1,Q+m+1,cmp);//按照询问的y从小到大处理

	int u=0,r=0,l=0;

	for(int i=1;i<=m;++i){

		while(r<Q[i].y){

			if(opt[l]=='P')r++;//更新目前处理到第几个串

			else if(opt[l]=='B'){

				add(dfn[u],-1);

				u=fa[u];

			}//删掉当前u所在字符

			else{

				u=T[u].ch[opt[l]-'a'];

				add(dfn[u],1);

			}//更新下一个字符

			l++;//操作串后移

		}

		ans[Q[i].id]=query(ed[pos[Q[i].x]])-query(dfn[pos[Q[i].x]]-1);//注意双映射！

	}

	for(int i=1;i<=m;++i)printf("%d\n",ans[i]);

	return 0;

}

巴特西

【题解】[NOI2011]阿狸的打字机

最新文章

热门文章