UOJ Logo chenliyan的博客

博客

可持久化后缀平衡树应用

2023-04-05 16:06:02 By chenliyan

当后缀平衡树用$treap$实现时,支持可持久化

具体应用……可以参考主席树的吧

例题

给定字符串$s$,求$[a,b]$中$t$的出现次数(多组询问)

sol

设$len$为$s$的长度,$len'$为$t$的长度

从后到前往后缀平衡树中插入后缀,每插入一个后缀,就存一个历史版本

令$ans[x]$为$[x,len]$中$t$出现次数,求$[x,len]$中$t$出现次数是容易的,只需调用插入第$x$个后缀的历史版本查询即可

若要求$[a,b]$中$t$ 出现次数,一个直观的想法是用$ans[a]-ans[b+1]$,但是这并不对,若$s$中的一个$t$子串恰好经过$b$点就可以把这种方法卡掉

于是我们就有了新的方法,用$ans[a]-ans[b-len'+2]$,这样就可以把恰好经过$b$点的情况给减掉

举个例子来说,假设$s=ababac$,$t=aba$,求$[0,3]$中$t$出现次数,就是$ans[0]-ans[3-3+2]=2-1=1$,显然是对的

时间复杂度$O(nlogn+Llogn)$,其中n为字符串$s$长度,$L$为查询字符串$t$的长度总和

chenliyan Avatar