**~~表示看不懂~~**
by 花满楼_落枫 @ 2019-01-20 18:14:54
@[61314w](/space/show?uid=116608)
###### 没事，我已经调了两个半小时了，前一秒终于调出来了，变量名重复了
by Froggy @ 2019-01-20 18:24:05
这是我AC的代码：
```cpp
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstdio>
using namespace std;
#define N 100010
string a;
queue<int> q;
int n,cnt=0,tot=0,num=0,len,tt=0,ttot=0;
int head[N],dfn[N],size[N],ans[N],here[N];
struct node{
int ch[26],nxt;
int fa;
}tree[N<<2];
struct Ask{
int x,y,index;
}ask[N];
struct Edge{
int to,nxt;
}edge[N];
struct Xian_duan_shu{
int val,l,r;
}s[N<<2];
void build_tree(int i,int l,int r){
s[i].l=l;
s[i].r=r;
if(l==r){
s[i].val=0;
return;
}
int mid=(l+r)>>1;
build_tree(i*2,l,mid);
build_tree(i*2+1,mid+1,r);
}
void add(int a,int b){
cnt++;
edge[cnt].to=b;
edge[cnt].nxt=head[a];
head[a]=cnt;
}
bool comp(Ask a,Ask b){
return a.y<b.y;
}
void insert(){
int u=0;
for(int i=0;i<len;i++){
if(a[i]=='B'){
u=tree[u].fa;
}
else if(a[i]=='P'){
here[++tt]=u;
}
else{
int c=a[i]-'a';
if(!tree[u].ch[c]){
tree[u].ch[c]=++tot;
tree[tot].fa=u;
}
u=tree[u].ch[c];
}
}
}
void bfs(){
for(int i=0;i<26;i++){
int v=tree[0].ch[i];
if(v){
tree[v].nxt=0;
q.push(v);
}
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<26;i++){
int v=tree[u].ch[i];
if(v){
tree[v].nxt=tree[tree[u].nxt].ch[i];
q.push(v);
}
else tree[u].ch[i]=tree[tree[u].nxt].ch[i];
}
}
}
void dfs(int u){
dfn[u]=++ttot;size[u]=1;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(u==v)continue;
dfs(v);
size[u]+=size[v];
}
}
int to_ans(int i,int l,int r){//子树求和
if(s[i].l==l&&s[i].r==r){
return s[i].val;
}
int mid=(s[i].l+s[i].r)>>1;
if(r<=mid) return to_ans(i*2,l,r);
if(l>mid) return to_ans(i*2+1,l,r);
return to_ans(i*2,l,mid)+to_ans(i*2+1,mid+1,r);
}
void _plus(int i,int x,int dis){
if(s[i].l==s[i].r){
s[i].val+=dis;
return;
}
int mid=(s[i].l+s[i].r)>>1;
if(x<=mid)_plus(i*2,x,dis);
else _plus(i*2+1,x,dis);
s[i].val=s[i*2].val+s[i*2+1].val;
}
void get_ans(){
int point=1,tot1=0;
int u=0;
for(int i=0;i<len;i++){
if(a[i]=='P'){
tot1++;
while(ask[point].y==tot1){
int x1=ask[point].x;
ans[ask[point].index]=to_ans(1,dfn[here[x1]],dfn[here[x1]]+size[here[x1]]-1);
point++;
}
}
else if(a[i]=='B'){
_plus(1,dfn[u],-1);
u=tree[u].fa;
}
else{
int c=a[i]-'a';
u=tree[u].ch[c];
_plus(1,dfn[u],1);
}
}
}
int main(){
cin>>a;
len=a.length();
insert();
cin>>n;
for(int i=1;i<=n;i++){
cin>>ask[i].x>>ask[i].y;
ask[i].index=i;
}
sort(ask+1,ask+n+1,comp);
bfs();
for(int i=0;i<=tot;i++){
add(tree[i].nxt,i);
}
dfs(0);
build_tree(1,1,ttot);
get_ans();
for(int i=1;i<=n;i++){
cout<<ans[i]<<endl;
}
return 0;
}
```
by Froggy @ 2019-01-20 18:24:40
楼主放出来代码不怕有人抄袭吗
by jc2018 @ 2019-01-20 18:28:13
@[Froggy](/space/show?uid=100285)
by jc2018 @ 2019-01-20 18:28:28
@[61314w](/space/show?uid=116608) 表示今天刚学，但内容还没全懂，用代码去实现更别提了
本蒟蒻才刚学会最小生成树~~我才不会告诉你我是照着老师的代码敲出来的~~
不过并查集我真是会写了，最小生成树也差不多会写了
by qwertylzx·破祥 @ 2019-01-20 18:28:59
@[jc2018](/space/show?uid=100699)
# 不怕
##### ~~因为我就是抄的~~（不过不是Ctrl+C，Ctrl+V，代码还是我自己写的）
by Froggy @ 2019-01-20 18:33:30
@[Froggy](/space/show?uid=100285) dalao太巨了
by wxw25 @ 2019-01-20 18:46:15
@[Froggy](/user/100285) dalao太巨了才调了两个半小时
我已经调了三个半小时了
by zhoukangyang @ 2020-08-12 20:07:44
好吧, 我犯了一个sb错误
by zhoukangyang @ 2020-08-12 20:17:40