# [suffix automaton] BZOJ5084. hashit

Teacher Chen shenti
Consider how to delete. Add two nodes at most each time. Then delete only two nodes

Two values will be changed when characters are added, one is nxt and the other is fail

When we delete the node uu, if the failure of a point vv is uu, then we need to change the failvfailv to failufailu, which can be realized by using concurrent query set

Another is nxt. When nxt changes, only when nq is added, can linked list be used for maintenance (probably also a concurrent query set)

```#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

const int N=200010;

int n;
char a[N];

ll ans;

inline int calc(int x){
int cur=x;
for(int i=17;~i;i--)
if(!vis[fa[x][i]]) x=fa[x][i];
return len[cur]-len[fa[x][0]];
}

int Find(int x){
if(!vis[fail[x]]) return fail[x]=Find(fail[x]);
return fail[x];
}

int Get(int &x){
return x;
}

inline void extend(int p,int c,int ps){
int np=++cnt; len[np]=len[p]+1; pos[ps]=np; vis[np]=1;
while(p && !Get(nxt[p][c])) nxt[p][c]=np,p=fail[p];
if(!p) fail[np]=1,size[1]++;
else{
int q=nxt[p][c];
if(len[q]==len[p]+1) fail[np]=q,size[q]++;
else{
memcpy(nxt[nq],nxt[q],sizeof(nxt[nq]));
ans-=len[q]-len[Find(q)];
fail[q]=fail[np]=nq;
ans+=len[q]-len[nq]+len[nq]-len[Find(nq)];
size[nq]+=2;
while(p && Get(nxt[p][c])==q) nxt[p][c]=nq,p=fail[p];
}
}
ans+=len[np]-len[Find(np)];
}

void PutAns(ll x){
if(x>=10) PutAns(x/10); putchar(x%10+'0');
}

inline void del(int x){
ans-=len[x]-len[Find(x)];
vis[x]=0; ans+=(len[x]-len[Find(x)])*size[x];
size[Find(x)]+=size[x]-1;
}

int main(){
scanf("%s",a+1); n=strlen(a+1);
pos[0]=1; vis[1]=1;
for(int i=1;i<=n;i++){
if(a[i]!='-'){
S[++top]=i; extend(pos[S[top-1]],a[i]-'a',i);
}
else{
int x=S[top--];