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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

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

2014-11-23 16:16:36|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2434: [Noi2011]阿狸的打字机

感觉在HDU上不管做啥题都永远过不了……
写了个题拍了10w次都没错交上去WA..
于是还是回来战BZOJ
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 1E5+10;
int n,m,T;
int list[N*2],bhn,ans[N],top;
char str[N];
int scan(){int i=0;scanf("%d",&i);return i;}
struct ASK{int a,b,i;}qs[N];
bool operator < (ASK a, ASK b){return a.b==b.b?a.a<b.a:a.b<b.b;}
struct Node{
Node(){last = fail = 0;memset(ch,0,sizeof(ch));}
int end;
Node *last,*fa,*ch[26],*fail;
}house[N],*bh[N];int hn;
Node *newNode(){
if(hn < N){return &house[hn++];}
return new Node;
}
struct Point{
Point(){next =NULL;}
Point *next;int d;
void push(int a){
Point *l = new Point;
l->next = next;next =l ;
l->d =a;
}
}point[N];
int tree[N*2],pos[N][2];
void add(int x,int val){for(;x<=list[0]+1;x+=x&-x)tree[x]+=val;}
int get(int x){int re=0;for(;x;x-=x&-x)re+=tree[x];return re;}
queue<Node*>dui;
struct AC{
Node *ROOT;
AC(){ROOT=newNode();ROOT->fail=ROOT->last=ROOT;ROOT->end=++T;}
void build(){
Node *r = ROOT;
int len = strlen(str);
for(int i=0;i<len;i++)
if(str[i]>='a'){
int c = str[i]-'a';
if(!r->ch[c]){r->ch[c]=newNode();r->ch[c]->fa=r;}
r = r->ch[c];
}else{
if(str[i] == 'P'){
if(!r->end)r->end = ++T;
bh[++bhn] = r;
}else{
r = r->fa;
}
}
}
void makefail(){
for(int i=0;i<26;i++)
if(ROOT->ch[i]){
ROOT->ch[i]->fail = ROOT->ch[i]->last = ROOT;
dui.push(ROOT->ch[i]);
}else ROOT->ch[i] = ROOT;
while(!dui.empty()){
Node *r = dui.front();dui.pop();
if(r->end) point[r->last->end].push(r->end);
for(int i=0;i<26;i++)
if(r->ch[i]){
Node *l = r->fail;
while(l->ch[i]==ROOT&&l!=ROOT)l = l->fail;
r->ch[i]->fail = l->ch[i];
r->ch[i]->last = l->ch[i]->end?l->ch[i]:l->ch[i]->last;
dui.push(r->ch[i]);
}else r->ch[i] = r->fail->ch[i];
}
}
void solve(){
Node *r = ROOT;bhn=0;
int len = strlen(str),c;
for(int i=0;i<len;i++)
if(str[i]>='a'){
c = str[i]-'a';
r = r->ch[c];
//add
if(!(c=r->end))c=r->last->end;
if(c>1) add(pos[c][0],1);
}else{
if(str[i] == 'P'){
++bhn;
//deal
while(qs[top].b==bhn){
c = bh[qs[top].a]->end;
ans[qs[top].i]=get(pos[c][1])-get(pos[c][0]-1);
top++;
}
}else{
//clear
if(!(c=r->end))c=r->last->end;
if(c>1) add(pos[c][0],-1);
r = r->fa;
}
}
}
}ac;
void dfs(int x = 1){
list[++list[0]] = x;
pos[x][0] = list[0];
for(Point *i = point[x].next;i!=NULL;i=i->next)
dfs(i->d);
list[++list[0]] = x;
pos[x][1] = list[0];
}
int ask(int a,int b){
if(bh[a]==bh[b])return 1;
int re=0;
a = bh[a]->end;
add(pos[a][0],1);
add(pos[a][1]+1,-1);
Node *r = bh[b];
while(r!=ac.ROOT){
if(r->end) re += get(pos[r->end][0]);
else re += get(pos[r->last->end][0]);
r = r->fa;
}
add(pos[a][0],-1);
add(pos[a][1]+1,1);
return re;
}
int main(){
//freopen("in.txt","r",stdin);
int i,j,a,b;
scanf("%s",str);
ac.build();
ac.makefail();
dfs();
m = scan();
for(i=1;i<=m;i++){
qs[i].a=scan();
qs[i].b=scan();
qs[i].i=i;
}
sort(qs+1,qs+1+m);
top=1;
ac.solve();
for(i=1;i<=m;i++)
printf("%d\n",ans[i]);
return 0;
}

题解:
传说中的AC自动机Fail树
对于trie树上表示某个串的一条链,所有节点向fail边走到根经过的所有末尾节点就相当于这个串的所有子串。
一开始我写的时候没经过大脑……采取的是比较暴力的方法,对于每个询问(a,b)先把a在fail树上的子树权值+1,然后扫一遍b串,对于它的每一个子串在树里查询权值,和就是本次询问的答案。
然后就T了……注意这个题说的输入≤1e5是指的给出的操作串长度,而不是所包含字符串的总长。
也就是说字符串总长可能达到接近1e(5+2)这么一个级别
那么接下来只剩下一条路可走:离线
但是感觉离线了之后还是没法搞……对于原来的方法一个串最多有LEN个位置需要查询。
反过来想,这次改成把查询的地方改成在树上的点修改,原来的修改变成现在的子树查询,按照操作串的顺序遍历一遍trie,每遇到一个P操作就处理一下符合的询问。

  评论这张
 
阅读(460)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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