后缀平衡树-学习笔记

~~很高兴后缀平衡树的思想之前在某次Rush题的时候想出来了~~ 首先我个人的习惯是，每次在结尾插入一个字符，然后把前缀排序，字典序比较为从后往前。 其实想法很简单，当我们插入一个新的前缀时，它和其他前缀的字典序比较：如果首字母不同，直接比较；否则，它们去掉首字母后的两个前缀的字典序比较关系已经确定了，我们可以直接查。 具体实现，如果可以$O(\log ^2n)$，我们可以 1.在平衡树上求出rk 2.Hash+二分求LCS 更快的方法：对每个点维护double权值表示自己的排名。 每个点有一个权值区间，表示自己子树里的权值都在这个区间里，自己选择区间的中点。 这就要求树高不能太高，所以需要平衡树。 而且树的结构一旦变化，pushup的时间是$O(size)$的，于是普通的平衡树就用不了了。 我们可以 1.用Treap，期望子树大小$O(\log n)$ 2.用替罪羊树，暴力重构。 我选择后者。 人傻常数大，慢的一批。BZOJ 5084 好像SGT的alpha一般要设的比较大，0.8左右。 ```cpp #define N 200005 #define ls (ch[x][0]) #define rs (ch[x][1]) const ull bas=233; ull h[N][17],pw[N]; int ys[N]; namespace SGT { const double alpha=0.85; double rk[N]; int tot,pos[N],sz[N],ch[N][2]; il void up(int x) {sz[x]=sz[ls]+1+sz[rs];} pair<int,int> st[N]; int tp; void dfs(int x) { if(!x) return; dfs(ls); st[++tp]=mp(pos[x],x); dfs(rs); } void build(int &x,int l,int r,const double &vl,const double &vr) { if(l>r) {x=0; return;} gm; x=st[mid].se,ys[pos[x]=st[mid].fi]=x; rk[x]=(vl+vr)/2; build(ls,l,mid-1,vl,rk[x]); build(rs,mid+1,r,rk[x],vr); up(x); } double nl,nr; il void rebuild(int &x) { tp=0; dfs(x); build(x,1,tp,nl,nr); } int *ned; #define chk(x) {if(max(sz[ls],sz[rs])>sz[x]*alpha) ned=&x,nl=vl,nr=vr;} il bool les(int x,int y) { return h[x][0]<h[y][0]||(h[x][0]==h[y][0]&&rk[ys[x-1]]<rk[ys[y-1]]); } void ins(int &x,int p,const double &vl,const double &vr) { if(!x) { x=++tot; ys[pos[tot]=p]=x,rk[x]=(vl+vr)/2,sz[x]=1; return; } if(les(p,pos[x])) ins(ls,p,vl,rk[x]); else ins(rs,p,rk[x],vr); up(x); chk(x); } int rt; il void ins(int p) { ned=NULL; ins(rt,p,0,1); if(ned!=NULL) rebuild(*ned); } int merge(int x,int y) { if(!x||!y) return x|y; if(sz[x]>sz[y]) return rs=merge(rs,y),up(x),x; else return ch[y][0]=merge(x,ch[y][0]),up(y),y; } void del(int &x,int p) { if(pos[x]==p) { x=merge(ls,rs); return; } if(les(p,pos[x])) del(ls,p); else del(rs,p); --sz[x]; } il void del(int p) {del(rt,p);} int getrk(int x,int p) { if(pos[x]==p) return sz[ls]+1; if(les(p,pos[x])) return getrk(ls,p); else return getrk(rs,p)+sz[ls]+1; } int getp(int x,int k) { if(!x||k<=0) return -1; if(k<=sz[ls]) return getp(ls,k); if(k==sz[ls]+1) return pos[x]; return getp(rs,k-sz[ls]-1); } il int getrk(int p) {return getrk(rt,p);} il int getp(int k) {return getp(rt,k);} } LL ans; il int lcs(int x,int y) { ull hx=0,hy=0; int ml=0; for(ri i=16; i>=0; --i) { if((1<<i)>min(x,y)) continue; ull nx=h[x][i]*pw[ml]+hx, ny=h[y][i]*pw[ml]+hy; if(nx==ny) { hx=nx,hy=ny; x-=1<<i,y-=1<<i,ml+=1<<i; } } return ml; } int cnt; void insert(const char c) { h[++cnt][0]=c; for(ri i=1; i<=16&&cnt-(1<<(i-1))>0; ++i) h[cnt][i]=h[cnt-(1<<(i-1))][i-1]*pw[1<<(i-1)]+h[cnt][i-1]; SGT::ins(cnt); int k=SGT::getrk(cnt),a=SGT::getp(k-1),b=SGT::getp(k+1); if(a!=-1&&b!=-1) ans-=lcs(a,b); if(a!=-1) ans+=lcs(a,cnt); if(b!=-1) ans+=lcs(b,cnt); } void remove() { int k=SGT::getrk(cnt),a=SGT::getp(k-1),b=SGT::getp(k+1); SGT::del(cnt); if(a!=-1) ans-=lcs(a,cnt); if(b!=-1) ans-=lcs(b,cnt); if(a!=-1&&b!=-1) ans+=lcs(a,b); --cnt; } signed main() { #ifdef M207 freopen("in.in","r",stdin); // freopen("ot.out","w",stdout); #endif pw[0]=1; for(ri i=1; i<N; ++i) pw[i]=pw[i-1]*bas; static char tc[N]; scanf("%s",tc+1); int cq=strlen(tc+1); for(ri i=1; i<=cq; ++i) { if(tc[i]=='-') remove(); else insert(tc[i]); out((LL)cnt*(cnt+1)/2-ans); } return 0; } ```