文档章节

BZOJ5084[hashit]

o
 osc_1ee7cxmx
发布于 2018/08/06 16:58
字数 725
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题解:

后缀自动机

我们可以通过建立trie

把询问变成询问一些点的并

把trie建立成SAM和广义SAM基本相同,就是在父亲和儿子之间连边

然后就变成了询问树链的并

我们可以发现答案=sigma dis[i]  -sigma(dis[lca(i,i+1)])

其中i和i+1dfs序相邻

可以通过set来维护

***

把倍增的预处理写在了dfs前

把&&写成了&

代码:

 

#include <bits/stdc++.h>
#define rint register int
#define IL inline
#define rep(i,h,t) for (rint i=h;i<=t;i++)
#define dep(i,t,h) for (rint i=t;i>=h;i--)
#define ll long long
using namespace std;
const int N=2e5;
char s[N];
int len,cnt,son[N][26],pos[N],cnt2;
struct hz{
  int ch[N][26],node,len[N],fa[N];
  hz()
  {
    node=1; 
  }
  int extend(int c,int z)
  {
  int lst=z;
  int f=lst;
  if (ch[f][c]&&len[ch[f][c]]==len[f]+1)
  { 
    lst=ch[f][c];
    return(lst);
  }
  int p=++node; lst=p;
  len[p]=len[f]+1; //size[p][pl]=1;
  while (f&&!ch[f][c]) ch[f][c]=p,f=fa[f];
  if (!f) { fa[p]=1; return(p);};
  int x=ch[f][c],y=++node;
  if (len[f]+1==len[x]) {fa[p]=x; node--;return(p);}
  len[y]=len[f]+1; fa[y]=fa[x]; fa[x]=fa[p]=y;
  memcpy(ch[y],ch[x],sizeof(ch[x]));
  while (f&&ch[f][c]==x) ch[f][c]=y,f=fa[f];
  return(p);
  }
  void build(int x)
  {
    rep(i,0,25)
      if (son[x][i])
      {
        pos[son[x][i]]=extend(i,pos[x]);
        build(son[x][i]);
      }
  }
}S;
int l,head[N],bz[N][21],dfn[N],rl[N],dis[N],fa[N],dep[N],zt[N];
struct re{
  int a,b;
}a[N];
void arr(int x,int y)
{
  a[++l].a=head[x];
  a[l].b=y;
  head[x]=l;
}
void dfs(int x,int y)
{
  int u=head[x]; bz[x][0]=y; dfn[x]=++cnt2; rl[cnt2]=x;
  dep[x]=dep[y]+1; 
  dis[x]=dis[y]+S.len[x]-S.len[y];
  while (u)
  {
    int v=a[u].b;
    dfs(v,x);
    u=a[u].a;
  }
}
set<int> M;
set<int>::iterator it;
int lca(int x,int y)
{
  if (dep[x]<dep[y]) swap(x,y);
  dep(i,20,0)
    if (dep[bz[x][i]]>=dep[y]) x=bz[x][i];
  if (x==y) return(x);
  dep(i,20,0)
    if (bz[x][i]!=bz[y][i]) x=bz[x][i],y=bz[y][i];
  return(bz[x][0]); 
}
int main()
{
  freopen("1.in","r",stdin);
  freopen("3.out","w",stdout);
  scanf("%s",s);
  len=strlen(s);
  int now=1;
  cnt=1;
  rep(i,0,len-1)
  {
    if (s[i]=='-') now=fa[now];
    else
    {
      if (!son[now][s[i]-'a']) son[now][s[i]-'a']=++cnt,fa[cnt]=now;
      now=son[now][s[i]-'a'];
    }
  }
  pos[1]=1; S.build(1);
  for(int i=2;i<=S.node;i++) arr(S.fa[i],i);
  dfs(1,0);
    rep(i,1,20)
    rep(j,1,S.node) bz[j][i]=bz[bz[j][i-1]][i-1];
  ll ans=0; now=1;
 int cnt3=0;
  rep(i,0,len-1)
  {
    if (s[i]=='-')
    {
      int x=0,y=0;
      ans-=dis[now];
      it=M.find(dfn[now]); it++;
      if (it!=M.end()) x=rl[*it]; it--;
      if (it!=M.begin()) y=rl[*--it];
      M.erase(dfn[now]);
      if (x) ans+=dis[lca(now,x)];
      if (y) ans+=dis[lca(now,y)];
      if (x&&y) ans-=dis[lca(x,y)];
      now=zt[--cnt3];
    } else
    {
      int x=0,y=0;
      now=S.ch[now][s[i]-'a'];
      zt[++cnt3]=now;
      ans+=dis[now];
      it=M.insert(dfn[now]).first; 
      it++;
      if (it!=M.end()) x=rl[*it]; it--; 
      if (it!=M.begin())
      { 
        y=rl[*--it];
      }
      if (x) ans-=dis[lca(now,x)];
      if (y) ans-=dis[lca(now,y)];
      if (x&&y) ans+=dis[lca(x,y)];
   //   cout<<lca(pos[now],x)<<" "<<lca(pos[now],y)<<" "<<x<<" "<<y<<endl; 
    }
    printf("%lld\n",ans);
  }
  return 0;
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

会议通知 | 2020中国计算与认知神经科学会议

关于大会关于 计算神经科学以神经生物实验为基础,以建立数学模型,开展计算模拟和分析作为基本手段,来刻画和描述大脑的神经活动,探究神经系统各种复杂活动和认知功能包括注意、学习、记忆...

脑机接口社区
06/02
20
0
大神分享快3怎么算下期和值

大神分享快3怎么算下期和值{叩67790572}使用的标签:constructor-arg标签出现的位置:bean标签的内部标签中的属性type:用于指定要注入的数据的数据类型,该数据类型也是构造函数中某个...

yiren081
31分钟前
21
0
Matlab系列之运算符和标点符号的功能介绍

本来月初就打算接着写的,但是电脑不小心进水,主板什么的都废了,周末才找时间拿去修好,心塞。 就不多讲太多废话了,开始分享今天的内容,对MATLAB的运算符做个介绍,然后再对标点符号进行...

狂人V
07/06
18
0
Java源码系列(1):Comparable和Comparator的区别

在讲Comparable和Comparator区别之前,先补充一个知识点。 先看代码: Person类 1public class Person<T> { 2  private T id; 3 4  public T getId() { 5    return i...

学习Java的小姐姐
2018/09/19
25
0
ThreadPoolTaskScheduler手写调度中心

先贴一个自己写的demo把,原理其实就是这样的。 CronTrigger这个类可以将cron表达式转换成Date,可以查看schedule源码学到不少东西,下面代码就是转换成下一执行时间。 public Date nextEx...

朝如青丝暮成雪
53分钟前
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部