正解:AC自动机+树状数组/线段树
解题报告:
这道题,首先想到暴力思路还是不难的,首先看到y有那么多个,菜鸡如我还不怎么会可持久化之类的,那就直接排个序什么的然后按顺序做就好,这样听说有70pts
然后思考一下,正解怎么做呢QAQ
回到AC自动机中关于fail指针的定义上来,因为fail指针指向的是最长后缀,这意味着,假如a指向b,那么a字符串中一定包含有root到b这一段字符串
于是假如我们要统计的字符串x,就只需要统计有多少个fail指针直接或间接指向x的ed那个点就是as辣
那不就是,建一棵fail树,求对于节点x的子树中有多少个节点是属于y的嘛
于是就考虑先dfs一下求出dfs序,然后这题就转化了鸭,就变成了这样:
有一个序列,支持向尾部加数和减数操作,每次只能操作一个数,然后还有一个询问操作,就是问[x,y]这个区间里有多少个数
那不就是线段树走一波就完事儿了嘛!
但是再仔细一想
这个询问操作其实还有一个性质
它的y一定是当前序列的最后一个数
那树状数组不就完事了嘛(主要树状数组比较好打+时空复杂度什么的比较好看,,,
然后就over辣!
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define il inline
#define rg register
#define lowbit(x) (x&(-x))
#define rp(i,x,y) for(rg ll i=x;i<=y;++i) const ll L=+,N=+;
ll cnt,tot,num,m,ed[L],dfn[L],low[L],edcnt,strlenth,tree[N],head[N],wdcnt,ans[N];
string str;
struct tre{ll to[],fil,fa;tre(){to[]=to[]=;fil=;}}tr[L];
struct qust{ll x,y,id;}as[N];
struct ed{ll to,nxt;}edge[L]; il ll read()
{
rg char ch=getchar();rg ll x=;rg bool y=;
while(ch!='-' && (ch>'' || ch<''))ch=getchar();
if(ch=='-')ch=getchar(),y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=getchar();
return y?x:-x;
}
il void bd()
{
cin>>str;strlenth=str.length();ll nw=;
rp(i,,strlenth)
{
if(str[i]>='a' && str[i]<='z'){if(!tr[nw].to[str[i]-'a'])tr[nw].to[str[i]-'a']=++cnt,tr[cnt].fa=nw;nw=tr[nw].to[str[i]-'a'];}
if(str[i]=='B')nw=tr[nw].fa;
if(str[i]=='P')ed[++tot]=nw;
}
}
il void ad(ll x,ll y){edge[++edcnt].to=y;edge[edcnt].nxt=head[x];head[x]=edcnt;}
il void fl()
{
queue<ll> Q;rp(i,,)if(tr[].to[i])Q.push(tr[].to[i]),ad(,tr[].to[i]);
while(!Q.empty())
{
ll nw=Q.front();Q.pop();
rp(i,,){if(tr[nw].to[i])tr[tr[nw].to[i]].fil=tr[tr[nw].fil].to[i],Q.push(tr[nw].to[i]),ad(tr[tr[nw].to[i]].fil,tr[nw].to[i]);else tr[nw].to[i]=tr[tr[nw].fil].to[i];}
}
}
il void dfs(ll x){/*printf("x=%d\n",x);*/dfn[x]=++num;for(rg ll i=head[x];i;i=edge[i].nxt)dfs(edge[i].to);low[x]=num;}
il bool cmp(qust gd,qust gs){return gd.y<gs.y;}
il void updat(ll x,ll y){while(x<N)tree[x]+=y,x+=lowbit(x);}
il ll query(ll x){ll as=;while(x)as+=tree[x],x-=lowbit(x);return as;}
il void solv()
{
ll nw=,nwnw=;
rp(i,,strlenth-)
{
// printf("QAQ? : ");cout<<str[i]<<endl;
if(str[i]>='a' && str[i]<='z')nwnw=tr[nwnw].to[str[i]-'a'],updat(dfn[nwnw],);
if(str[i]=='B')updat(dfn[nwnw],-),nwnw=tr[nwnw].fa;
if(str[i]=='P')
{
++wdcnt;
// printf("cnt=%d\n",wdcnt);
while(as[nw].y==wdcnt && nw<=m)
{
// printf("nw=%d\n",nw);
ll tmp=ed[as[nw].x];
ans[as[nw].id]=query(low[tmp])-query(dfn[tmp]-),++nw;
}
// if(nw>m)return;
}
}
return;
} int main()
{
bd();fl();dfs();m=read();rp(i,,m){as[i].x=read(),as[i].y=read(),as[i].id=i;/*if(as[i].y==1)printf("id=%d\n",i);*/}sort(as+,as++m,cmp);solv();
// rp(i,0,cnt)printf("dfn=%d low=%d\n",dfn[i],low[i]);
rp(i,,m)printf("%d\n",ans[i]);
return ;
}
/*
,,,我佛了我发现这题太复杂了
我来理下思路
首先确定一下各个变量的作用,,,
const ll L=100000+500,N=100000+100;
常数变量,L是字母个数,N是询问个数
ll cnt,tot,num,m,ed[L],dfn[L],low[L],edcnt,strlenth,tree[N],head[N],wdcnt,ans[N];
cnt,建AC自动机的时候用
tot,存ed的时候用
num，存dfn序的时候用
ed[],存询问的节点编号
dfn[],存dfs序,即题解中[x,y]的x
low[],同上,即y
edcnt,连边的时候用
strlenth,存str的长度
tree[],树状数组
head[],链式前向星一部分
wdcnt,存做到哪个单词了
ans[],存答案
string str;
读入的那个字符串
struct tre{ll to[30],fil,fa;tre(){to[0]=to[1]=0;fil=0;}}tr[L];
trie树 to和fil不说,fa是为了Back操作
struct qust{ll x,y,id,ass;}as[N];
存询问,方便排序和再排
struct ed{ll to,nxt;}edge[L];
存边
然后明确一下工作
bd();
读入字符串,建trie树:main函数中操作
ad();
连边,fail指向节点:fl中操作
fl();
建fail指针:main函数中操作
dfs();
记dfs序:main函数中操作
cmp();
排序,保证疑问y递增:main函数sort中操作
updat();
树状数组+-操作:solv中操作
query();
树状数组求值操作:solv中操作
solv();
求ans:main函数中操作
欧克克我jio得现在思路海星了大概是细节有点儿问题下午搞QAQ
*/
总算过辣呜呜呜