UR #25 A

考虑先把所有 * 替成 (，然后这样还不满足前缀非负的肯定不对。

再把 * 替换成 )，这样还不满足后缀非负的也不对。

考虑为什么满足这两个就对了。首先肯定将一段前缀 * 替成 (，后缀替成 )，由于满足两个条件，最终必然有前后缀和非负。再考虑能否满足总和为 0。由于可以有空串，在【* 替成 (】的情况下依次将后缀 * 改成 )，最后奇偶性问题用一个空串解决。

所以问题变成了求 $(x,y)$ 个数使得 $r_y\le x\le y\le l_x$。随便扫描线。倒序枚举 $y$ 即可。

设 $S$ 中有 $l$ 个 $\texttt ($、$r$ 个 $\texttt )$、$s$ 个 $\texttt *$，这个问题的判定等价于：

• 对于 $S$ 的每个前缀有 $l + s \geq r$；
• 对于 $S$ 的每个后缀有 $r + s \geq l$。

如果有能够简洁严谨证明这个结论的，可以 qq 私信我 /kel。

但是无论如何，这个过对拍了，所以我们对于每个 $l$ 可以扫描线出最大的合法 $r$，对于每个 $r$ 同理，转化为经典的二维数点问题。

$\mathcal O(n\log n)$。