自动搬运

查看原文

来自洛谷，原作者为

	A7F3jK9pR0xf_ DFS = Dead Fat Sheep |百万罚时过大江

搬运于2025-08-24 23:14:12，当前版本为作者最后更新于2025-08-14 18:20:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

红题。不知为何评绿？

先对每个字符做前缀和，令 $s1_{i,j}$ 为前 $i$ 个字符中出现小写字母表第 $j+1$ 个字符的数量。这一步可以 $O(|\sum|n)$ 处理，其中 $\sum$ 是字符集。

接着用栈进行括号匹配，具体为：

• 若 $s_i$ 为 ( 则将 $i$ 入栈
• 若 $s_i$ 为 ) 则将栈顶取出并删除栈顶

设每次取出栈顶元素为 $cur$，那么 $s_{cur}$ 与 $s_i$ 组成一对匹配的括号。此时小写字母表第 $j+1$ 个字符在这对括号中间出现的次数为 $s1_{i-1,j}-s1_{cur,j}$，我们可以建一个桶 $s2_{i,j}$ 来存储小写字母表第 $j+1$ 个字符 恰好 出现 $i$ 次的括号对数量，那么每算出一个括号对我们就对 $s2$ 数组 $O(|\sum|)$ 维护。

计算完 $s2$ 数组后，不难发现每次所求答案即为 $\sum_{i=x}^ns2_{i,c-'a'}$，那么我们对 $s2$ 做一次后缀和即可。这一步的复杂度依旧是 $O(|\sum|n)$，总复杂度为 $O(|\sum|n)$，注意 $x$ 可能取 $0$ 所以后缀和要做到下标 $0$。

代码很好写。