HEAT OJ #39. 【2020.9.3 NOIP模拟赛 T3】C

题意简述

给一长为 (10^6) 的字符串，求有多少子串能够看作合法括号序列（要求配对的“括号”字母相同）。

题解

模拟赛的重大失误 给了70还是很不错的，总比写挂爆零强

首先看到括号序列要想栈，能配对尽可能配对，这样就可以做到 (O(n^2)) 了。

现在我们换一种思路，对于每一个前缀，找合法后缀个数。显然我们可以设 (f(i)) 表示以 (i) 为结尾的合法后缀个数，那么 (f(i) = f(p) + 1)，其中 (p) 表示最靠后的那个合法位置。若能快速求 (p)，即可 (O(n)) DP。

我们现在的问题是，求 (g(i,c))（在 (i) 及之前的第一个 (c) 在合法位置出现的 (c) 的位置），求出后就可以通过 (g(i-1,s_i)) 确定 (p) 了。考虑如何推 (g(i,c))，“合法”即那个位置之后的部分可以被看作合法括号序列，显然这样的位置是具有传递性的，我们可以直接从上一个第一个合法的位置直接复制过来。而上一个第一个合法的位置可以通过 (p) 求。

代码：

for (register int i = 1; i <= n; ++i) {
  int c = s[i] - 'a', pre = g[i - 1][c] - 1;
  g[i][c] = i;
  if (pre < 0)  continue;
  f[i] = f[pre] + 1;
  ans += f[i];
  memcpy(g[i], g[pre], sizeof(g[pre]));
  g[i][c] = i;
}

明明这种题我去年CSP还会呢怎么现在不会了kk