记录编号	310680	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016 Round1] 生成魔咒	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.754 s
提交时间	2016-09-22 21:21:46	内存使用	6.41 MiB

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <list>
#include <map>
using namespace std;
#define MAXN 100003
long long ans = 0;
struct SAM
{
    int last, size;
    struct state
    {
        map<int, int> next;
        int link, len;
        void init()
        {
            link = -1;
            len = 0;
        }
    }st[MAXN<<1];
    SAM()
    {
        last = size = 0;
        newst();
    }
    int newst()
    {
        st[size++].init();
        return size-1;
    }
    void copy(int a, int b)
    {
        st[a].next = st[b].next;
        st[a].link = st[b].link;
    }
    void append(int c)
    {
        int cur = newst();
        st[cur].len = st[last].len + 1;
        int p;
        for(p = last; p != -1 && !st[p].next[c]; p = st[p].link)
            st[p].next[c] = cur;
        if(p == -1)
            st[cur].link = 0;
        else
        {
            int q = st[p].next[c];
            if(st[q].len == st[p].len + 1)
                st[cur].link = q;
            else
            {
                int clone = newst();
                copy(clone, q);
                st[clone].len = st[p].len + 1;
                for(; p != -1 && st[p].next[c] == q; p = st[p].link)
                    st[p].next[c] = clone;
                st[q].link = st[cur].link = clone;
            }
        }
        ans += st[cur].len - st[st[cur].link].len; 
        printf("%lld\n", ans);
        last = cur;
    }
}s;

int main()
{
    freopen("menci_incantation.in", "r", stdin);
    freopen("menci_incantation.out", "w", stdout);
    int n;
    scanf("%d", &n);
    while(n--)
    {
        int a;
        scanf("%d", &a);
        s.append(a);
    }
    return 0;
}