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

n+e

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

 
 
 

日志

 
 

[BZOJ3881][Coci2015]Divljak  

2015-05-01 20:35:23|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3881: [Coci2015]Divljak

Time Limit: 10 Sec  Memory Limit: 768 MB
Submit: 246  Solved: 60
[Submit][Status][Discuss]

Description

Alice有n个字符串S_1,S_2...S_n,Bob有一个字符串集合T,一开始集合是空的。
接下来会发生q个操作,操作有两种形式:
“1 P”,Bob往自己的集合里添加了一个字符串P。
“2 x”,Alice询问Bob,集合T中有多少个字符串包含串S_x。(我们称串A包含串B,当且仅当B是A的子串)
Bob遇到了困难,需要你的帮助。

Input

第1行,一个数n;
接下来n行,每行一个字符串表示S_i;
下一行,一个数q;
接下来q行,每行一个操作,格式见题目描述。

Output

对于每一个Alice的询问,帮Bob输出答案。

Sample Input

3 a bc abc 5 1 abca 2 1 1 bca 2 2 2 3

Sample Output

1 2 1

HINT

【数据范围】
1 <= n,q <= 100000;
Alice和Bob拥有的字符串长度之和各自都不会超过 2000000;
字符串都由小写英文字母组成。

Source

Solution

听说是2015论文题。。。
对于Alice的串先插到AC自动机里面,然后用Bob的串来贡献答案。
考虑什么时候贡献了答案,一个串P能贡献给Sx答案 当且仅当Bob的P串能(沿匹配边或fail边)走到Alice的Sx串终止位置。
所以有一种暴力的做法是,对于新加进来的某个节点,我们暴力沿着这个节点跳fail,如果没更新就更新一下,这样做的复杂度应该可以卡到平方级别。
考虑优化暴力。我上网搜了一下都是一些树链求并的题解,求LCA,dfs序,树状数组,然后T了2333真是喜闻乐见好像论文里就是这种写法。。。
然后Orz了kfdong,发现LCT可以直接上!整个人都惊呆了
我的access代码大概长这样:
void access(int t,int las=0){
    for(;t;splay(t),son[t][1]=las,las=t,t=fa[t]);
}
LCT求LCA:假设求lca(x,y),那么access(x),access(y),做完y以后的las就是LCA。
对于这道题而言,我们求出fail树,然后在上面维护两个标记,一个是时间戳,另一个是增量。
不是要把树链并起来吗?还是用access,只不过多访问一次时间戳。如果节点t之前的点已经在这一个时间段更新过了,那么就停止access,然后打标记。
然后写一下交一发,发现跑了8s+(我机子慢一个测试点开了O2要跑24s+。。。。真是一个悲伤的故事)
还有什么地方可以优化的呢?
再次Orz了AKF的代码以后,发现他有一个优化,缩点!将不是danger标记的节点统统删掉,这样的话点集规模直接变成了n,然后剩下的该怎么做就怎么做,一下子跑进了4s
试了试IO,好像数据有问题还是自己写龊了会RE。于是就扔在一边不管了。。。

Code

/**************************************************************
    Problem: 3881
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:3496 ms
    Memory:242856 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
#define N 1620000
int n,m,i,j,fail[N],ch[N][26],tot,las,end[N],q[N],danger[N],id[N];char s[N];
int fa[N],son[N][2],add[N],cnt[N],tim[N],vis[N],tc;
#define ls son[t][0]
#define rs son[t][1]
#define nr(t) (son[fa[t]][0]==t||son[fa[t]][1]==t)
void pd(int t){if(!t)return;
    if(add[t]){
        add[ls]+=add[t],add[rs]+=add[t];
        cnt[ls]+=add[t],cnt[rs]+=add[t];add[t]=0;
    }
    if(tim[ls]<tim[t]||vis[ls]<tim[t])vis[ls]=tim[ls]=tim[t];
    if(tim[rs]<tim[t]||vis[rs]<tim[t])vis[rs]=tim[rs]=tim[t];
}
void rtt(int t){
    int f=fa[t],p=son[f][1]==t;
    fa[t]=fa[f],nr(f)?son[fa[f]][son[fa[f]][1]==f]=t:1;
    (son[f][p]=son[t][p^1])?fa[son[f][p]]=f:1,son[fa[f]=t][p^1]=f;
}
void pv(int t){if(nr(t))pv(fa[t]);pd(t);}
void splay(int t){int f;
    for(pv(t);nr(t);rtt(t))
    if(f=fa[t],nr(f))rtt(son[f][1]==t^son[fa[f]][1]==f?t:f);
}
void access(int t){int las=0;
    for(;t&&(splay(t),vis[t]<tc);rs=las,las=t,t=fa[t]);
    if(las&&vis[las]<tc)tim[las]=vis[las]=tc,add[las]++,cnt[las]++,splay(las);
}
void build_AC(){
    int l,r,i,j,cnt=1;
    for(q[l=r=0]=0;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];
        q[++r]=j;
    }
    else ch[q[l]][i]=ch[fail[q[l]]][i];
    for(id[0]=i=1;i<=r;i++)
    if(danger[q[i]]){
        id[q[i]]=++cnt;
        fa[cnt]=id[fail[q[i]]];
    }
    else id[q[i]]=id[fail[q[i]]];
}
int main(){
    scanf("%d\n",&n);
    for(i=1;i<=n;i++){
        scanf("%s",s);
        for(las=j=0;s[j];j++){
            s[j]-='a';
            if(!ch[las][s[j]])ch[las][s[j]]=++tot;
            las=ch[las][s[j]];
        }
        end[i]=las;danger[las]=1;
    }
    build_AC();
    for(scanf("%d",&m);m--;){
        scanf("%s",s);
        if(s[0]=='1'){
            scanf("%s",s);tc++;
            for(las=i=0;s[i];i++){
                las=ch[las][s[i]-'a'];
                access(id[las]);
            }
        }
        else{
            scanf("%d",&i);i=id[end[i]];
            pv(i);printf("%d\n",cnt[i]);
        }
    }
}

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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