bzoj2434 fail树 + dfs序 + 树状数组

时间：2020-12-25 21:38:33

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

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

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

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

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

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

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

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

题意

首先第一个想法一定是把所有单词插入到AC自动机并且保存所有N个单词的end结点位置，对于x，y串的询问，将y串end结点到根节点之间的所有结点跳一边fail指针，将经过的结点全部 + 1，查询一下x的结点保存的大小即可。

当然这是纯暴力的写法，我们考虑去优化。

首先把对于同一y的x，当然可以合并起来一起处理

其次对于y串包含x串，就意味着x被包含的次数为fail树上将y全部结点加入之后的子树和。

对于这一类动态的去维护子树和的行为，我们自然而然的想到dfs序，求出整颗fail树上的dfs序之后用树状数组动态的对于每个询问加入y串和查询然后删除y串一气呵成。

到了这一步看似已经稳如狗，可交上去依旧TLE

事实上仔细看题意里给出的字符串构造方式，我们就会发现这些字符串并不是毫无关联的字符串，换言之，在开始的insert里面，不需要每次都插入一个独立的字符串，而是只需要开一个now来模拟当前结点的位置，如果遇到P则直接返回now，如果遇到B则将now变为他的父节点，插入时就变为它指向的目标子结点。

不仅仅如此，即使在最后离线查询的时候，事实上也是不需要每次都动态的加入整个y串和删除y串的

只要模拟当前字符串的移动路线，每次遇到B的时候返回父节点并且删除当前结点在dfs序中的加成，遇到插入的时候就在树状数组中相应位置 + 1，每次查询就不用遍历y结点到根节点的所有结点了。

#include <map>

#include <set>

#include <ctime>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

inline int read(){int now=;register char c=getchar();for(;!isdigit(c);c=getchar());

for(;isdigit(c);now=now*+c-'',c=getchar());return now;}

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

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

#define Mem(f, x) memset(f,x,sizeof(f))

#define Sca(x) scanf("%d", &x)

#define Sca2(x,y) scanf("%d%d",&x,&y)

#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define Scl(x) scanf("%lld",&x);

#define Pri(x) printf("%d\n", x)

#define Prl(x) printf("%lld\n",x);

#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();

#define LL long long

#define ULL unsigned long long

#define mp make_pair

#define PII pair<int,int>

#define PIL pair<int,long long>

#define PLL pair<long long,long long>

#define pb push_back

#define fi first

#define se second

typedef vector<int> VI;

const double eps = 1e-;

const int maxn = 1e5 + ;

const int maxm = 5e5 + ;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

int N,M,K;

char mstr[maxn];

char str[maxn];

int Index[maxn];

//链式前向星

struct Edge{

    int to,next;

}edge[maxm];

int head[maxm],TOT;

void init(int n){

    for(int i =  ; i < n; i ++) head[i] = -;

    TOT = ;

}

void add(int u,int v){

    edge[TOT].to = v;

    edge[TOT].next = head[u];

    head[u] = TOT++;

}

//AC自动机

int nxt[maxm][],fail[maxm],tot,root,fa[maxm];

int newnode(int f){

    for(int i =  ; i < ; i ++) nxt[tot][i] = -;

    fa[tot] = f;

    return tot++;

}

void init(){

    tot = ;root = newnode();

}

void Build(){

    queue<int>Q; init(tot);

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

        if(~nxt[root][i]){

            fail[nxt[root][i]] = root;

            add(root,nxt[root][i]);

            Q.push(nxt[root][i]);

        }else{

            nxt[root][i] = root;

        }

    }

    while(!Q.empty()){

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

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

            if(~nxt[u][i]){

                fail[nxt[u][i]] = nxt[fail[u]][i];

                add(nxt[fail[u]][i],nxt[u][i]);

                Q.push(nxt[u][i]);

            }else{

                nxt[u][i] = nxt[fail[u]][i];

            }

        }

    }

}

//dfs序

int num = ;

PII pos[maxm];

void dfs(int t,int la){

    pos[t].fi = ++num;

    for(int i = head[t]; ~i; i = edge[i].next){

        int v = edge[i].to;

        if(v == la) continue;

        dfs(v,t);

    }

    pos[t].se = ++num;

}

//树状数组

int tree[maxm * ];

void tadd(int x,int t){

    for(;x <= num; x += x & -x) tree[x] += t;

}

int getsum(int x){

    int s = ;

    for(;x > ;x -= x & -x) s += tree[x];

    return s;

}

struct Query{

    int x,y,id;

}query[maxn];

bool cmp(Query a,Query b){

    return a.y < b.y;

}

int ans[maxn];

int main(){

    //freopen("C.in","r",stdin);

    scanf("%s",mstr);

    N = ;

    init();

    int now = ;

    for(int i = ; mstr[i]; i ++){

        if(mstr[i] == 'B'){

            now = fa[now];

        }else if(mstr[i] == 'P'){

            Index[++N] = now;

        }else{

            if(nxt[now][mstr[i] - 'a'] == -){

                nxt[now][mstr[i] - 'a'] = newnode(now);

            }

            now = nxt[now][mstr[i] - 'a'];

        }

    }

    Build();

    dfs(root,-);

    Sca(M);

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

        query[i].x = read();

        query[i].y = read();

        query[i].id = i;

    }

    sort(query + ,query +  + M,cmp);

    now = root;

    int cnt = ;

    int si = ;

    for(int i =  ; mstr[i] && cnt <= M; i ++){

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

            si++;

            while(cnt <= M && query[cnt].y == si){

                ans[query[cnt].id] = getsum(pos[Index[query[cnt].x]].se) - getsum(pos[Index[query[cnt].x]].fi - );

                cnt++;

            }

        }else if(mstr[i] == 'B'){

            tadd(pos[now].fi,-);

            now = fa[now];

        }else{

            now = nxt[now][mstr[i] - 'a'];

            tadd(pos[now].fi,);

        }

    }

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

        Pri(ans[i]);

    }

    return ;

}

相关文章