Luogu P4070 [SDOI2016]生成魔咒

题目链接 (Click) (Here)

其实是看后缀数组资料看到这个题目的，但是一眼反应显然后缀自动机，每次维护添加节点后的答案贡献即可，唯一不友好的一点是需要平衡树维护，这里因为复杂度不卡而且也不需要用到(ch)数组的遍历访问，我采用了(map)的写法。

其实是因为不会平衡树维护啦，如果有机会还是要学一下啊。。这个题可是没给不用平衡树的部分分啊(Qwq)（直接全体(1e9)）

#include <bits/stdc++.h>
using namespace std;

const int N = 200010;

struct Suffix_Auto {
	int cnt, las; long long ans;
	int fa[N], len[N];
	map <int, int> ch[N];

	Suffix_Auto () {
		cnt = las = 1; ans = 0;
		memset (fa, 0, sizeof (fa));
		memset (len, 0, sizeof (len));
	}
	
	void extend (int c) {
		int p = las, q = ++cnt; las = q;
		len[q] = len[p] + 1;
		while (p != 0 && ch[p][c] == 0) {
			ch[p][c] = q;
			p = fa[p];
		}
		ans += len[q];
		if (p == 0) {
			fa[q] = 1;
		} else {
			int x = ch[p][c];
			if (len[x] == len[p] + 1) {
				fa[q] = x;
				ans -= len[x];
			} else {
				int y = ++cnt;
				fa[y] = fa[x];
				fa[x] = fa[q] = y;
				len[y] = len[p] + 1;
				ch[y] = ch[x];
				while (p != 0 && ch[p][c] == x) {
					ch[p][c] = y;
					p = fa[p];
				}
				ans -= len[y];
			}
		}
		cout << ans << endl;
	}
}sam;

int n, num;

int main () {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> num;
		sam.extend (num);
	}
}