Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXN 400010

int n;

char c[MAXN];

struct node

{

	int tr[26];

	int par,maxl;

}s[MAXN << 1];

int ptr = 1,root = 1;

int newnode(int l){int k = ++ptr;s[k].maxl = l;return k;}

int extend(int last,int k)

{

	int p = last;

	if(s[p].tr[k])

	{

		int q = s[p].tr[k];

		if(s[p].maxl + 1 == s[q].maxl)return q;

		else

		{

			int nq = newnode(s[p].maxl + 1);

			memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

			s[nq].par = s[q].par;

			s[q].par = nq;

			for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

			return nq;

		}

	}

	else

	{

		int np = newnode(s[p].maxl + 1);

		for(;p && s[p].tr[k] == 0;p = s[p].par)s[p].tr[k] = np;

		if(p == 0)s[np].par = root;

		else

		{

			int q = s[p].tr[k];

			if(s[p].maxl + 1 == s[q].maxl)s[np].par = q;

			else

			{

				int nq = newnode(s[p].maxl + 1);

				memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

				s[nq].par = s[q].par;

				s[q].par = s[np].par = nq;

				for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

			}

		}

		return np;

	}

}

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int dad[MAXN];

int tr[MAXN][26];

int pos[MAXN];

void dfs(int k,int cur)

{

	pos[k] = cur;

	for(int i = 0;i < 26;++i)

	{

		if(tr[k][i] == 0)continue;

		int nxt = extend(cur,i);

		dfs(tr[k][i],nxt);

	}

	return;

}

int siz[MAXN],son[MAXN],top[MAXN],dep[MAXN],fa[MAXN],rnk[MAXN],dfn[MAXN],tot = 0;

void dfs1(int k,int depth)

{

	dep[k] = depth;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa[k])continue;

		fa[e[i].to] = k;

		dfs1(e[i].to,depth + 1);

		siz[k] += siz[e[i].to];

		if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

		{

			son[k] = e[i].to;

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	rnk[k] = ++tot;dfn[tot] = k;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return (dep[a] < dep[b] ? a : b);

}

set<int> ss;

long long sum = 0;

void insert(int k)

{

	sum += s[k].maxl;

	set<int>::iterator pre,nxt;

	pre = nxt = ss.lower_bound(rnk[k]);

	int pr = 0,nx = 0;

	if(nxt != ss.end())nx = *nxt;

	if(pre != ss.begin())pr = *(--pre);

	if(pr != 0)sum -= s[LCA(k,dfn[pr])].maxl;

	if(nx != 0)sum -= s[LCA(k,dfn[nx])].maxl;

	if(pr != 0 && nx != 0)sum += s[LCA(dfn[pr],dfn[nx])].maxl;

	ss.insert(rnk[k]);//cout << "insert " << k << " " << rnk[k] << endl;

	return;

}

void remove(int k)

{

	ss.erase(rnk[k]);//cout << "erase " << k << " " << rnk[k] << endl;

	sum -= s[k].maxl;

	set<int>::iterator pre,nxt;

	pre = nxt = ss.lower_bound(rnk[k]);

	int pr = 0,nx = 0;

	if(nxt != ss.end())nx = *nxt;

	if(pre != ss.begin())pr = *(--pre);

	if(pr != 0)sum += s[LCA(k,dfn[pr])].maxl;

	if(nx != 0)sum += s[LCA(k,dfn[nx])].maxl;

	if(pr != 0 && nx != 0)sum -= s[LCA(dfn[pr],dfn[nx])].maxl;

	return;

}

int main()

{

	scanf("%s",c + 1);

	int l = strlen(c + 1);

	int cur = 1;n = 1;

	for(int i = 1;i <= l;++i)

	{

		if(c[i] == '-')cur = dad[cur];

		else

		{

			if(tr[cur][c[i] - 'a'] == 0)

			{

				++n;

				dad[n] = cur;

				tr[cur][c[i] - 'a'] = n;

			}

			cur = tr[cur][c[i] - 'a'];

		}

	}

	dfs(1,1);

	for(int i = 2;i <= ptr;++i)add(s[i].par,i);

	dfs1(1,1);dfs2(1,1);

	cur = 1;

	for(int i = 1;i <= l;++i)

	{

		if(c[i] == '-')

		{

			remove(pos[cur]);

			cur = dad[cur];

		}

		else

		{

			cur = tr[cur][c[i] - 'a'];

			insert(pos[cur]);

		}

		printf("%lld\n",sum);

	}

	return 0;

}