题目链接：点我啊╭(╯^╰)╮
题目大意：
给出一个括号序列
s e t set set —— 将给定区间全部转化为指定括号
r e v e r s e reverse reverse —— 将给定区间的括号全部取反
q u e r y query query —— 查询给定区间是否为合法的括号序列
代码思路：
将 （ （ （视为 ? 1 -1 ?1 ， ） ） ）视为 1 1 1
s u m sum sum —— 区间和
r e v rev rev —— 区间取反
m i n v minv minv —— 最小前缀和
m a x v maxv maxv —— 最大前缀和
??
解题思路：
判断一个序列是否为合法序列，只需要判断 s u m sum sum 是否为 0 0 0，同时最大前缀是否小于等于0即可
那么维护前缀在这里就不细说了，关键在于取反
在 p u s h d o w n pushdown pushdown 的时候，必须先处理完赋值的操作，再处理取反的操作
进行取反时，最小前缀和 = = = 最大前缀和 × ? 1 ×-1 ×?1，最大前缀和 = 最小前缀和 × ? 1 ×-1 ×?1
也就是
int a = -maxv[rt], b = -minv[rt];maxv[rt] = max(a, b);minv[rt] = min(a, b);
注意，这里必须要先赋值，后比较，不然直接放到括号里面就会出问题，被这个点坑了几个小时 日
最后在查询的时候，要处理好各个关系量，我看见很多人都是用两个查询，其实只要用一个就好，下面的代码比较简洁（其实也是学习别人的）
核心：线段树维护 括号序列 get!
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = 1000000+10;
char s[maxn], ch[10];
int minv[maxn<<2],maxv[maxn<<2];
int t[maxn<<2],sum[maxn<<2],rev[maxn<<2];void pushup(int rt) {sum[rt] = sum[rt<<1] + sum[rt<<1|1];minv[rt] = min(minv[rt<<1], sum[rt<<1] + minv[rt<<1|1]);maxv[rt] = max(maxv[rt<<1], sum[rt<<1] + maxv[rt<<1|1]);
}void setval(int l,int r,int rt,int c) {t[rt] = c;int len = r-l+1;sum[rt] = len*c;maxv[rt] = max(len*c, 0);minv[rt] = min(len*c, 0);rev[rt] = 0;
}void build(int l,int r,int rt) {t[rt] = rev[rt] = 0;if(l==r) {if(s[l]=='(') setval(l,r,rt,-1);if(s[l]==')') setval(l,r,rt,1);return;}int m = (l+r)>>1;build(lson);build(rson);pushup(rt);
}void reverse(int rt) {if(t[rt]) {t[rt] *= -1;sum[rt] *= -1;rev[rt] = 0;} else {sum[rt] *= -1;rev[rt] ^= 1;}int a = -maxv[rt], b = -minv[rt];maxv[rt] = max(a, b);minv[rt] = min(a, b);
}void pushdown(int l,int r,int rt) {int m = (l+r)>>1;if(t[rt]) {setval(lson,t[rt]);setval(rson,t[rt]);t[rt] = 0;}if(rev[rt]) {reverse(rt<<1);reverse(rt<<1|1);rev[rt] = 0;}
}void update(int L,int R,int C,int l,int r,int rt,int op) {if(L<=l&&r<=R) {if(op) reverse(rt);else setval(l,r,rt,C);return ;}pushdown(l,r,rt);int m = (l+r)>>1;if(L<=m) update(L,R,C,lson,op);if(R>m) update(L,R,C,rson,op);pushup(rt);
}void query(int L,int R,int l,int r,int rt,int& summ,int& maxx) {if(L<=l&&r<=R) {maxx = maxv[rt];summ = sum[rt];return;}pushdown(l,r,rt);int m = (l+r)>>1;int suml=0, sumr=0, maxl=0, maxr=0;if(L<=m) query(L,R,lson,suml,maxl);if(R>m) query(L,R,rson,sumr,maxr);summ = suml + sumr;maxx = max(maxl, suml + maxr);
}int main() {int T, l, r, n, q, cas=1;char str[10];scanf("%d", &T);while(T--) {scanf("%d%s%d", &n, s, &q);build(0,n-1,1);printf("Case %d:\n", cas++);while(q--) {scanf("%s", str);if(str[0]=='s') {scanf("%d%d%s", &l, &r, ch);if(ch[0]=='(') update(l,r,-1,0,n-1,1,0);if(ch[0]==')') update(l,r,1,0,n-1,1,0);}if(str[0]=='r') {scanf("%d%d", &l, &r);update(l,r,0,0,n-1,1,1);}if(str[0]=='q') {scanf("%d%d", &l, &r);int maxx=0, summ=0;query(l,r,0,n-1,1,summ,maxx);if (summ==0 && maxx<=0) puts("YES");else puts("NO");}}puts("");}
}