【[NOI2011]阿狸的打字机】

首先发现这个插入的非常有特点，我们可以直接利用这个特殊的性质在\(Trie\)树上模拟指针的进退

之后得到了\(Trie\)树，先无脑建出\(AC\)机

之后考虑一下如何写暴力

最简单的暴力对于每一个询问直接在\(AC\)机上匹配之后跳\(fail\)，跳到多少次\(fail\)就代表出现了几次

显然这并不能通过

考虑一下优雅的跳\(fail\)

发现\(fail\)指针建出来恰好是一个树的结构，因为一个点的\(fail\)只能指向唯一的一个点

把这样一棵\(fail\)树建出来，我们直接在\(fail\)树上判断另一个串的结束标记是否在这个点到根的路径上就好了

可以对\(fail\)树搞一个\(dfs\)序，之后把问题转化为单点加，区间查显然可以直接用一个树状数组来维护

但是这个样子还是要对每一个串都进行一遍这样的操作

但是考虑到每一个查询操作有很多共用的节点，我们可以直接按照\(Trie\)上的顺序离线下来，之后利用大量重复的这一特性去统计答案

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#define re register

#define maxn 100005

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define lowbit(x) ((x)&(-x))

struct E

{

	int v,nxt;

}e[maxn<<1];

int head[maxn],fa[maxn];

int n,m,to[maxn],dfn[maxn],DFN[maxn];

int cnt,num,tot,__,t;

struct Ask

{

	int x,y,rk,ans;

}a[maxn];

inline int read()

{

	char c=getchar();

	int x=0;

	while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();

	return x;

}

inline void add_edge(int x,int y)

{

	e[++num].v=y;

	e[num].nxt=head[x];

	head[x]=num;

}

char S[maxn];

int c[maxn],sum[maxn];

inline void add(int x,int val){for(re int i=x;i<=cnt+1;i+=lowbit(i)) c[i]+=val;}

inline int ask(int x){int now=0;for(re int i=x;i;i-=lowbit(i)) now+=c[i];return now;}

int son[maxn][26],trie[maxn][26],fail[maxn],Ans[maxn];

inline void ins()

{

	int now=0;

	fa[now]=0;

	scanf("%s",S+1);

	int len=strlen(S+1);

	for(re int i=1;i<=len;i++)

	{

		if(S[i]=='B')

		{

			now=fa[now];

			continue;

		}

		if(S[i]=='P')

		{

			to[++tot]=now;

			continue;

		}

		if(!son[now][S[i]-'a']) son[now][S[i]-'a']=trie[now][S[i]-'a']=++cnt,fa[cnt]=now;

		now=son[now][S[i]-'a'];

	}

}

inline void Build()

{

	std::queue<int> q;

	for(re int i=0;i<26;i++) if(son[0][i]) q.push(son[0][i]);

	while(!q.empty())

	{

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

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

		if(son[k][i]) fail[son[k][i]]=son[fail[k]][i],q.push(son[k][i]);

			else son[k][i]=son[fail[k]][i];

	}

}

inline int cmp(Ask A,Ask B)

{

	return dfn[A.x]<dfn[B.x];

}

void DFS(int x)

{

	dfn[x]=++__;

	if(x!=fail[x]) add_edge(fail[x],x);//printf("%d\n",x);

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

		if(trie[x][i]) DFS(trie[x][i]);

}

void dfs(int x,int F)

{

	sum[x]=1;DFN[x]=++__;

	for(re int i=head[x];i;i=e[i].nxt)

	if(e[i].v!=F)

	{

		dfs(e[i].v,x);

		sum[x]+=sum[e[i].v];

	}

}

void Dfs(int x)

{

	__++;

	add(DFN[x],1);

	while(a[t].x==x)

	{

		int Y=to[a[t].y];

		a[t].ans=ask(DFN[Y]+sum[Y]-1)-ask(DFN[Y]-1);

		t++;

	}

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

		if(trie[x][i]) Dfs(trie[x][i]);

	add(DFN[x],-1);

}

int main()

{

	ins();

	Build(),DFS(0);

	n=read();

	for(re int i=1;i<=n;i++) a[i].x=read(),a[i].y=read(),a[i].rk=i,std::swap(a[i].x,a[i].y),a[i].x=to[a[i].x];

	std::sort(a+1,a+n+1,cmp);

	__=0,dfs(0,0),__=0;t=1;

	Dfs(0);

	for(re int i=1;i<=n;i++) Ans[a[i].rk]=a[i].ans;

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

	return 0;

}

巴特西

【[NOI2011]阿狸的打字机】

最新文章

热门文章