题解：CF1685C Bring Balance

结论题，下文默认 $n$ 为原题面中的 $2n$。

证明：

将 ( 视作 $1$，) 视作 $-1$，令 $a_i$ 为字符串的前缀和。设 $x$ 为 $a$ 中最大元素所在位置，那么操作 $\left[1,x\right]$ 和 $\left[x+1,n\right]$ 一定满足要求。这一点可以将前缀和取出来计算。

那么只用考虑答案为 $0,1,2$ 的情况，为 $0$ 直接判断初始是不是合法括号序列即可，考虑为 $1$ 的情况如何判断。

假设最左边的 $a_i<0$ 的位置为 $pl$，最右边为 $pr$，那么答案区间 $\left[l,r\right]$ 一定满足 $l\le pl,pr\le r$。

证明：

考虑翻转后括号序列合法性的 check。此时的 $a'_{r - (i-l)}=a_{l-1}+a_r-a_i\geq 0$，也就是说 $a_{l-1}+a_r\geq a_i$。显然 $a_l,a_r\geq 0$（因为可以取 $l=1$，$r=n$），所以当 $a_{l-1}$ 和 $a_r$ 最大的时候一定最优。

因此只需要找到这样的 $l,r$ 判断是否合法即可，不合法就选最大值构造，时间复杂度 $\operatorname{O}(n)$。