﻿ P2414 [NOI2011]阿狸的打字机

## 题目

P2414 [NOI2011]阿狸的打字机

## 做法

(parents)树欧拉序找区间，每个查询((x,y))(x)丢到(y)节点去

## My complete code

``````#include<cstring>
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
const LL maxn=1e5+9;
LL x(0),f(1); char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1; c=getchar();
}
while(c>='0'&&c<='9')
x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*f;
}

LL T,nod=0;
LL son[maxn][26],tmp[maxn][26],ans[maxn],fail[maxn],fa[maxn],nd[maxn];
struct Qy{
LL x,y,id;
}q[maxn];
inline bool cmp(Qy x,Qy y){
return x.y<y.y;
}
inline void Get_fail(){
queue<LL> que;
for(LL i=0;i<26;++i)
if(tmp[0][i])
que.push(tmp[0][i]);
while(que.size()){
LL u=que.front(); que.pop();
for(LL i=0;i<26;++i){
LL v=tmp[u][i];
if(v)
fail[v]=tmp[fail[u]][i],
que.push(v);
else
tmp[u][i]=tmp[fail[u]][i];
}
}
}

struct node{
LL to,next;
}dis[maxn];
}
void Xu(LL u){
dfn[u]=++tot;
Xu(dis[i].to);
low[u]=tot;
}

struct Tree{
LL x,id;
};
LL sum[maxn];
vector<Tree> belong[maxn];
inline LL Lowbit(LL x){
return x&(-x);
}
inline void Modify(LL i,LL val){
for(;i<=nod+1;i+=Lowbit(i))
sum[i]+=val;
}
inline LL Query(LL i){
LL ret(0);
for(;i;i-=Lowbit(i))
ret+=sum[i];
return ret;
}
void Dfs(LL u){
Modify(dfn[u],1);
for(LL i=0;i<belong[u].size();++i)
ans[belong[u][i].id]=Query(low[nd[belong[u][i].x]])-Query(dfn[nd[belong[u][i].x]]-1);
for(LL i=0;i<26;++i)
if(son[u][i])
Dfs(son[u][i]);
Modify(dfn[u],-1);
}
char s[maxn];
int main(){
scanf(" %s",s+1);
for(LL i=1,Len=strlen(s+1),now=0,cnt=0;i<=Len;++i){
char c=s[i];
if(c>='a'&&c<='z'){
c-='a';
if(!son[now][c])
tmp[now][c]=son[now][c]=++nod,
fa[nod]=now;
now=son[now][c];
}else if(c=='B')
now=fa[now];
else
nd[++cnt]=now;
}
Get_fail();
for(LL i=1;i<=nod;++i)
Xu(0);
for(LL i=1;i<=T;++i){
q[i]=(Qy){x,y,i};
}
sort(q+1,q+1+T,cmp);
for(LL i=1,pos=1;i<=T;i=pos){
while(q[i].y==q[pos].y)
belong[nd[q[pos].y]].push_back((Tree){q[pos].x,q[pos].id}),
++pos;
}
Dfs(0);
for(LL i=1;i<=T;++i)
printf("%lld
",ans[i]);
return 0;
}/*
aaaPBPBPaP
1
3 2
*/
``````