【BZOJ 4516】[SDOI2016] 生成魔咒

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4516

考试的时候，一看到要动态维护就把SA扔一边凉快去了QAQ
想一想，不能这么草率啊！
来说一说SA和SAM两种做法

1) SAM：
很明显就是求一个字符串本质不同的字串个数
SAM本身就是增量构造，于是就成裸题了

2) SA：
考虑离线之后，先逆序建一个完整的出来
那么加入一个字符，实际上就是加入了一个后缀
那么其对于答案的贡献，就是原来的height数组搞一搞
实现的话，搞一个RMQ什么的就好
代码的话，我们来召唤Menci：https://oi.men.ci/sdoi2016-incantation/

自己太懒，于是就只写了SAM的代码：

#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define LL long long
using namespace std;
using namespace tr1;

const int N = 200000+9; 

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

namespace Suffix_Automaton{
	#define SAM Suffix_Automaton
	int len[N],fail[N],cnt,tail;
	unordered_map<int,int> ch[N]; 
	
	inline int Extend(int c) {
		int w = tail; tail = ++cnt; len[tail] = len[w] + 1;
		while (w&&!ch[w]) ch[w] = cnt, w = fail[w];
		if (!w) fail[tail] = 1;
		else {
			if (len[ch[w]] == len[w]+1) fail[tail] = ch[w];
			else {
				int to = ch[w]; ch[++cnt] = ch[to];
				fail[cnt] = fail[to]; fail[to] = cnt; fail[tail] = cnt; 
				len[cnt] = len[w] + 1; while (ch[w] == to) ch[w] = cnt, w = fail[w];
			}
		} return len[tail] - len[fail[tail]];
	}
	
	inline void solve(int n) {
		cnt = tail = 1; 
		for (LL i=1,vout=0;i<=n;i++) 
			printf("%lld\n",vout+=Extend(read()));
	}
};

int main(){
	SAM::solve(read());
	return 0;
}

—– UPD 2016.9.29 —–
这™map比unordered_map快这么多有几个意思QAQ

这种感觉……
真·生无可恋