记录编号	377927	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016][GDOI2016模拟3.14] hashit	最终得分	100
用户昵称	半汪	是否通过	通过
代码语言	C++	运行时间	0.412 s
提交时间	2017-03-02 18:04:54	内存使用	4.58 MiB

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <ctime>
 
using namespace std;
typedef unsigned long long LL;
 
const int MAXN = 1e5 + 5;
const int Pri = 9973;
const LL Inf = 1ll << 62;
 
struct SuffixBalanceTree {
    LL tag;
    int Son[2], Size, fix;
} Tr[MAXN];
 
int tot, Root, Lcp[MAXN];
char S[MAXN];
LL Del, Pow[MAXN], Has[MAXN];
 
bool Cmp(int x, int y) {
    return S[x] < S[y] || S[x] == S[y] && Tr[x - 1].tag < Tr[y - 1].tag;
}
 
void Clear(int x, LL l, LL r) {
    Tr[x].fix = rand();
    Tr[x].Son[0] = Tr[x].Son[1] = 0;
    Tr[x].Size = 1;
    Tr[x].tag = (l + r) >> 1;
}
 
void Update(int Now, LL l, LL r) {
    if (!Now) return;
    Tr[Now].tag = (l + r) >> 1;
    LL Mid = (l + r) >> 1;
    Update(Tr[Now].Son[0], l, Mid), Update(Tr[Now].Son[1], Mid + 1, r);
    Tr[Now].Size = Tr[Tr[Now].Son[0]].Size + Tr[Tr[Now].Son[1]].Size + 1;
}
 
void Rotate(int Now, int Pre, LL l, LL r) {
    int Side = Tr[Pre].Son[1] == Now;
    Tr[Pre].Son[Side] = Tr[Now].Son[Side ^ 1];
    Tr[Now].Son[Side ^ 1] = Pre;
    Update(Now, l, r);
}
 
void Insert(int &Now, LL l, LL r) {
    if (!Now) {
        Now = tot;
        Clear(Now, l, r);
        return;
    }
    Tr[Now].Size ++;
    LL Mid = (l + r) >> 1;
    if (Cmp(tot, Now)) Insert(Tr[Now].Son[0], l, Mid); else
        Insert(Tr[Now].Son[1], Mid + 1, r); 
    if (Tr[tot].fix > Tr[Now].fix) {
        Rotate(tot, Now, l, r);
        Now = tot;
    }
}
 
int GetRank(int Now) {
    if (Now == tot) return Tr[Tr[Now].Son[0]].Size + 1;
    if (Cmp(tot, Now)) return GetRank(Tr[Now].Son[0]); 
    return Tr[Tr[Now].Son[0]].Size + 1 + GetRank(Tr[Now].Son[1]);
}
 
int Search(int Now, int rk) {
    if (!Now) return Now;
    if (Tr[Tr[Now].Son[0]].Size + 1 == rk) return Now;
    if (Tr[Tr[Now].Son[0]].Size >= rk) return Search(Tr[Now].Son[0], rk); 
    return Search(Tr[Now].Son[1], rk - Tr[Tr[Now].Son[0]].Size - 1);
}
 
bool Same(int l1, int l2, int len) {
    int r1 = l1 + len - 1, r2 = l2 + len - 1;
    return Has[r1] - Has[l1 - 1] * Pow[len] == Has[r2] - Has[l2 - 1] * Pow[len];
}
 
int TreatLcp(int x, int y) {
    int l = 1, r = min(x, y), Ans = 0;
    while (l <= r) {
        int Mid = (l + r) >> 1;
        if (Same(x - Mid + 1, y - Mid + 1, Mid)) Ans = Mid, l = Mid + 1; else 
            r = Mid - 1;
    }
    Lcp[y] = Ans;
}
 
void Add(char c) {
    S[++ tot] = c;
    Has[tot] = Has[tot - 1] * Pri + S[tot] - 'a' + 1;
    Insert(Root, 1, Inf);
    int rk = GetRank(Root);
    int l = Search(Root, rk - 1), r = Search(Root, rk + 1);
    Del = Del - Lcp[r];
    TreatLcp(l, tot), TreatLcp(tot, r);
    Del = Del + Lcp[tot] + Lcp[r];
}
 
int Merge(int a, int b) {
    if (!a) return b;
    if (!b) return a;
    if (Tr[a].fix < Tr[b].fix) {
        Tr[b].Son[0] = Merge(a, Tr[b].Son[0]);
        return b;
    }
    Tr[a].Son[1] = Merge(Tr[a].Son[1], b);
    return a;
}
 
void Out(int &Now, LL l, LL r) {
    if (tot == Now) {
        Now = Merge(Tr[Now].Son[0], Tr[Now].Son[1]);
        Update(Now, l, r);
    } else {
        Tr[Now].Size --;
        LL Mid = (l + r) >> 1;
        if (Cmp(tot, Now)) Out(Tr[Now].Son[0], l, Mid); else 
            Out(Tr[Now].Son[1], Mid + 1, r);
    }
}
 
void Delete() {
    int rk = GetRank(Root);
    int l = Search(Root, rk - 1), r = Search(Root, rk + 1);
    Del = Del - Lcp[tot] - Lcp[r];
    TreatLcp(l, r);
    Del = Del + Lcp[r];
    Out(Root, 1, Inf);
    tot --;
}
 
int main() {
	freopen("hahaha.in","r",stdin);freopen("hahaha.out","w",stdout);
	int len;
	scanf("%d",&len);
    scanf("%s", S + 1);
    Pow[0] = 1;
    for (int i = 1; i <= len; i ++) Pow[i] = Pow[i - 1] * Pri;
    for (int i = 1; i <= len; i ++) {
        if (S[i] == '-') Delete(); else 
            Add(S[i]);
        printf("%lld\n", 1ll * tot * (tot + 1) / 2 - Del);
    }
}