题目概述

给出一个操作串：如果是小写字母，表示在当前字符串后面添加这个小写字母。如果是 $−$ ，表示删除当前字符串最后的小写字母（保证合法）。求每次操作后当前字符串不同子串的个数。

解题报告

暴力后缀自动机回滚做法戳这里。

后缀平衡树就是每次前端插入字符（插入一个后缀），动态维护后缀数组（以及rank和height）。

有两种写法：1.Hash大法好。2.手写平衡树动态标号。我懒死了当然就直接set+hash啦。

具体就是用set维护后缀数组，用二分+Hash定义一下后缀的优先级，然后每次前端插入（其实当成后端插入就行，就是Hash比较的时候需要倒过来）就直接insert(n)就好啦。

至于本质不同子串个数，我们插入和删除的时候找到前驱和后继，修正一下Height就行了。

set+hash的缺点：1.插入删除复杂度 $O(log_2^2n)$ 。2.没法维护rank数组……求rank可能还是得手写平衡树。

示例程序

#include<set>
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;typedef unsigned long long ULL;
const int maxn=100000,BA=19260817;

int n;LL ans;char s[maxn+5];ULL pw[maxn+5],ha[maxn+5];
struct SF {int x;SF(int X=0) {x=X;}};
#define Hash(L,R) (ha[R]-ha[(L)-1]*pw[(R)-(L)+1])
inline bool operator < (const SF &a,const SF &b){
    int A=a.x,B=b.x,L=1,R=min(A,B);if (Hash(A-R+1,A)==Hash(B-R+1,B)) return A<B;
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        Hash(A-mid+1,A)==Hash(B-mid+1,B)?L=mid+1:R=mid-1;return s[A-R]<s[B-R];
}
set<SF> S;set<SF>::iterator pre,suf;

inline int Height(int A,int B){
    int L=1,R=min(A,B);
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        Hash(A-mid+1,A)==Hash(B-mid+1,B)?L=mid+1:R=mid-1;return B-R;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    pw[0]=1;for (int i=1;i<=maxn;i++) pw[i]=pw[i-1]*BA;
    for (char ch=getchar();islower(ch)||ch=='-';ch=getchar()){
        if (islower(ch)){
            s[++n]=ch;ha[n]=ha[n-1]*BA+ch-'a';suf=S.upper_bound(SF(n));
            if (suf!=S.end()) {if (suf==S.begin()) ans-=(*suf).x;ans+=Height(n,(*suf).x);}
            if (suf!=S.begin()) pre=suf,pre--,ans+=Height((*pre).x,n); else ans+=n;
            if (suf!=S.begin()&&suf!=S.end()) ans-=Height((*pre).x,(*suf).x);
            S.insert(SF(n));
        } else{
            S.erase(SF(n));if (n==1) ans=0;suf=S.upper_bound(SF(n));
            if (suf!=S.end()) {if (suf==S.begin()) ans+=(*suf).x;ans-=Height(n,(*suf).x);}
            if (suf!=S.begin()) pre=suf,pre--,ans-=Height((*pre).x,n); else ans-=n;
            if (suf!=S.begin()&&suf!=S.end()) ans+=Height((*pre).x,(*suf).x);
            n--;
        }printf("%lld\n",ans);
    }return 0;
}