当前位置: 代码迷 >> 综合 >> 线段树 csu1542 Flipping Parentheses
  详细解决方案

线段树 csu1542 Flipping Parentheses

热度:30   发布时间:2023-12-14 04:02:38.0

题意:先给出一个符合括号匹配的字符串,然后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