题面
Sol
首先有个很显然的暴力，构建AC自动机
每次询问(x, y)就(y)暴跳(trie中的父亲)，(跳fail)检查是否有(x)的结尾
# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(1e5 + 10);
int m, ch[26][_], tot, fail[_], id[_], cnt, fa[_];
char op[_];
queue <int> Q;
IL void GetFail(){
for(RG int i = 0; i < 26; ++i) if(ch[i][0]) Q.push(ch[i][0]);
while(!Q.empty()){
RG int fa = Q.front(); Q.pop();
for(RG int i = 0; i < 26; ++i)
if(ch[i][fa]) fail[ch[i][fa]] = ch[i][fail[fa]], Q.push(ch[i][fa]);
else ch[i][fa] = ch[i][fail[fa]];
}
}
int main(RG int argc, RG char* argv[]){
scanf(" %s%d", op, &m); RG int len = strlen(op), i = 0, x = 0;
while(i < len){
if(op[i] == 'P') id[++cnt] = x;
else if(op[i] == 'B') x = fa[x];
else fa[++tot] = x, x = ch[op[i] - 'a'][x] = tot;
++i;
}
GetFail();
for(RG int i = 1; i <= m; ++i){
RG int x, y, ans = 0; scanf("%d%d", &x, &y);
for(RG int k = id[y]; k; k = fa[k])
for(RG int t = k; t; t = fail[t])
ans += (id[x] == t);
printf("%d
", ans);
}
return 0;
}
考虑换一种思路，构建出(fail)树，那么就是每次找(x)的子树中(y到trie的根)的字符的个数
把询问按(y)挂链，扫一遍(fail)树，处理出(x)的子树的(dfs)序的区间，开一个树状数组，重新来一边建(trie)的过程，每次('P')就树状数组区间查询；('B')就回撤，树状数组减去贡献；加的时候就加贡献
# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(1e5 + 10);
int m, ch[26][_], tot, fail[_], cnt, fa[_], dfn[_], ed[_], Index, bit[_], ans[_], id[_];
char op[_];
queue <int> Q;
vector <int> G[_], Qry[_], ID[_];
IL void Add(RG int x, RG int d){ for(; x <= Index; x += x & -x) bit[x] += d; }
IL int Query(RG int x){ RG int ret = 0; for(; x; x -= x & -x) ret += bit[x]; return ret; }
IL void GetFail(){
for(RG int i = 0; i < 26; ++i) if(ch[i][0]) Q.push(ch[i][0]);
while(!Q.empty()){
RG int fa = Q.front(); Q.pop();
for(RG int i = 0; i < 26; ++i)
if(ch[i][fa]) fail[ch[i][fa]] = ch[i][fail[fa]], Q.push(ch[i][fa]);
else ch[i][fa] = ch[i][fail[fa]];
G[fail[fa]].push_back(fa);
}
}
IL void Dfs(RG int u){
dfn[u] = ++Index;
for(RG int i = 0, l = G[u].size(); i < l; ++i) Dfs(G[u][i]);
ed[u] = Index;
}
int main(RG int argc, RG char* argv[]){
scanf(" %s%d", op, &m); RG int len = strlen(op);
for(RG int i = 0, x = 0; i < len; ++i)
if(op[i] == 'B') x = fa[x];
else if(op[i] == 'P') id[++cnt] = x;
else{
if(!ch[op[i] - 'a'][x]) ch[op[i] - 'a'][x] = ++tot;
fa[ch[op[i] - 'a'][x]] = x; x = ch[op[i] - 'a'][x];
}
GetFail(); Dfs(0);
for(RG int i = 1, x, y; i <= m; ++i) scanf("%d%d", &x, &y), Qry[y].push_back(x), ID[y].push_back(i);
for(RG int i = 0, x = 0, j = 0; i < len; ++i)
if(op[i] == 'P'){
++j;
for(RG int k = 0, l = Qry[j].size(); k < l; ++k)
ans[ID[j][k]] = Query(ed[id[Qry[j][k]]]) - Query(dfn[id[Qry[j][k]]] - 1);
}
else if(op[i] == 'B') Add(dfn[x], -1), x = fa[x];
else x = ch[op[i] - 'a'][x], Add(dfn[x], 1);
for(RG int i = 1; i <= m; ++i) printf("%d
", ans[i]);
return 0;
}