NOI 2011 阿狸的打字机（AC自动机+主席树）

时间：2022-09-25 19:55:25

题意

https://loj.ac/problem/2444

思路

​多串匹配，考虑 \(\text{AC}\) 自动机。模拟打字的过程，先建出一棵 \(\text{Trie}\) 树，把它变成自动机。对于每一个询问 \((x,y)\) ，相当于求 \(y\) 在 \(\text{Trie}\) 上的父节点中，有多少个是 \(x\) 在 \(\text{fail}\) 树上的子节点。

不难想到离线，我们对于 \(y\) 记录所有 \(x\) ，求出 \(\text{fail}\) 树上的 \(\text{dfs}\) 序并在 \(\text{Trie}\) 树上 \(\text{dfs}\) ，通过主席树维护遍历到每个点时 \(\text{fail}\) 树 \(\text{dfs}\) 序的信息，每遍历到一个点就把它在 \(\text{fail}\) 树上的 \(\text{dfs}\) 序记进主席树里，并回答在这个点上的所有询问即可。

代码

#include<bits/stdc++.h>

#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)

#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)

#define x first

#define y second

using namespace std;

template<typename T,typename _T>inline bool chk_min(T &x,const _T y){return y<x?x=y,1:0;}

template<typename T,typename _T>inline bool chk_max(T &x,const _T y){return x<y?x=y,1:0;}

typedef long long ll;

typedef pair<int,int> pii;

const int N=1e5+5;

const int NN=N*40;

template<const int maxn,const int maxm>struct Linked_list

{

	int head[maxn],to[maxm],nxt[maxm],tot;

	Linked_list(){clear();}

	void clear(){memset(head,-1,sizeof(head));tot=0;}

	void add(int u,int v){to[++tot]=v,nxt[tot]=head[u],head[u]=tot;}

	#define EOR(i,G,u) for(int i=G.head[u];~i;i=G.nxt[i])

};

struct ChairmanTree

{

	int rt[N],lson[NN],rson[NN],sum[NN];

	int tot;

	int &operator [](const int x){return rt[x];}

	void build()

	{

		memset(rt,0,sizeof(rt));

		sum[tot=0]=lson[0]=rson[0]=0;

	}

	void create(int &k)

	{

		sum[++tot]=sum[k],lson[tot]=lson[k],rson[tot]=rson[k];

		k=tot;

	}

	void update(int &k,int x,int val,int l,int r)

	{

		create(k);

		if(l==r){sum[k]+=val;return;}

		int mid=(l+r)>>1;

		if(x<=mid)update(lson[k],x,val,l,mid);

		else update(rson[k],x,val,mid+1,r);

		sum[k]=sum[lson[k]]+sum[rson[k]];

	}

	int query(int k,int L,int R,int l,int r)

	{

		if(L<=l&&r<=R)return sum[k];

		int mid=(l+r)>>1;

		if(R<=mid)return query(lson[k],L,R,l,mid);

		else if(L>mid)return query(rson[k],L,R,mid+1,r);

		else return query(lson[k],L,R,l,mid)+query(rson[k],L,R,mid+1,r);

	}

};

Linked_list<N,N>G;

ChairmanTree CT;

int fa[N],son[N][26],ch[N][26],f[N],idx[N];

int L[N],R[N],ord;

int rt,tot;

string str;

int n,m;

vector<pii>vec[N];

int Output[N];

void build(){rt=tot=0;}

void create(int &k)

{

	if(!k)

	{

		k=++tot;

		FOR(i,0,25)son[k][i]=ch[k][i]=0;

	}

}

void get_fail()

{

	queue<int>Q;

	while(!Q.empty())Q.pop();

	f[rt]=rt;

	FOR(i,0,25)

	{

		if(ch[rt][i])f[ch[rt][i]]=rt,Q.push(ch[rt][i]);

		else ch[rt][i]=rt;

	}

	while(!Q.empty())

	{

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

		FOR(i,0,25)

		{

			if(ch[u][i])f[ch[u][i]]=ch[f[u]][i],Q.push(ch[u][i]);

			else ch[u][i]=ch[f[u]][i];

		}

	}

}

void dfs_fail(int u)

{

	L[u]=++ord;

	EOR(i,G,u)dfs_fail(G.to[i]);

	R[u]=ord;

}

void init(string &str)

{

	create(rt);

	fa[rt]=rt;

	int now=rt;

	FOR(i,0,str.length()-1)

	{

		char a=str[i];

		if(a>='a'&&a<='z')

		{

			if(!ch[now][a-'a'])

			{

				create(ch[now][a-'a']);

				son[now][a-'a']=ch[now][a-'a'];

				fa[son[now][a-'a']]=now;

			}

			now=ch[now][a-'a'];

		}

		else if(a=='P')

		{

			n++;

			idx[n]=now;

		}

		else if(a=='B')now=fa[now];

	}

}

void dfs_trie(int u)

{

	CT.update(CT[u],L[u],1,1,tot);

	FOR(i,0,(int)vec[u].size()-1)

	{

		int x=vec[u][i].x,id=vec[u][i].y;

		Output[id]=CT.query(CT[u],L[x],R[x],1,tot);

	}

	FOR(i,0,25)if(son[u][i])

	{

		CT[son[u][i]]=CT[u];

		dfs_trie(son[u][i]);

	}

}

int main()

{

	cin>>str>>m;

	init(str);

	FOR(i,1,m)

	{

		int x,y;

		scanf("%d%d",&x,&y);

		vec[idx[y]].push_back(pii(idx[x],i));

	}

	get_fail();

	FOR(i,1,tot)if(f[i]!=i)G.add(f[i],i);

	ord=0;dfs_fail(rt);

	CT.build();

	dfs_trie(rt);

	FOR(i,1,m)printf("%d\n",Output[i]);

	return 0;

}

相关文章