yyb 好强啊...

Problem

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

Solution

考虑在 fail 树上进行求解

事实上就是询问在 fail 树上一个儿子中的子树有多少个某类点

然后就不会了.jpg

因为 fail 树暴跳会 gg

然而事实上是把询问离线就行了 emm

怎么离线戳：https://www.luogu.org/blog/cjyyb/solution-p2414

Code

// Code by ajcxsu
// Problem: ali

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10, M=2e5+10;
int h[N], to[M], nexp[M], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
char S[N];
int dfn[N];

#define lowbit(x) x&-x
int C[N];
void updata(int x, int d) {
    while(x<N) C[x]+=d, x+=lowbit(x);
}
int query(int x) {
    int ret=0;
    while(x) ret+=C[x], x-=lowbit(x);
    return ret;
}

int idx;
struct Node {
    Node *ch[26], *fail, *rin;
    int end, id, dep;
    vector<int> qa, qb; // what where
    Node () { end=0; memset(ch, 0, sizeof(ch)), fail=rin=0; }
} *rt, po[N], *pp=po;
void ini() {
    rt=pp++, rt->fail=rt->rin=rt, rt->id=++idx;
}

Node *stk[N], *ha[N];
int t, n, m;
void insert(Node *x) {
    stk[++t]=x, x->dep=t;
    Node *at;
    int num=0;
    for(int i=0;i<n;i++) {
        at=stk[t];
        if(S[i]=='B') t--;
        else if(S[i]=='P') at->end=1, ha[++num]=at;
        else {
            if(!at->ch[S[i]-'a'])
                at->ch[S[i]-'a']=pp++, at->ch[S[i]-'a']->id=++idx,
                at->ch[S[i]-'a']->dep=t+1;
            stk[++t]=at->ch[S[i]-'a'];
        }
    }
}
queue<Node*> qu;
void build(Node *x) {
    for(int i=0;i<26;i++)
        if(x->ch[i]) x->ch[i]->fail=x->ch[i]->rin=x, qu.push(x->ch[i]), ins(x->id, x->ch[i]->id);
        else x->ch[i]=x;
    while(!qu.empty()) {
        x=qu.front(), qu.pop();
        for(int i=0;i<26;i++)
            if(x->ch[i])
                x->ch[i]->fail=x->fail->ch[i],
                x->ch[i]->rin=x->ch[i]->fail->end?x->ch[i]->fail:x->ch[i]->fail->rin,
                ins(x->ch[i]->rin->id, x->ch[i]->id),
                qu.push(x->ch[i]);
            else x->ch[i]=x->fail->ch[i];
    }
}

int siz[N];
void dfs(int x) {
    dfn[x]=++idx, siz[x]=1;
    for(int u=h[x];u;u=nexp[u])
        if(!dfn[to[u]]) dfs(to[u]), siz[x]+=siz[to[u]];
}
int ans[N];
void dfs2(Node *x) {
    updata(dfn[x->id], 1);
    if(x->end)
        for(int i=0, j=x->qa.size(); i<j; i++)
            ans[x->qb[i]]=query(dfn[x->qa[i]]+siz[x->qa[i]]-1) - query(dfn[x->qa[i]]-1);
    for(int i=0;i<26;i++)
        if(x->ch[i]->dep>x->dep) dfs2(x->ch[i]);
    updata(dfn[x->id], -1);
}

int main() {
    ios::sync_with_stdio(false), ini();
    cin>>S>>m, n=strlen(S);
    insert(rt), build(rt), idx=0, dfs(1);
    int u, v;
    for(int i=0;i<m;i++)
        cin>>v>>u, ha[u]->qa.push_back(ha[v]->id), ha[u]->qb.push_back(i);
    dfs2(rt);
    for(int i=0;i<m;i++) cout<<ans[i]<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-2414.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆