BZOJ2434：[NOI2011]阿狸的打字机—

https://www.lydsy.com/JudgeOnline/problem.php?id=2434

https://www.luogu.org/problemnew/show/P2414

打字机上只有28个按键，分别印有26个小写英文字母和'B'、'P'两个字母。经阿狸研究发现，这个打字机是这样工作的：

·输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。

·按一下印有'B'的按键，打字机凹槽中最后一个字母会消失。

·按一下印有'P'的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。

例如，阿狸输入aPaPBbP，纸上被打印的字符如下：

a aa ab 我们把纸上打印出来的字符串从1开始顺序编号，一直到n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数(x,y)（其中1≤x,y≤n），打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。

阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？

因为没有前置技能现学了一发fail树，再回头看就是fail树棵题了。

因为询问x串在y串出现几次，可以直接转化为y串在trie的节点在fail树x串末节点的子树中出现了几次（这个比较绕，但是很好想。）

而且因为这题特殊的建trie的方式，我们完全可以离线，对y排序，然后重新跑一遍建trie的过程，这样就保证了y的快（顺）速（序）查找。

那么中间记录y节点的工作就交给树状数组完成即可。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cctype>

#include<cstdio>

#include<queue>

#include<cmath>

using namespace std;

typedef long long ll;

const int S=1e5+;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

struct trie{

    int a[],fa,fail;

}tr[S];

struct node{

    int to,nxt;

}e[S];

struct data{

    int x,y,id;

}p[S];

int m,tot,cnt,ed[S],id,head[S];

int idx,pos[S],a[S],size[S],ans[S];

char s[S];

queue<int>q;

inline bool cmp(data a,data b){

    return a.y<b.y;

}

inline void add(int u,int v){

    e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;

}

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

inline void ins(int x,int y){

    for(int i=x;i<=idx;i+=lowbit(i))a[i]+=y;

}

inline int qry(int x){

    int res=;

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

    return res;

}

void build(){

    int n=strlen(s),now=;

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

        if(s[i]=='P')ed[++id]=now;

        else if(s[i]=='B')now=tr[now].fa;

        else{

            int c=s[i]-'a';

            if(!tr[now].a[c])tr[now].a[c]=++tot;

            tr[tr[now].a[c]].fa=now;

            now=tr[now].a[c];

        }

    }

}

void dfs_trie(){

    int n=strlen(s),now=,r=,j=,sum=;

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

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

            sum++;

            for(;j<=m;j++){

                if(p[j].y==sum){

                    int l=pos[ed[p[j].x]],r=l+size[ed[p[j].x]]-;

                    ans[p[j].id]=qry(r)-qry(l-);

                }else break;

            }

        }

        else if(s[i]=='B'){

            ins(pos[now],-);

            now=tr[now].fa;

        }

        else{

            now=tr[now].a[s[i]-'a'];

            ins(pos[now],);

        }

    }

}

void getfail(){

    tr[].fail=;

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

        int u=tr[].a[i];

        if(u){

            tr[u].fail=;

            q.push(u);

            add(,u);

        }

    }

    while(!q.empty()){

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

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

            if(tr[u].a[i]){

                int v=tr[u].a[i];

                tr[v].fail=tr[tr[u].fail].a[i];

                q.push(v);

                add(tr[v].fail,v);

            }else tr[u].a[i]=tr[tr[u].fail].a[i];

        }

    }

    return;

}

void dfs_fail(int u){

    pos[u]=++idx;size[u]=;

    for(int i=head[u];i;i=e[i].nxt){

        int v=e[i].to;

        dfs_fail(v);

        size[u]+=size[v];

    }

}

int main(){

    scanf("%s",s);

    build();getfail();dfs_fail();

    m=read();

    for(int i=;i<=m;i++){

        p[i].x=read(),p[i].y=read(),p[i].id=i;

    }

    sort(p+,p+m+,cmp);

    dfs_trie();

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

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/ +

+++++++++++++++++++++++++++++++++++++++++++

巴特西

BZOJ2434：[NOI2011]阿狸的打字机——题解

最新文章

热门文章