MnZn 求助熟练剖分

/*
 * Author: Endline
 * Time: 2024/01/07 20:24:02
 * File: P2414.cpp
 */
#include<bits/stdc++.h>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
using ll=long long;
const int MAXN=100002;
int CNT;
double ST,ED;
string str;
int m;
int ans[MAXN],val[MAXN],pos[MAXN],rt[MAXN];
vector<pair<int,int>>qr[MAXN];
struct SegmentTree
{
    int tr[MAXN<<2],tag[MAXN<<2];
    inline void addtag(int l,int r,int p,int k)
    {
        tr[p]+=(r-l+1)*k,tag[p]+=k;
        return;
    }
    inline void pushup(int p)
    {
        tr[p]=tr[ls(p)]+tr[rs(p)];
        return;
    }
    inline void pushdown(int l,int r,int p)
    {
        if(tag[p])
        {
            int mid=l+r>>1;
            addtag(l,mid,ls(p),tag[p]);addtag(mid+1,r,rs(p),tag[p]);
            tag[p]=0;
        }
    }
    inline void update(int l,int r,int s,int t,int p,int k)
    {
        if(s>=l&&t<=r){addtag(s,t,p,k);return;}
        int mid=s+t>>1;
        pushdown(s,t,p);
        if(mid>=l)update(l,r,s,mid,ls(p),k);
        if(mid<r)update(l,r,mid+1,t,rs(p),k);
        pushup(p);
    }
    inline int query(int goal,int s,int t,int p)
    {
        if(s==t)return tr[p];
        int mid=s+t>>1;
        pushdown(s,t,p);
        if(mid>=goal)return query(goal,s,mid,ls(p));
        else return query(goal,mid+1,t,rs(p));
    }
}tree;
struct AC_Automaton
{
    int cnt,tot,ecnt,dcnt;
    int tr[MAXN][26],fail[MAXN],fa[MAXN],head[MAXN];
    int dfn[MAXN],siz[MAXN],son[MAXN],top[MAXN];
    bool vis[MAXN],flag[MAXN][26];
    vector<int>id[MAXN];
    struct edge
    {
        int v,nxt;
    }e[MAXN];
    inline void addedge(int u,int v)
    {
        e[++ecnt]={v,head[u]};
        head[u]=ecnt;
    }
    inline void insert(string str)
    {
        int p=0,pre=0;
        for(int i=0;i<str.size();i++)
        {
            if(str[i]=='B'){p=fa[p];continue;}
            if(str[i]=='P'){id[p].push_back(++tot);pos[tot]=p;continue;}
            if(!tr[p][str[i]-'a'])tr[p][str[i]-'a']=++cnt,flag[p][str[i]-'a']=true;
            fa[tr[p][str[i]-'a']]=p;
            p=tr[p][str[i]-'a'];
        }
    }
    inline void build()
    {
        queue<int>q;
        for(int i=0;i<26;i++)
            if(tr[0][i])q.push(tr[0][i]);
        while(!q.empty())
        {
            int p=q.front();q.pop();
            for(int i=0;i<26;i++)
                if(tr[p][i])fail[tr[p][i]]=tr[fail[p]][i],q.push(tr[p][i]);
                else tr[p][i]=tr[fail[p]][i];
        }
        return;
    }
    void dfs1(int u)
    {
        siz[u]=1;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            dfs1(v);
            siz[u]+=siz[v];
            if(siz[v]>siz[son[u]])son[u]=v;
        }
    }
    void dfs2(int u,int topn)
    {
        top[u]=topn;
        dfn[u]=++dcnt;
        if(son[u])dfs2(son[u],topn);
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(v==son[u])continue;
            dfs2(v,v);
        }
    }
    inline void update(int u,int k)
    {
        while(top[u])
        {
            tree.update(dfn[top[u]],dfn[u],1,dcnt,1,k),CNT++;
            u=fail[top[u]];
        }
        tree.update(dfn[0],dfn[u],1,dcnt,1,k),CNT++;
        if(CNT%10000==0)debug("%d\n",CNT);
        return;
    }
    inline void prework()
    {
        for(int i=1;i<=cnt;i++)addedge(fail[i],i);
        dfs1(0);dfs2(0,0);
    }
    void dfs(int p)
    {
        vis[p]=true;
        update(p,1);
        for(auto i:qr[p])ans[i.second]=tree.query(dfn[i.first],1,dcnt,1);
        for(int i=0;i<26;i++)
            if(tr[p][i]&&flag[p][i])dfs(tr[p][i]);
        update(p,-1);
    }
}At;
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>str;
    At.insert(str);At.build();
    At.prework();
    cin>>m;
    for(int i=1,x,y;i<=m;i++)
    {
        cin>>x>>y;
        qr[pos[y]].push_back({pos[x],i});
    }
    At.dfs(0);
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}