题解：CF1685C Bring Balance

· · 题解

CF1685C Bring Balance

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

结论 1：答案一定小于等于 2。

证明：

将 ( 视作 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。

结论 2：存在合法区间 \left[L,R\right] 时 l,r 满足 a_{l-1} 是 \left[0,pl-1\right] 中最大值，a_{r} 是 \left[pr,n\right] 最大值的区间 \left[l,r\right] 一定合法。

证明：

考虑翻转后括号序列合法性的 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)。