[CSP-S 2023] 消消乐

题目

有一个长度为 $n$ 且仅由小写字母构成的字符串。我们称一个字符串是可消除的，当且仅当可以对这个字符串进行若干次操作，使之成为一个空字符串。

其中每次操作可以从字符串中删除两个相邻的相同字符，操作后剩余字符串会拼接在一起。

求这个字符串的所有非空连续子串中，有多少个是可消除的。

$1 \le n \le 2 \times 10^6$ ，且询问的字符串仅由小写字母构成。

题解

令 $f_i$ 为以 $i$ 为结尾的最短的合法串的左端点，用栈 $\mathcal{O}(n)$ 扫一遍。发现扫不全，一些点如左端点本来也可以有它左端点，但这里忽略了。考虑 $l_i$ 表示以 $i$ 为右端点最长合法串的左端点；为了方便统计答案，再设一个 $\text{cnt}_i$ 表示这几个连续的最短合法串的数量。再类似失配指针那样设一个 $\pi_{i,j}$ 表示在以 $i$ 为结尾的这几个连续最短合法串中最后一次把 $j$ 作为右端点的位置。在栈之后再扫一遍就可以扫完。

这样就可以转移完全。

复杂度 $\mathcal{O}(26n)$ 。

代码

const int N = 2e6 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	struct node {
		int pos;
		char val;
	} stk[N];
	int n, f[N], l[N], cnt[N];
	int pos[N][30];
	char s[N];
	int top;
	ll ans;

	int main () {
		n = Read();
		scanf ("%s", s + 1);
		for (int i = 1; i <= n; i++) {
			if (stk[top].val == s[i]) l[i] = f[i] = stk[top].pos, top--, cnt[i] = 1, pos[i][s[i] - 'a'] = i;
			else stk[++top] = (node) {i, s[i]};
		}
		for (int i = 2; i <= n; i++) {
			if (f[i]) {
				if (l[f[i] - 1]) {
					l[i] = l[f[i] - 1], cnt[i] = cnt[f[i] - 1] + 1;
					for (int j = 0; j < 26; j++) 
						pos[i][j] = max(pos[i][j], pos[f[i] - 1][j]);
				}
			} else {
				if (pos[i - 1][s[i] - 'a']) {
					l[i] = f[i] = pos[i - 1][s[i] - 'a'];
					cnt[i] = 1;
					pos[i][s[i] - 'a'] = i;
					if (l[f[i] - 1]) {
						l[i] = l[f[i] - 1], cnt[i] = cnt[f[i] - 1] + 1;
						for (int j = 0; j < 26; j++) 
							pos[i][j] = max(pos[i][j], pos[f[i] - 1][j]);
					}
				} 
			}
			// printf ("%d %d %d\n", f[i], l[i], cnt[i]);
		}

		for (int i = n; i; i--) {
			ans += 1ll * cnt[i];
		}
		printf ("%lld\n", ans);
		return 0;
	}
}

int main () {
	freopen ("game.in", "r", stdin);
	freopen ("game.out", "w", stdout);
	Main::main();
	return 0;
}