【BZOJ2434】阿狸的打字机（fail树，DFS序）

题意：

1<=N<=10^5

1<=M<=10^5

输入总长<=10^5

思路：

From http://blog.csdn.net/lych_cys/article/details/50646799

首先你会发现他打字的方式非常奇妙。。实际上不就是在构建一颗Tire吗？P相当于给节点标记；B相当于退回父亲节点；a..z相当于建立新的节点。

然后跑AC自动机得到fail指针。

首先得知道如何得出单个操作x,y。在后缀数组（sam，后缀树等）中，判断u是v的子串的方法是看是否是每一个后缀的前缀；而AC自动机则架构在前缀树Tire上，自然地，判断AC自动机上面的两个子串u,v（AC自动机上的子串x可以看成是从根节点到节点x连成的一个字符串），u是否是v的子串，就等价于u是否是v某个前缀的后缀！在AC自动机上，判断u是x的后缀非常简单，只要看x能否沿着fail指针走到u即可。

那么，查询u在v中出现了几次就比较明了了，只要看从根节点到v的路径中有多少个x，满足u是x的后缀即x能沿着fail指针走到u。

于是，我们可以将fail[x]作为x（这里的x不同于上面的x）的父节点建立一颗新的树，这样的话如果i是j的祖先，那么j显然可以由fail指针走到i。那么查询u,v时，将root->v的路径上的每一个点都变为1，那么答案就相当于u的子树中有多少个1了。

但是这样直接在线查询显然不行（除非写一些高大上的数据结构）。单点修改子树查询可以用dfs序+树状数组解决，因此关键是减少修改次数。我们可以离线，以v为关键字排序，这样就可以根据原来建立AC自动机的顺序进行修改了，只要在进入一个点t时+1，出去时-1，查询时自然root->v的路径上的每一个点都是1了。

var map:array[..,..]of longint;

    f,fa,ind,oud,q,t,x,y,id,head,vet,next,ans,num:array[..]of longint;

    n,m,i,cnt,now,tot,j,k,len,time,u,que,tmp:longint;

    ch:ansistring;

procedure acauto;

var t,w,u,p,i,son:longint;

begin

 t:=; w:=; q[]:=;

 while t<w do

 begin

  inc(t); u:=q[t];

  for i:= to  do

   if map[u,i]> then

   begin

    son:=map[u,i];

    p:=f[u];

    if u= then f[son]:=

     else f[son]:=map[p,i];

    inc(w); q[w]:=son;

   end

    else

    begin

     p:=f[u];

     if u= then map[u,i]:=

      else map[u,i]:=map[p,i];

    end;

 end;

end;

procedure add(a,b:longint);

begin

 inc(tot);

 next[tot]:=head[a];

 vet[tot]:=b;

 head[a]:=tot;

end;

procedure dfs(u:longint);

var e,v:longint;

begin

 inc(time); ind[u]:=time; oud[u]:=time;

 e:=head[u];

 while e<> do

 begin

  v:=vet[e];

  if ind[v]= then

  begin

   dfs(v);

   oud[u]:=oud[v];

  end;

  e:=next[e];

 end;

end;

procedure swap(var x,y:longint);

var t:longint;

begin

 t:=x; x:=y; y:=t;

end;

procedure qsort(l,r:longint);

var i,j,t,mid:longint;

begin

 i:=l; j:=r; mid:=y[(l+r)>>];

 repeat

  while mid>y[i] do inc(i);

  while mid<y[j] do dec(j);

  if i<=j then

  begin

   swap(x[i],x[j]);

   swap(y[i],y[j]);

   swap(id[i],id[j]);

   inc(i); dec(j);

  end;

 until i>j;

 if l<j then qsort(l,j);

 if i<r then qsort(i,r);

end;

function lowbit(x:longint):longint;

begin

 exit(x and (-x));

end;

procedure ins(x,y:longint);

begin

 while x<=time do

 begin

  t[x]:=t[x]+y;

  x:=x+lowbit(x);

 end;

end;

function query(x:longint):longint;

begin

 query:=;

 while x> do

 begin

  query:=query+t[x];

  x:=x-lowbit(x);

 end;

end;

begin

 assign(input,'bzoj2434.in'); reset(input);

 assign(output,'bzoj2434.out'); rewrite(output);

 readln(ch);

 m:=length(ch); len:=; cnt:=; now:=;

 for i:= to m do

 begin

  case ch[i] of

   'P':

   begin

    inc(n); num[n]:=now;

    continue;

   end;

   'B':

   begin

    now:=fa[now];

    continue;

   end;

  end;

  u:=ord(ch[i])-ord('a')+;

  if map[now,u]= then

  begin

   inc(cnt); map[now,u]:=cnt;

   fa[cnt]:=now;

  end;

  now:=map[now,u];

 end;

 acauto;

 for i:= to cnt do add(f[i],i);

 dfs();

 readln(que);

 for i:= to que do

 begin

  read(x[i],y[i]);

  id[i]:=i;

 end;

 qsort(,que);

 j:=; k:=; now:=;

 for i:= to m do

 begin

  case ch[i] of

   'B':

   begin

    ins(ind[now],-); now:=fa[now];

    continue;

   end;

   'P':

   begin

    inc(j);

    while (k<=que)and(y[k]=j) do

    begin

     tmp:=num[x[k]];

     ans[id[k]]:=query(oud[tmp])-query(ind[tmp]-);

     inc(k);

    end;

    continue;

   end;

  end;

  now:=map[now,ord(ch[i])-ord('a')+];

  ins(ind[now],);

 end;

 for i:= to que do writeln(ans[i]);

 close(input);

 close(output);

end.

巴特西

【BZOJ2434】阿狸的打字机（fail树，DFS序）

最新文章

热门文章