[CSP-S 2023] 消消乐

给定一个串，它是可消除的，当且仅当存在两个相邻的位置字符相等，并且删去它们后剩下的字符串是可消除的。

如果这个串中出现了多个相邻的位置字符相等呢？我们如何找到删哪个字符能够构成一个可消除字符串呢？

经过简单考虑后不难发现，一个串如果是可消除的，那么第一步删除任意一组相邻相等字符都可以得到一个可消除串。

如果一个串可消除，找出它的任意一组消除方案，其中记与位置 $x$ 一同被删除的是位置 $\hat x$。对于任意一组相邻相等字符 $u,v$（$u<v$），如果 $u=\hat v$，那么在原方案中将“删除 $u,v$”这一步放到最开始做，其余步骤不变，仍然合法；否则不难发现原方案中 $\hat u,\hat v$ 之间（不含端点）的子串一定是内部相互配对，那么我们先消除 $u,v$，在删除 $\hat u,\hat v$ 之间的子串后删除 $\hat u,\hat v$，仍然合法。

所以我们从前往后考察每个位置，并维护一个栈表示已经做完的前缀中未被匹配的字符。如果当前位置和栈顶相等，立即匹配，弹出栈顶；否则压入栈。显然该串可消除当且仅当结束时栈为空。

---

原问题是询问这样的可消除子串有多少个。

可以把每个点都作为起点扫一遍，每当栈为空就统计一次，时间复杂度 $O(n^2)$。

显然我们只能对整个序列扫一次。考虑到一个子串可被消除当且仅当，加入它的第一个位置前，和加入它的最后一个位置后，两个时刻栈相等。对栈进行哈希，每个位置结束后进行统计即可。