题意:先给出一个符合括号匹配的字符串,然后Q次操作
每次操作将某个括号反转,问将哪个括号反转能使字符串的括号再次匹配,位置要越靠近左端越好
假如(表示数字1,)表示数字-1,A[i]表示前i个括号代表的数字之和
((()))代表的数组A就是1 2 3 2 1 0
那么这些数字会有什么用呢,,我们可以来找下规律
如果是将(变成),如上面那个字符串的第2个反转,就会得到()())),对应的A数组是1 0 1 0 -1 -2
可以发现,反转后是以前的数组,在反转的位置t到n整个区间段的数字都减少了2
如果将)变成(,同理会得到,反转后在反转的位置到n整个区间段的数字都增加了2
所以我们可以得到一个这样的决策:
设反转的位置是t
若位置t是(,找到第一个),将)变成(,因为会使后面所有的数字都增加2,所以这样一定是最优的
若位置t是),找到一个位置p,使得[p+1,n]的所有数字都>=2,然后将p+1的括号反转,这样就会让后面的数字都减少2,就还原了
第一种情况可以用set维护,也可以利用F=A[i]-l的值去维护,如果[1,i]区间内存在),那么A[i]-l会小于0
第二种情况明显可以用线段树去维护最小值,然后通过最小值去定位
#include<cstdio>
#include<cmath>
#include<cstring>
#include