【BZOJ5084】hashit（字尾平衡樹）（哈希）

傳送門

題解：

如果我們能夠搞出字尾數組，顯然我們考慮維護一下ht數組就行了。

直接上字尾平衡樹，每次找到前驅後繼，然後直接算LCP即可。

算LCP直接哈希就行了。

代碼：

#include<bits/stdc++.h>
#define ll long long
#define re register
#define cs const

using std::cerr;
using std::cout;

cs int mod=1e9+19;
inline int add(int a,int b){a+=b-mod;return a+(a>>31&mod);}
inline int dec(int a,int b){a-=b;return a+(a>>31&mod);}
inline int mul(int a,int b){ll r=(ll)a*b;return r>=mod?r%mod:r;}

cs int N=1e5+7;

char s[N];int n;

int nl;ll ans;
int lc[N],rc[N],lcp[N];
int siz[N],rt,*bad;
double L[N],R[N],rebl,rebr;
cs double alpha=0.6;

int h[N],pw[N],base=47;

inline int get_hash(int l,int r){
	return dec(h[r],mul(h[l-1],pw[r-l+1]));
}

inline int LCP(int a,int b){
	int l=0,r=std::min(a,b),mid,ans=0;
	while(l<=r){
		mid=l+r>>1;
		if(get_hash(a-mid+1,a)==get_hash(b-mid+1,b))ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}

inline double val(int u){return L[u]+R[u];}
inline bool Cmp(int u,int v){
	return s[u]<s[v]||(s[u]==s[v]&&val(u-1)<val(v-1));
}

inline void ins(int &u,int i,double l=0,double r=1e18){
	if(!u){u=i,lc[i]=rc[i]=0,siz[i]=1,L[u]=l,R[u]=r;return ;}
	++siz[u];double mid=val(u)*0.5;
	if(Cmp(u,i)){
		ins(lc[u],i,l,mid);
		if(siz[lc[u]]>siz[u]*alpha)bad=&u,rebl=l,rebr=r;
	}
	else {
		ins(rc[u],i,mid,r);
		if(siz[rc[u]]>siz[u]*alpha)bad=&u,rebl=l,rebr=r;
	}
}
inline int merge(int u,int v){
	if(!u||!v)return u|v;
	if(siz[u]>siz[v]){
		siz[u]+=siz[v];
		rc[u]=merge(rc[u],v);
		return u;
	}
	else {
		siz[v]+=siz[u];
		lc[v]=merge(u,lc[v]);
		return v;
	}
}
inline void del(int &u,int i,double l=0,double r=1e18){
	if(u==i){u=merge(lc[u],rc[u]);return ;}
	--siz[u];double mid=val(u)*0.5;
	if(val(u)<val(i)){
		del(rc[u],i,mid,r);
		if(siz[lc[u]]>siz[u]*alpha)bad=&u,rebl=l,rebr=r;
	}
	else {
		del(lc[u],i,l,mid);
		if(siz[rc[u]]>siz[u]*alpha)bad=&u,rebl=l,rebr=r;
	}
}

int q[N],qn;
inline void inorder_dfs(int u){
	if(lc[u])inorder_dfs(lc[u]);q[++qn]=u;
	if(rc[u])inorder_dfs(rc[u]);
}

inline int build(int l,int r,double vl,double vr){
	if(l>r)return 0;int mid=l+r>>1,u=q[mid];
	double Mid=(vl+vr)*0.5;
	L[u]=vl,R[u]=vr;siz[u]=r-l+1;
	lc[u]=build(l,mid-1,vl,Mid);
	rc[u]=build(mid+1,r,Mid,vr);
	return u;
}

inline void rebuild(int &u){
	qn=0;inorder_dfs(u);
	u=build(1,qn,rebl,rebr);
}

inline int Rank(int i){
	int u=rt,ans=0;
	while(u){
		if(u==i)return ans+siz[lc[u]]+1;
		if(val(u)<val(i))ans+=siz[lc[u]]+1,u=rc[u];
		else u=lc[u];
	}
	assert(0);
}

inline int Kth(int k){
	int u=rt;
	while(u){
		if(siz[lc[u]]+1==k)return u;
		if(k<=siz[lc[u]])u=lc[u];
		else k-=siz[lc[u]]+1,u=rc[u];
	}
	return 0;
}

inline void Ins(char c){
	s[++nl]=c;h[nl]=add(mul(h[nl-1],base),c);
	bad=NULL;ins(rt,nl);
	if(bad!=NULL)rebuild(*bad);
	int u=nl,k=Rank(u),pre=Kth(k-1),suf=Kth(k+1);
	ans-=lcp[suf];
	lcp[suf]=LCP(suf,u),lcp[u]=LCP(u,pre);
	ans+=lcp[suf]+lcp[u];
}

inline void Del(){
	int u=nl,k=Rank(nl),pre=Kth(k-1),suf=Kth(k+1);--nl;
	ans-=lcp[u]+lcp[suf];
	ans+=lcp[suf]=LCP(pre,suf);
	bad=NULL;del(rt,u);
	if(bad!=NULL)rebuild(*bad);
}

signed main(){
#ifdef zxyoi
	freopen("hashit.in","r",stdin);
#endif
	scanf("%s",s+1);n=strlen(s+1);pw[0]=1;
	for(int re i=1;i<=n;++i)pw[i]=mul(pw[i-1],base);
	for(int re i=1;i<=n;++i){
		if(s[i]!='-')Ins(s[i]);else Del();
		cout<<(nl+1)*nl/2-ans<<"\n";
	}
	return 0;
}