【LG4070】[SDOI2016]生成魔咒

题面

洛谷

题解

如果我们不用在线输的话，那么答案就是对于所有状态\(i\)

\[\sum (i.len-i.fa.len)
\]

现在我们需要在线询问，那么因为\(SAM\)是在线算法，我们考虑每次的对答案的贡献。

那么产生的贡献就是\(last.len-last.fa.len\)。

与\(yyb\)的对话：

Q:为什么构建自动机时中间过程新加的点不会算到最后答案中呢？

A:不影响答案啊，你在两个len之间断开，对于答案的贡献不变。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <tr1/unordered_map>

using namespace std;

using namespace std::tr1;

inline int gi() {

    register int data = 0, w = 1;

    register char ch = 0;

    while (!isdigit(ch) && ch != '-') ch = getchar();

    if (ch == '-') w = -1, ch = getchar();

    while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();

    return w * data;

}

const int MAX_N = 1e5 + 5;

struct Node {

	unordered_map<int, int> ch;

	int len, fa;

} t[MAX_N << 1];

int tot = 1, lst = 1;

long long ans = 0;

void extend(int c) {

	int New = ++tot;

	t[lst].ch[c] = New;

	t[New].len = t[lst].len + 1;

	int p = t[lst].fa; lst = tot;

	while (p && t[p].ch.find(c) == t[p].ch.end()) t[p].ch[c] = New, p = t[p].fa;

	if (!p) t[New].fa = 1;

	else {

		int q = t[p].ch[c];

		if (t[q].len == t[p].len + 1) t[New].fa = q;

		else {

			int _q = ++tot; t[_q] = t[q];

			t[New].fa = t[q].fa = _q, t[_q].len = t[p].len + 1;

			while (p) {

				unordered_map<int, int> :: iterator ite;

				ite = t[p].ch.find(c);

				if (ite == t[p].ch.end() || ite->second != q) break;

				t[p].ch[c] = _q;

				p = t[p].fa;

			}

		}

	}

	ans += t[New].len - t[t[New].fa].len;

} 

int main () {

#ifndef ONLINE_JUDGE

    freopen("cpp.in", "r", stdin);

#endif

	int N = gi();

	for (int i = 1; i <= N; i++) extend(gi()), printf("%lld\n", ans);

    return 0;

}

巴特西

【LG4070】[SDOI2016]生成魔咒

【LG4070】[SDOI2016]生成魔咒

题面

题解

代码

最新文章

热门文章