注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2434][Noi2011]阿狸的打字机  

2015-05-14 15:14:17|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2434: [Noi2011]阿狸的打字机

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 1386  Solved: 801
[Submit][Status][Discuss]

Description

 阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字机上只有28个按键,分别印有26个小写英文字母和'B'、'P'两个字母。
经阿狸研究发现,这个打字机是这样工作的:
l 输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
l 按一下印有'B'的按键,打字机凹槽中最后一个字母会消失。
l 按一下印有'P'的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消失。
例如,阿狸输入aPaPBbP,纸上被打印的字符如下:
a
aa
ab
我们把纸上打印出来的字符串从1开始顺序编号,一直到n。打字机有一个非常有趣的功能,在打字机中暗藏一个带数字的小键盘,在小键盘上输入两个数(x,y)(其中1≤x,y≤n),打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。
阿狸发现了这个功能以后很兴奋,他想写个程序完成同样的功能,你能帮助他么?

Input

 输入的第一行包含一个字符串,按阿狸的输入顺序给出所有阿狸输入的字符。
第二行包含一个整数m,表示询问个数。
接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y,表示第i个询问为(x, y)。

Output

 输出m行,其中第i行包含一个整数,表示第i个询问的答案。

Sample Input

aPaPBbP 3 1 2 1 3 2 3

Sample Output

2 1 0

HINT

 1<=N<=10^5

1<=M<=10^5
输入总长<=10^5

Solution

首先按照题目的意思建一个AC自动机
“第x个打印的字符串在第y个打印的字符串中出现了多少次”在AC自动机上的问题可以转换为将y串所有节点沿fail树打上标记,问danger(x)的点权,也就是说在danger(x)的子树中有多少节点在y串上面。
树状数组+打标记。注意到用题目中给的串可以做到线性时间访问,于是整个时间效率就是O(nlogn)

Code

/**************************************************************
    Problem: 2434
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:492 ms
    Memory:16924 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
#define N 100010
struct A{int x,y,n;}a[N];
bool operator<(const A&i,const A&j){return i.x<j.x;}
char s[N],c;int m,et,la[N],n,pos[N],las,tot,fa[N],ch[N][26],fail[N],i,j,L[N],R[N],z[N],ans[N],q[N],cnt;
void add(int t){for(;t<=cnt;t+=t&-t)z[t]++;}
void dec(int t){for(;t<=cnt;t+=t&-t)z[t]--;}
int gs(int t){int f=0;for(;t;t-=t&-t)f+=z[t];return f;}
struct E{int to,nxt;}e[N];
#define adde(x,y) (e[++et]=(E){y,la[x]},la[x]=et)
void build_AC(){int l=1,r=0,i,j;
    for(i=0;i<26;i++)if(ch[0][i])q[++r]=ch[0][i],adde(0,ch[0][i]);
    for(;l<=r;l++)
    for(i=0;i<26;i++)
    if(j=ch[q[l]][i]){
        if(q[l])fail[j]=ch[fail[q[l]]][i],adde(fail[j],j);
        q[++r]=j;
    }
    else ch[q[l]][i]=ch[fail[q[l]]][i];
}
void dfs(int x){
    for(L[x]=++cnt;la[x];la[x]=e[la[x]].nxt)dfs(e[la[x]].to);R[x]=cnt;
}
int main(){
    for(scanf("%s",s+1),i=1;s[i];i++)
    if(s[i]>='a'&&s[i]<='z'){
        if(c=s[i]-'a',!ch[las][c])ch[las][c]=++tot,fa[tot]=las;
        las=ch[las][c];
    }
    else if(s[i]=='P')pos[++n]=las;
    else las=fa[las];
    build_AC();dfs(0);
    for(scanf("%d",&m),i=1;i<=m;i++)scanf("%d%d",&a[i].y,&a[i].x),a[i].n=i;
    for(std::sort(a+1,a+1+m),las=n=0,i=j=1;s[i];i++)
    if(s[i]>='a'&&s[i]<='z')add(L[las=ch[las][s[i]-'a']]);
    else if(s[i]=='P'){
        for(n++;j<=m&&a[j].x==n;j++)
        ans[a[j].n]=gs(R[pos[a[j].y]])-gs(L[pos[a[j].y]]-1);
    }
    else dec(L[las]),las=fa[las];
    for(i=1;i<=m;i++)printf("%d\n",ans[i]);
}
  评论这张
 
阅读(26)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018