P4070 [SDOI2016]生成魔咒

(color{#0066ff}{ 题目描述 })

魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 1、2 拼凑起来形成一个魔咒串 [1,2]。

一个魔咒串 S 的非空字串被称为魔咒串 S 的生成魔咒。

例如 S=[1,2,1] 时，它的生成魔咒有 [1]、[2]、[1,2]、[2,1]、[1,2,1] 五种。S=[1,1,1] 时，它的生成魔咒有 [1]、[1,1]、[1,1,1] 三种。最初 S 为空串。共进行 n 次操作，每次操作是在 S 的结尾加入一个魔咒字符。每次操作后都需要求出，当前的魔咒串 S 共有多少种生成魔咒。

(color{#0066ff}{输入格式})

第一行一个整数 n。

第二行 n 个数，第 i 个数表示第 i 次操作加入的魔咒字符。

(color{#0066ff}{输出格式})

输出 n 行，每行一个数。第 i 行的数表示第 i 次操作后 S 的生成魔咒数量

(color{#0066ff}{输入样例})

7
1 2 3 3 3 1 2

(color{#0066ff}{输出样例})

1
3
6
9
12
17
22

(color{#0066ff}{数据范围与提示})

对于%10的数据，(1 le n le 10)
对于%30的数据，(1 le n le 100)
对于%60的数据，(1 le n le 100)
对于%100的数据，(1 le n le 100000)
用来表示魔咒字符的数字 x 满足(1 le n le 10^9)

(color{#0066ff}{ 题解 })

SAM 大水题

题目相当于问你一个串，每加进一个字符，询问当前不同字串个数

用SAM统计就行了

#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL in() {
	char ch; int x = 0, f = 1;
	while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
	for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
	return x * f;
}
const int maxn = 2e5 + 5;
struct SAM {
protected:
	struct node {
		node *fa;
		std::map<int, node*> ch;
		int len, siz;
		node(int len = 0, int siz = 0): fa(NULL), len(len), siz(siz) {
			ch.clear();
		}
	};
	node *root, *tail, *lst;
	node pool[maxn];
	void clr() {
		tail = pool;
		root = lst = new(tail++) node();
	}
public:
	SAM() { clr(); }
	node *extend(int c) {
		node *o = new(tail++) node(lst->len + 1, 1), *v = lst;
		for(; v && !v->ch[c]; v = v->fa) v->ch[c] = o;
		if(!v) o->fa = root;
		else if(v->len == v->ch[c]->len - 1) o->fa = v->ch[c];
		else {
			node *n = new(tail++) node(v->len + 1), *d = v->ch[c];
			n->ch = d->ch;
			n->fa = d->fa, d->fa = o->fa = n;
			for(; v && v->ch[c] == d; v = v->fa) v->ch[c] = n;
		}
		return lst = o;
	}
}sam;
int main() {
	int n = in();
	LL ans = 0;
	for(int i = 1; i <= n; i++) {
		auto o = sam.extend(in());
		ans += o->len - o->fa->len;
		printf("%lld
", ans);
	}
	return 0;
}