Codeforces Round #748 Changing Brackets 题解 (Java/C++)

题解

首先，根据题意，我们可以知道括号的方向完全不影响结果。那么很自然的，我们只需要考虑不同类型括号的奇偶性。

于是我们注意到，如果两个相邻的方括号之间有偶数个圆括号（反过来也一样），那么一定不需要任何成本。比如[(((([，中间的4个圆括号可以相互配对。
而我们注意到，如果两个方括号之间有偶数个圆括号，那么这两个方括号的下标的奇偶性一定相反。
相反，如果两个方括号之间有奇数个圆括号，则至少需要1的成本。

于是，奇数位上的方括号数目和偶数位上的方括号应当一一对应，每一处不对应都会需要一次操作。
因此我们用两个前缀和来分别维护区间中奇数位置上的方括号和偶数位置上方括号的数目即可。最后的答案是区间内，奇数位置的方括号和偶数位置的方括号数目的差的绝对值。

代码

Java

C++