记录编号	387050	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016 Round1] 生成魔咒	最终得分	100
用户昵称	Hellc	是否通过	通过
代码语言	C++	运行时间	0.212 s
提交时间	2017-03-25 15:46:04	内存使用	6.48 MiB

#include <cstdio>
#include <map>
 
namespace io{
    const int IN_SIZE = 1 << 15, OT_SIZE = 1 << 15;
 
    char inBuf[IN_SIZE], *S = NULL, *T = NULL, ch;
 
    char otBuf[OT_SIZE];
    int cur;
 
    inline int getchar(){
        if(S == T) S = inBuf, T = inBuf + fread(inBuf, 1, IN_SIZE, stdin);
        if(S == T) return EOF;
        return *S++;
    }
 
    template<typename Int>
    inline void readint(Int &x){
        do ch = getchar(); while('0' > ch || ch > '9');
        for(x = 0; '0' <= ch && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
    }
 
    inline void flush(){
        fwrite(otBuf, 1, cur, stdout);
        cur = 0;
    }
 
    inline void putchar(char ch){
        otBuf[cur++] = ch;
        if(cur == OT_SIZE) flush();
    }
 
    template<typename Int>
    inline void putint(Int x){
        if(x > 9) putint(x / 10);
        putchar('0' + x % 10);
    }
 
    inline void br(){
        putchar('\n');
    }
 
    inline void close(){
        flush();
    }
}
 
typedef long long ll;
 
const int MAX_N = 100000;
 
struct SuffixAutoMaton{
    struct Node{
        Node *parent;
        int len;
        std::map<int, Node*> next;
    } nodes[2 * MAX_N], *ptr;
 
    Node *root, *lastNode;
 
    ll ans;
 
    SuffixAutoMaton(){
        ptr = nodes;
 
        lastNode = root = ptr++;
 
        ans = 0;
    }
 
    ll append(int x){
        Node *newNode = ptr++;
        newNode->len = lastNode->len + 1;
 
        Node *curr = lastNode;
        while(curr && !curr->next.count(x)){
            curr->next[x] = newNode;
            curr = curr->parent;
        }
 
        if(curr == NULL){
            newNode->parent = root;
        } else{
            Node *child = curr->next[x];
 
            if(child->len == curr->len + 1){
                newNode->parent = child;
            } else{
                Node *clone = ptr++;
                
                clone->len = curr->len + 1;
                clone->parent = child->parent, child->parent = clone;
 
                clone->next = child->next;
                while(curr && curr->next.count(x) && curr->next[x] == child){
                    curr->next[x] = clone;
                    curr = curr->parent;
                }
 
                newNode->parent = clone;
            }
        }
 
        lastNode = newNode;
 
        return ans += lastNode->len - (lastNode->parent->len + 1) + 1;
    }
} sam;
 
int main(){
    freopen("menci_incantation.in", "r", stdin), freopen("menci_incantation.out", "w", stdout);
 
    int n;
    io::readint(n);
    for(int i = 0; i < n; i++){
        int x;
        io::readint(x);
        io::putint(sam.append(x)), io::br();
    }
 
    io::close();
    fclose(stdin), fclose(stdout);
    return 0;
}