将左括号看作 $1$，右括号看作 $-1$。

先尝试判定。我们可以通过再次反转区间 $[l,r]$ 来将 $S'$ 还原为 $S$，此时 $S$ 的前缀和（记作 $S_i$）将变为：

$$S_i=\begin{cases} S'_i & \text{if }i<l\\ 2S'_{l-1}-S'_i & \text{if }l\le i\le r\\ S'_i-2(S'_r-S'_{l-1}) & \text{if }r<i \end{cases}$$

因为 $S$ 合法当且仅当 $S$ 的前缀和均非负且 $S_N=0$，于是 $r<i$ 时的 $S_i$ 可以改写为 $S'_i-S'_N$ 而不影响充要性。于是限制只有四条：

• 对 $i<l$，$S'_i\ge 0$；
• 对 $l\le i\le r$，$S'_i\le 2S'_{l-1}$；
• 对 $r<i$，$S'_i-S'_N\ge 0$；
• $S'_N=2(S'_r-S'_{l-1})$，即 $S'_r=S'_{l-1}+\frac{1}{2}S'_N$。

那么判定一个 $S'$ 是否合法就只需要判定是否存在 $[l,r]$ 使得 $S'_i$ 满足上述条件即可。

感觉上第一条和第三条限制是比较好处理的，所以接下来我们将直接讨论 $S'_i$ 与 $S'_i-S'_N$ 内是否存在负数。

两者内部都不存在负数

那么这等价于 $S'$ 已经是一个合法括号串了，取 $[l,r]$ 为空集即可。

计数是平凡的。

其中一者存在负数

不妨假设是 $S'_i$ 中存在负数，另一种情况可以简单的翻转并反转 $S''$ 来计数。

设首次出现负数的位置为 $p$，那么必须有 $l\le p$，且由于 $S'_i-S'_N$ 非负，我们只需考虑第二、四条限制。

同时因为 $S'_i\ge S'_N$ 且存在 $S'_i<0$，所以 $S'_N<0$，因此 $S'_r=S'_{l-1}+\frac{1}{2}S'_N<S'_{l-1}$。

于是若 $S'_r\ge 0$，根据介值定理，我们一定能在 $[l,p)$ 内找到一个符合条件的 $r$，取 $S'_{l-1}$ 为 $[0,p)$ 中 $S'_i$ 的最大值即可保证满足第二条限制；否则若 $S'_{l-1}$ 不是最大值，取一个更大值 $S'_{l'-1}$ 后 $[l,r)$ 内一定也会存在一个符合条件的 $r'$，因此第二条限制也更容易满足。

这就总结出我们的策略：一定是找到 $[0,p)$ 中最大的那个 $S'_{l-1}$，再往后找到第一个 $S'_r$，校验 $[l,r]$ 中的 $i$ 是否都满足 $S'_i\le 2S'_{l-1}$ 即可。

枚举 $p$，左半部分的计数是简单的，只需要记录一下最大前缀和。而 $r$ 要么在 $p$ 之前要么在 $p$ 之后，如果它在 $p$ 之前，就只需要 $S'_r\ge 0$；如果它在 $p$ 之后，就要求 $S'_{p+1\dots r}\le 2S'_{l-1}$，即 $S'_{p+1\dots r}-S'_N\le 2(S'_{l-1}-\frac{1}{2}S'_N)$，并且 $S_r-S'_N=S'_{l-1}-\frac{1}{2}S'_N$，于是枚举 $S'_{l-1}-\frac{1}{2}S'_N$ 后从后往前 dp，状态里记录一下有没有找到 $r$ 即可。

两者内部都存在负数

找到第一个 $-1$ 出现的位置 $p$ 和最后一个 $-1+S'_N$ 出现的位置 $q$。如果 $p\ge q$，那么同时有 $-1-S'_N\ge 0$ 和 $-1+S'_N\ge 0$，矛盾，因此必然有 $p<q$。第一、三条限制等价于 $l<p<q<r$。

欸你发现简单地将 $[0,p)$ 中的最大值作为 $S'_{l-1}$ 行不通了，因为可能找不到对应的 $S'_r$，但是可以发现如果此时找不到 $S'_r$ 就说明 $S'_{l-1}+\frac{1}{2}S'_N>\max S'_{q+1\dots N}$，此时反过来取 $S'_r$ 为 $(q,N]$ 中的最大值就有 $S'_r-\frac{1}{2}S'_N<\max S'_{0\dots p-1}$，于是可以找到对应的 $S'_{l-1}$。所以正着做一遍反着做一遍，然后减掉 $\max S'_{0\dots p-1}+\frac{1}{2}S'_N=\max S'_{q+1\dots N}$ 时算重的部分即可。

剩下的部分就和上一个情况类似了，同样枚举 $p$，右半部分新增一个阶段来记录有没有找到 $q$ 即可。

总时间复杂度 $\Theta(N^3)$。代码可以去翻我的 atc 提交记录。