526互联

[NOI2011] 阿狸的打字机

发布时间 2023-04-17 16:19:12作者: basicecho

[NOI2011] 阿狸的打字机

/*
其实也就是动态建树的问题，如果这个点有，那就把这个点给激活。
如果这个点消失了，对应的把他的值取消掉就可以了
这样就可以在对应的树下进行查询。

然后就是单点修改，对树的子树大小进行查询，用树状数组进行维护就可以了

首先根据fail建立子树
在fail树上查找某个串出现的次数，其实也就是子树的大小就可以了


*/

#include <bits/stdc++.h>
using namespace std;
const int M=2e5+5;

char s[M];
int n,m;
int idx[M],cnt=0;
int fa[M],ch[M][26],fail[M],tot;

void init_tire() {//建立tire树
    scanf("%s",s+1);
    n=strlen(s+1);
    int p=0;
    for(int i=1;i<=n;i++) {
        if(s[i]=='P')idx[++cnt]=p;
        else if(s[i]=='B')p=fa[p];
        else {
            int v=s[i]-'a';
            if(ch[p][v]==0)ch[p][v]=++tot,fa[ch[p][v]]=p;
            p=ch[p][v];
        }
    }
}

void build() {
    queue<int>q;
    for(int i=0;i<26;i++)
        if(ch[0][i])q.push(ch[0][i]);
    while(!q.empty()) {
        int now=q.front();q.pop();
        for(int i=0;i<26;i++) {
            if(ch[now][i]) {
                fail[ch[now][i]]=ch[fail[now]][i];
                q.push(ch[now][i]);
            }
            else ch[now][i]=ch[fail[now]][i];
        }
    }
}

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


int L[M],R[M],id=0;
vector<int>g[M];
void dfs(int now,int fa) {
    L[now]=++id;
    for(auto to:g[now])
        if(to!=fa)dfs(to,now);
    R[now]=id;
}

int c[M];
void add(int i,int v) {
    while(i<=id) {
        c[i]+=v;
        i+=lowbit(i);
    }
}

int query(int i) {
    int ans=0;
    while(i) {
        ans+=c[i];
        i-=lowbit(i);
    }
    return ans;
}

#define fi first
#define se second

int ans[M];
vector<int>v[M];
pair<int,int>q[M];
void solve() {
    int m;cin>>m;
    for(int i=1;i<=m;i++) {
        cin>>q[i].fi>>q[i].se;
        v[q[i].se].push_back(i);
    }
    for(int i=0;i<=tot;i++)g[fail[i]].push_back(i);
    dfs(0,0);
    int p=0,cnt=0;
    for(int i=1;i<=n;i++) {
        if(s[i]=='P') {
            cnt++;
            for(auto j:v[cnt]) {
                int x=idx[q[j].fi];
                ans[j]=query(R[x])-query(L[x]-1);
            }
        }
        else if(s[i]=='B')add(L[p],-1),p=fa[p];
        else p=ch[p][s[i]-'a'],add(L[p],1);
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
}

int main() {
    init_tire();
    build();
    solve();
    return 0;
}