你有一个字符串S，最开始为空，要求支持两种操作

在S后面加入字符c

删除S最后一个字符

每次操作询问S有多少个两两不同子串

应该本来应该用SAM+Trie离线做的，然而为了练一下后缀平衡树就写了

其实也很好写，用哈希比较一下就好了，可以用set实现，开一个数组存每个后缀对应的节点就好

求height也可以用哈希

#pragma GCC opitmize("O3")#pragma G++ opitmize("O3")#include
    
     #include
     
      #include
      
       #include
       
        #define LL long longusing namespace std;char s[100010]; int n=0;LL h[100010],bas[100010]={
     1};struct suffix{ int x; };inline LL gH(int l,int r){ return h[r]-h[l-1]*bas[r-l+1]; }inline int lcp(int x,int y){	if(x==y) return 0; 	int l=-1,r=min(x,y)-1;	for(int m;l
        
         >1;		if(gH(x-m,x)==gH(y-m,y)) l=m;		else r=m-1;	}	return l+1;}inline bool operator< (suffix a,suffix b){	int c=lcp(a.x,b.x); return s[a.x-c]
         
          
            w;multiset
           
            ::iterator c[100010],p,q;int main(){ int ans=0; for(int i=1;i<=100000;++i) bas[i]=bas[i-1]*27; for(char o;;){ o=getchar(); if(o=='-'){ p=q=c[n]; ++p; --q; ans-=n-lcp(p->x,n)-lcp(n,q->x)+(p->x==n || q->x==n?0:lcp(p->x,q->x)); w.erase(c[n--]); } else if(o>='a' && o<='z'){ s[++n]=o; h[n]=h[n-1]*27+o-'a'; p=q=c[n]=w.insert((suffix){n}); ++p; --q; ans+=n-lcp(p->x,n)-lcp(n,q->x)+(p->x==n || q->x==n?0:lcp(p->x,q->x)); } else break; printf("%d\n",ans); }}