Yavin(ijɳ²èµÄ´úÂë¿â)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;

typedef long long LL;
typedef double ld;

const int MAX=1000000+10;
const int Alpha=26;

int INF=MAX-1,Del,Add;
char str[MAX];
LL ans=0;

struct Node
{
	Node* ne[Alpha];
	Node* fail,*p;//ºó׺Á´½Ó
	int l,r,nume;
	Node(int a=0,int b=0,Node* father=0)
	{
		memset(ne,0,sizeof ne);
		fail=0;
		l=a,r=b;
		p=father;
		nume=0;
	}

	void set(int id,Node* t)
	{
		if(!ne[id])
			++nume;
		ne[id]=t;
	}

	pair<Node*,Node*> split(int L,int id,int len)
	{
		if(L==r-l)
		{
			Node* nleaf=new Node(len,INF,this);
			set(id,nleaf);
			ans-=len;
			return mp(nleaf,this);
		}

		if(r!=INF)//ans-=r-l+1
			ans-=r+1;
		ans+=l;

		Node * np=new Node(l,l+L,p);
		ans+=L+1;

		p->set(str[l],np);
		np->set(str[l+L+1],this);
		l=l+L+1;
		if(r!=INF)
			ans+=r+1;
		ans-=l;

		p=np;
		Node* nleaf=new Node(len,INF,np);
		np->set(id,nleaf);
		ans-=len;
		return mp(nleaf,np);
	}
}*Root;

struct State
{
	Node* u;
	int L;

	int check(int id)
	{
		if(L==u->r-u->l)
			return u->ne[id]!=0;
		else
			return (str[u->l+L+1])==id;
	}

	void Go(int id)
	{
		if(L==u->r-u->l)
		{
			u=u->ne[id];
			L=0;
		}
		else L++;
	}

	State Up()
	{
		State p;
		p.u=u->p;
		p.L=L;
		int c=u->l;
		if(p.u==Root && L==0)
			return p;
		if(p.u==Root)
		{
			p.L--;
			c++;
			p.u=p.u->fail->ne[(int)str[u->l+1]];
		}
		else
			p.u=p.u->fail->ne[(int)str[c]];
		for(;;)
		{
			int len=p.u->r-p.u->l+1;
			if(p.L<len)
				break;
			c+=len;
			p.L-=len;
			p.u=p.u->ne[(int)str[c]];
		}
		return p;
	}
}active;

queue<Node*> leaf_que;

void showEdge(Node* u)
{
	int i;
	REP(i,max(u->l,1),min( u->r, Add ))
		cout<<char( str[i]+'a' );
	cout<<" ";
}

Node* st[MAX];
int top;

void showTree(Node* u)
{
	if(!u)
		return;
	int i;
	st[++top]=u;
	REP2(i,0,Alpha)
		showTree(u->ne[i]);
	if(u->r==MAX-1)
	{
		REP(i,2,top)
			showEdge(st[i]);
		cout<<endl;
	}
	--top;
}

void add(int len,int id)
{
	Node* last=0;
	for(;1;)
	{
		if(active.check(id))
		{
			if(last)
				last->fail=active.u;
			active.Go(id);
			break;
		}
		pair<Node*,Node*> np=active.u->split(active.L,id,len);
		if(last)
			last->fail=np.y;
		leaf_que.push(np.x);
		if(active.u==Root)
			break;
		last=np.y;
		active.u=np.y;
		active=active.Up();
	}
}

void del(int len)
{
	Node* u=leaf_que.front();
	leaf_que.pop();
	len=len-Del+1;
	int cc=0;
//	showEdge(active.u);
//	cout<<endl;
	for(;u->nume==0 && u!=active.u;)
	{
		Node* p=u->p;
		p->nume--;
		p->ne[(int)str[u->l]]=0;
		if(u->r!=INF)
			ans-=u->r+1;
		ans+=u->l;
		len+=min(u->r,Add)-u->l+1;
		delete u;
		u=p;
	}
	if(u!=Root && u==active.u && u->nume==0)
	{
		if(u->r!=INF)
			ans-=u->r+1;
		ans+=u->l;

		u->r=INF;
		cc+=(min(u->r,Add)-u->l+1);
		cc-=active.L+1;
		u->l+=cc;
		ans-=u->l;
		leaf_que.push(u);
		active=active.Up();
	}
}

int main()
{
	freopen("fqw.in","r",stdin);
	freopen("fqw.out","w",stdout);
	int n;
	scanf("%d",&n);
	Add=0,Del=1;
	active.u=Root=new Node(0,0,0);
	Root->p=0;
	Root->fail=Root;
	active.L=0;
	while(n--)
	{
		char Q[10];
		scanf("%s",Q);
		if(Q[0]=='+')
		{
			scanf("%s",Q);
			str[++Add]=Q[0]-'a';
			add(Add,str[Add]);
		}
		else
		{
			/*
		if(Add+Del+1-1==7)
			showTree(Root);
			*/
			del(Add);
			++Del;
		}
		cout<<ans+(LL)leaf_que.size()*(Add+1)<<endl;
		/*
		if(Add+Del-1==7)
			showTree(Root);
			*/
	}
	return 0;
}