记录编号	380854	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016][GDOI2016模拟3.14] hashit	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.350 s
提交时间	2017-03-10 14:46:06	内存使用	2.69 MiB

#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;
const int N=1e5+10,p=479<<21|1,INV=681649299;
int n,len;
ll Mi[N],hash[N],inv[N];
char s[N];
ll HASH(int i,int l){return (p+hash[i]-hash[i-l])*inv[i-l]%p;}
int lcp(int x,int y){
	int l=0,r=min(x,y)-1;
	while (l<r){
		int mid=(l+r)>>1;
		if (HASH(x,mid+1)==HASH(y,mid+1)) l=mid+1;else r=mid;
	}
	return l;
}
ll ans;
struct suf{
	int p;
	bool operator < (const suf &x)const{
		int l=lcp(p,x.p);
		return s[p-l]<s[x.p-l];
	}
};
set<suf> S;
typedef set<suf>::iterator it;
int main()
{
	freopen("hahaha.in","r",stdin);
	freopen("hahaha.out","w",stdout);
	scanf("%d",&n);
	Mi[0]=inv[0]=1;
	for (int i=1;i<=n;i++)
		Mi[i]=Mi[i-1]*28%p,inv[i]=inv[i-1]*INV%p;
	hash[0]=s[0]=27;
	hash[len=1]=27*28;
	S.insert((suf){0});
	S.insert((suf){1});
	for (int i=1;i<=n;i++){
		char ch=getchar();
		while (ch!='-'&&(ch>'z'||ch<'a')) ch=getchar();
		if (ch=='-'){
			it x=S.find((suf){len}),y=x,z=y;
			--y;++z;
			ans+=lcp(y->p,z->p);
			ans-=lcp(x->p,y->p);
			ans-=lcp(x->p,z->p);
			S.erase(x);
			s[len--]=0;
		}
		else{
			ch=ch-'a'+1;
			s[++len]=ch;
			hash[len]=(hash[len-1]+Mi[len-1]*ch)%p;
			S.insert((suf){len});
			it x=S.find((suf){len}),y=x,z=x;
			--y;++z;
			ans-=lcp(y->p,z->p);
			ans+=lcp(x->p,y->p);
			ans+=lcp(x->p,z->p);
		}
		printf("%lld\n",(ll)len*(len-1)/2-ans);
	}
	return 0;
}