对一台打字机，有两个功能字符：P 表示打印当前缓存中的串，B 表示删去缓存末尾的一个字符。给定一个操作串。你需要回答 \(m\) 个询问，每个询问指定 \((x,y)\)，求第 \(x\) 个打印的字符串在第 \(y\) 个打印的字符串中出现了多少次。
Solution
问 \(S\) 是否在 \(T\) 出现，就是问 ACAM 上，\(T\) 到 Trie 根的沿着 Trans 边路径上，有没有 \(S\) 在 fail 树上的子树内的结点
先处理操作串来建 Trie，遇到 P 操作就将当前结点打标记，遇到 B 操作就退回到 Trie 上的父亲结点
对于询问 \((x,y)\)，就是要求 fail 树上以 \(x\) 为根的子树内，有多少个 \(y\) 沿着 Trie 树上的边走到根的路径上的结点
注意这里的 Trie 树和 fail 树上的边要加以区分，这就是为什么不能直接套个链剖走人
考虑离线，将 Trie 树 DFS 一遍，同时维护一个桶，桶中下标为 \(i\) 的位置表示当前所在点到根的链上是否有 \(i\) 这个点
这个维护方式是显然的，每次 DFS 进入一个点时就 \(+1\)，完成一个点时就 \(-1\)
我们将每个询问挂在 \(y\) 上，那么进入 \(y\) 后，询问 \(x\) 这个点的子树和即可
于是桶需要按照 DFS 序做下标，需要用树状数组维护
（注意区分这里所涉及的 Trans 图边，Fail 树边，Trie 树边）
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
const int dbg = 0;
int ar[N]; // index: 1 ~ N
int lowbit(int t) { return t & (-t); }
void add(int i, int v) {
if(i==0) return;
for (; i < N; ar[i] += v, i += lowbit(i));
}
int sum(int i) {
int s = 0;
for (; i > 0; s += ar[i], i -= lowbit(i));
return s;
}
int sum(int i,int j) {
return sum(j) - sum(i-1);
}
queue <int> q;
int c[N][26],fi[N],cnt,tot,fa[N],pos[N];
vector <int> val[N];
vector <int> g[N];
vector <int> tr[N];
void ins(char *str) {
int len=strlen(str), p=0;
for(int i=0; i<len; i++) {
if(str[i]=='B') {p=fa[p]; continue;}
if(str[i]=='P') {val[p].push_back(++tot); pos[tot]=p; continue;}
int v=str[i]-'a';
if(!c[p][v]) c[p][v]=++cnt,tr[p].push_back(c[p][v]);
fa[c[p][v]]=p;
p=c[p][v];
}
}
void build() {
for(int i=0; i<26; i++) if(c[0][i]) fi[c[0][i]]=0, q.push(c[0][i]);
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=0; i<26; i++)
if(c[u][i]) fi[c[u][i]]=c[fi[u]][i], q.push(c[u][i]);
else c[u][i]=c[fi[u]][i];
}
}
void query(char *s) {
int len=strlen(s);
int p=0;
for(int i=0; i<len; i++) {
p=c[p][s[i]-'a'];
}
}
char str[N];
int dfn[N],fin[N],ind,ans[N];
struct cquery {
int x,y,id;
};
vector <cquery> qu[N];
void dfs(int p) {
dfn[p]=++ind;
for(int q:g[p]) dfs(q);
fin[p]=ind;
}
void solve(int p) {
add(dfn[p],1);
for(cquery t:qu[p]) {
ans[t.id]=sum(dfn[t.x],fin[t.x]);
}
for(int q:tr[p]) solve(q);
add(dfn[p],-1);
}
signed main() {
ios::sync_with_stdio(false);
cin>>str;
ins(str);
build();
for(int i=1;i<=cnt;i++) g[fi[i]].push_back(i);
dfs(0);
if(dbg) {
cout<<"fail"<<endl;
for(int i=0;i<=cnt;i++) {
for(int j:g[i]) cout<<i<<"->"<<j<<endl;
}
cout<<"trans"<<endl;
for(int i=0;i<=cnt;i++) {
for(int j:tr[i]) cout<<i<<"->"<<j<<endl;
}
for(int i=0;i<=cnt;i++) cout<<dfn[i]<<" ";
cout<<endl;
}
int m,x,y;
cin>>m;
for(int i=1;i<=m;i++) {
cin>>x>>y;
x=pos[x];
y=pos[y];
if(dbg) cout<<"translated "<<x<<" "<<y<<endl;
qu[y].push_back({x,y,i});
}
solve(0);
for(int i=1;i<=m;i++) {
cout<<ans[i]<<endl;
}
}