题解：
后缀自动机
我们可以通过建立trie
把询问变成询问一些点的并
把trie建立成SAM和广义SAM基本相同，就是在父亲和儿子之间连边
然后就变成了询问树链的并
我们可以发现答案=sigma dis[i] -sigma(dis[lca(i,i+1)])
其中i和i+1dfs序相邻
可以通过set来维护
***
把倍增的预处理写在了dfs前
把&&写成了&
代码：
#include <bits/stdc++.h> #define rint register int #define IL inline #define rep(i,h,t) for (rint i=h;i<=t;i++) #define dep(i,t,h) for (rint i=t;i>=h;i--) #define ll long long using namespace std; const int N=2e5; char s[N]; int len,cnt,son[N][26],pos[N],cnt2; struct hz{ int ch[N][26],node,len[N],fa[N]; hz() { node=1; } int extend(int c,int z) { int lst=z; int f=lst; if (ch[f][c]&&len[ch[f][c]]==len[f]+1) { lst=ch[f][c]; return(lst); } int p=++node; lst=p; len[p]=len[f]+1; //size[p][pl]=1; while (f&&!ch[f][c]) ch[f][c]=p,f=fa[f]; if (!f) { fa[p]=1; return(p);}; int x=ch[f][c],y=++node; if (len[f]+1==len[x]) {fa[p]=x; node--;return(p);} len[y]=len[f]+1; fa[y]=fa[x]; fa[x]=fa[p]=y; memcpy(ch[y],ch[x],sizeof(ch[x])); while (f&&ch[f][c]==x) ch[f][c]=y,f=fa[f]; return(p); } void build(int x) { rep(i,0,25) if (son[x][i]) { pos[son[x][i]]=extend(i,pos[x]); build(son[x][i]); } } }S; int l,head[N],bz[N][21],dfn[N],rl[N],dis[N],fa[N],dep[N],zt[N]; struct re{ int a,b; }a[N]; void arr(int x,int y) { a[++l].a=head[x]; a[l].b=y; head[x]=l; } void dfs(int x,int y) { int u=head[x]; bz[x][0]=y; dfn[x]=++cnt2; rl[cnt2]=x; dep[x]=dep[y]+1; dis[x]=dis[y]+S.len[x]-S.len[y]; while (u) { int v=a[u].b; dfs(v,x); u=a[u].a; } } set<int> M; set<int>::iterator it; int lca(int x,int y) { if (dep[x]<dep[y]) swap(x,y); dep(i,20,0) if (dep[bz[x][i]]>=dep[y]) x=bz[x][i]; if (x==y) return(x); dep(i,20,0) if (bz[x][i]!=bz[y][i]) x=bz[x][i],y=bz[y][i]; return(bz[x][0]); } int main() { freopen("1.in","r",stdin); freopen("3.out","w",stdout); scanf("%s",s); len=strlen(s); int now=1; cnt=1; rep(i,0,len-1) { if (s[i]=='-') now=fa[now]; else { if (!son[now][s[i]-'a']) son[now][s[i]-'a']=++cnt,fa[cnt]=now; now=son[now][s[i]-'a']; } } pos[1]=1; S.build(1); for(int i=2;i<=S.node;i++) arr(S.fa[i],i); dfs(1,0); rep(i,1,20) rep(j,1,S.node) bz[j][i]=bz[bz[j][i-1]][i-1]; ll ans=0; now=1; int cnt3=0; rep(i,0,len-1) { if (s[i]=='-') { int x=0,y=0; ans-=dis[now]; it=M.find(dfn[now]); it++; if (it!=M.end()) x=rl[*it]; it--; if (it!=M.begin()) y=rl[*--it]; M.erase(dfn[now]); if (x) ans+=dis[lca(now,x)]; if (y) ans+=dis[lca(now,y)]; if (x&&y) ans-=dis[lca(x,y)]; now=zt[--cnt3]; } else { int x=0,y=0; now=S.ch[now][s[i]-'a']; zt[++cnt3]=now; ans+=dis[now]; it=M.insert(dfn[now]).first; it++; if (it!=M.end()) x=rl[*it]; it--; if (it!=M.begin()) { y=rl[*--it]; } if (x) ans-=dis[lca(now,x)]; if (y) ans-=dis[lca(now,y)]; if (x&&y) ans+=dis[lca(x,y)]; // cout<<lca(pos[now],x)<<" "<<lca(pos[now],y)<<" "<<x<<" "<<y<<endl; } printf("%lld ",ans); } return 0; }