傳送門

（bzoj上不去我也很無奈啊）

題意：維護一個字符串，支持后面加字符串，給定串詢問出現次數。強制在線。

數據范圍：暴力跑不過

前置知識：重量平衡樹

眾所周知，平衡樹都用了一些策略保證平衡。

平衡有三種：嚴格平衡，均攤平衡，期望平衡

其中嚴格平衡和期望平衡的（當然不是很嚴格，規模上是平衡的就可以了）稱為重量平衡樹。（該定義存疑）

這種平衡樹每次操作對樹的結構影響很小（最大的子樹為log級別）。這意味著你可以用它維護子樹規模的集合。

也就是說可以在里面套一個動態開點線段樹維護子樹的所有權值。

常見的有替罪羊樹和treap。

（fhq好像也可以，但好像沒人用……）

以維護子樹集合為例，替罪羊樹每次重構的時候暴力更新集合。

treap就比較玄學，旋轉完后暴力更新，期望是log的……

---

回到這道題，我們需要一個叫后綴平衡樹的黑科技。

其實就是用重量平衡樹維護后綴數組。

首先把所有串倒序，注意是假裝一來就是倒的，顯然不影響答案，只是改成了在前面加。

把字符一個一個添加，這樣每添加一個只會多一個后綴，只需要把這個后綴插入平衡樹。

注意：把添加的字符按順序記下來，這樣得到的串是輸入順序，但實際上是倒著存的。

現在的問題是如何快速比較兩個后綴。

由于新來的后綴不在樹上，但之前的樹上的后綴是可以快速比較的。

所以我們比較第一個字符，如果一樣就丟掉然后在樹上比較。

顯然可以$O(logn)$做。一個技巧，對于每個節點維護$(l,r)$,其權值為$val=\frac{l+r}{2}$,左兒子$(l,val)$,右兒子$(val,r)$,可以直接用權值$O(1)$比較，因為深度是$log$的，精度可以保證。 重構時暴力更新。

詢問的時候查比$S$小的后綴數，再在后面加一個很大的字符再查一次，兩個減一下。由于深度是$log$的，所以直接暴力比較復雜度是$O(|S|logn)$

莫名覺得比后綴數組好寫是怎么回事

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <algorithm> //#include <windows.h> #include <cassert> #define MAXN 3600005 using namespace std; const double alpha=0.7; char c[MAXN]; int ch[MAXN][2],siz[MAXN],rt,tot; double L[MAXN],R[MAXN]; inline double val(const int& x){return x?L[x]+R[x]:-1e6;} inline bool cmp(const int& x,const int& y){return c[x]<c[y]||(c[x]==c[y]&&val(x-1)<val(y-1));} int p[MAXN]; void dfs(int u) {if (ch[u][0]) dfs(ch[u][0]);p[++p[0]]=u;if (ch[u][1]) dfs(ch[u][1]); } void build(int& x,int l,int r,double vl,double vr) {if (l>r) return (void)(x=0);int mid=(l+r)>>1;x=p[mid];siz[x]=r-l+1;L[x]=vl;R[x]=vr;double vmid=(vl+vr)/2;build(ch[x][0],l,mid-1,vl,vmid);build(ch[x][1],mid+1,r,vmid,vr); } void insert(int& x,int i,double l,double r) {if (!x) return (void)(siz[x=i]=1,L[x]=l,R[x]=r);if (siz[ch[x][0]]>siz[x]*alpha||siz[ch[x][1]]>siz[x]*alpha){p[0]=0;dfs(x);build(x,1,p[0],l,r);}++siz[x];L[x]=l;R[x]=r;double mid=(l+r)/2;if (cmp(i,x)) insert(ch[x][0],i,l,mid);else insert(ch[x][1],i,mid,r); } inline void insert(char i){c[++tot]=i;insert(rt,tot,0,1e6);} int de; int query(int x,char *s,int len) {if (!x) return 0;int i;for (i=0;s[i]==c[x-i]&&i<len;i++);if (i==len||s[i]<c[x-i]) return query(ch[x][0],s,len);else{de=x;int res=siz[ch[x][0]]+1+query(ch[x][1],s,len);return res;} } char s[MAXN]; int len,mask; inline void read(int type) {#ifndef ONLINE_JUDGE type=0;#endifscanf("%s",s);len=strlen(s);if (type){int t=mask;for (int i=0;i<len;i++) swap(s[i],s[t=(t*131+i)%len]); } } int main() {int q;scanf("%d",&q);read(0);for (int i=0;i<len;i++) insert(s[i]);while (q--){read(0);if (s[0]=='A'){read(1);for (int i=0;i<len;i++) insert(s[i]);}else{read(1);reverse(s,s+len);int ans=-query(rt,s,len);int t=de;s[len]='Z'+1;ans+=query(rt,s,len+1);printf("%d\n",ans);mask^=ans;}}return 0; }

總結

以上是生活随笔為你收集整理的【bzoj2555】Substring【后缀平衡树入门】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。