PerfectPan
;

BZOJ 2434 [Noi2011]阿狸的打字机

September 29, 2018

题目链接https://darkbzoj.tk/problem/2434

题意:略。

思路:首先需要观察到这个打字的过程就是在构造一个 TrieTrie 树,然后考虑询问,可以很容易想到相当于是在 failfail 树上询问字符串 xx 结尾的那个节点为根的子树里有多少个 yy 的节点。但是直接求不好求,所以我们把询问离线,重新走一遍 TrieTrie 的构建过程,用树状数组维护 dfsdfs 序的 sumsum 值,每走一个节点就单点加一,这样走到一个字符串结尾的时候我们就把这个字符串所有节点都在 failfail 树上权值加一了然后就处理这个字符串的所有询问好了,一堆区间查询 sumsum 值。

#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
using namespace std;
const int N=1e5+10;
const int SIGMA_SIZE=26;
int T,i,j,tot,dfs_clock,n,m,x,y,cnt,ans[N],sum[N],q[N],fail[N],fa[N],pos[N],L[N],R[N],son[N][SIGMA_SIZE];
char s[N];
vector<int>G[N];
vector<pair<int,int> >qu[N];
inline int lowbit(int x){return x&(-x);}
int get(int x){
	int res=0;
	for (;x>0;x-=lowbit(x)) res+=sum[x];
	return res;
}
void add(int x,int v){for(;x<=dfs_clock;x+=lowbit(x))sum[x]+=v;}
void build(char* s){
	int p=0,id=0;
	for (i=0;s[i];++i){
		if (s[i]=='P') pos[++id]=p;
		else if (s[i]=='B') p=fa[p];
		else{
			int idx=s[i]-'a';
			if (!son[p][idx]){
				son[p][idx]=++tot;
				fa[tot]=p;
			}
			p=son[p][idx];
		}
	}
}
void getfail(){
	int head=0,tail=0;
	for (i=0;i<SIGMA_SIZE;++i){
		if (son[0][i]) q[tail++]=son[0][i];
	}
	for (;head!=tail;){
		int u=q[head++];
		for (i=0;i<SIGMA_SIZE;++i){
			if (son[u][i]){
				fail[son[u][i]]=son[fail[u]][i];
				q[tail++]=son[u][i];
			}
			else son[u][i]=son[fail[u]][i];
		}
	}
}
void dfs(int u){
	L[u]=++dfs_clock;
	for (int i=0;i<(int)G[u].size();++i){
		int v=G[u][i];
		dfs(v);
	}
	R[u]=dfs_clock;
}
void solve(){
	int p=0,id=0;	
	add(L[p],1);
	for (i=0;s[i];++i){
		if (s[i]=='P'){
			id++;
			for (j=0;j<(int)qu[id].size();++j){
				int u=qu[id][j].first,idx=qu[id][j].second;
				ans[idx]=get(R[pos[u]])-get(L[pos[u]]-1);
			}
		}
		else if (s[i]=='B'){
			add(L[p],-1);
			p=fa[p];
		}
		else{
			p=son[p][s[i]-'a'];
			add(L[p],1);
		}
	}
}
int main(){
	scanf("%s",s);
	build(s);
	getfail();
	for (i=1;i<=tot;++i) G[fail[i]].PB(i);
	dfs(0);
	for (scanf("%d",&m),i=1;i<=m;++i){
		scanf("%d%d",&x,&y);
		qu[y].PB(MP(x,i));
	}
	solve();
	for (i=1;i<=m;++i) printf("%d\n",ans[i]);
	return 0;
}

Yiming Pan

Written by Yiming Pan who lives and works in Hangzhou China. Welcome follow me on Github

Cannot load comments. Please check you network.