【bzoj2434】 Noi2011—阿狸的打字机

http://www.lydsy.com/JudgeOnline/problem.php?id=2434 (题目链接)

题意

　　给出一个字符串，$P$表示输出，$B$表示退格。$m$组询问$(x,y)$，问第$x$个串在第$y$个串中出现了多少次。

Solution

　　构出fail树，搞出dfs序，那么显然问题就转化为了自动机上匹配y时经过的节点有多少个在x的子树内，我们将询问排好序做过去树状数组单点修改维护子树和就可以了。

细节

　　mdzz建ACM和查询的时候没注意，直接重新开始TLE飞了。

代码

// bzoj2434

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<queue>

#include<ctime>

#define LL long long

#define inf (1ll<<30)

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)

using namespace std;

const int maxn=100010;

int n,m,sz=1,cnt,dfn,pos[maxn],head[maxn],c[maxn],in[maxn],out[maxn],ans[maxn];

char ch[maxn],tmp[maxn];

struct data {int x,y,id;}q[maxn];

struct edge {int to,next;}e[maxn<<1];

struct node {

	int son[26],next,fa;

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

}tr[maxn];

int lowbit(int x) {

	return x&-x;

}

void add(int x,int val) {

	for (int i=x;i<=sz;i+=lowbit(i)) c[i]+=val;

}

int query(int x) {

	int res=0;

	for (int i=x;i;i-=lowbit(i)) res+=c[i];

	return res;

}

void link(int u,int v) {

	e[++cnt]=(edge){v,head[u]};head[u]=cnt;

	e[++cnt]=(edge){u,head[v]};head[v]=cnt;

}

void dfs(int x,int fa) {

	in[x]=++dfn;

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

		if (e[i].to!=fa) dfs(e[i].to,x);

	out[x]=dfn;

}

bool cmp(data a,data b) {

	return a.y<b.y;

}

void buildfail() {

	queue<int> q;q.push(1);

	tr[1].next=0;

	while (!q.empty()) {

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

		for (int i=0;i<26;i++) if (tr[x][i]) {

				int p=tr[x].next;

				while (!tr[p][i]) p=tr[p].next;

				link(tr[x][i],tr[p][i]);

				tr[tr[x][i]].next=tr[p][i];

				q.push(tr[x][i]);

			}

	}

}

int main() {

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

	for (int i=0;i<26;i++) tr[0][i]=1;

	n=strlen(ch+1);int p=1,id=0;

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

		if (ch[i]=='P') pos[++id]=p;

		else if (ch[i]=='B') p=tr[p].fa;

		else {

			if (!tr[p][ch[i]-'a']) tr[p][ch[i]-'a']=++sz;

			tr[tr[p][ch[i]-'a']].fa=p;p=tr[p][ch[i]-'a'];

		}

	}

	buildfail();

	dfs(1,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+1+m,cmp);

	int pp=1;id=0,p=1;

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

		if (ch[i]=='P') {

			id++;

			for (;q[pp].y==id;pp++) {

				int t=pos[q[pp].x];

				ans[q[pp].id]=query(out[t])-query(in[t]-1);

			}

		}

		else if (ch[i]=='B') add(in[p],-1),p=tr[p].fa;

		else p=tr[p][ch[i]-'a'],add(in[p],1);

	}

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

	return 0;

}