题目大意：对于一个括号序列，有两种操作。set操作：将区间内的数置同；reverse:将区间内的数取反。对于每个询问，判断该区间的括号是否匹配。
思路：数据规模100000,要在O(logn)或者O(1)内完成操作，线段树维护信息和查询。
对于每个询问，需要O（1）的判断括号是否匹配：将‘（’看做-1，‘）’看做1，从左到右扫一遍，记录连续和最大值，和整个区间的和，只要 区间和==0 && 连续和最大值<=0，则括号匹配。
但是有一个问题：当reverse的操作做完之后，无法在O(1)的时间内更新区间连续和的最大值，因为该最大值恰巧是未操作之前的区间连续和最小值。所以线段树还要维护这个信息。
看看线段树维护的信息：区间和sum，区间连续和最大值mx，区间连续和最小值mi，reverse操作的懒惰标记，set操作的懒惰标记
PS：对于两个懒惰标记的处理，可能是个人原因，我搜到的程序自己看的不大懂，所以自己写了一个很一般的程序。或许是数据比较弱，感觉自己写的可能会有BUG，希望如果读到有错误的地方，予以指正。
对于更新set操作，当他遇到reverse的懒惰标记的时候，可以完全将该标记覆盖，因为无论前面的操作对数列有什么影响，set操作把它们全变成同一个数。对于更新reverse操作，当他遇到set懒惰标记时，实际上的功用就是将set懒惰标记的值变为相反数（想想为什么），比如set标记的值为1，就是将该区间全变为1，想在有个revers操作，不就是将该区间全变为-1么，将1改为-1就ok。还有就是，当他遇到reverse懒惰标记的时候，取个异或值，因为对一个区间做两次reverse操作，相当于什么也没做。
这样做的时候，其实不会出现在同一个区间，reverse懒惰标记和set懒惰标记同时出现。也就是说，两者只会出现一个。(这一块儿就是我看别人的代码看不懂的地方，别人都是两个一块儿考虑的)
更新操作：父亲->sum=左儿子->sum + 右儿子->sum;
父亲->mx=max ( 左儿子->mx,左儿子->sum + 右儿子->mx);
父亲->mi=min ( 左儿子->mi,左儿子->sum + 右儿子->mi);
reverse操作: mx=-mi; mi=-mx; sum=-sum;
#include <iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
using namespace std;
const int maxn=100000+10;
struct Node
{
int l,r;
int sum;
int mx,mi;
int lz_r,lz;//lz_r是reverse操作的懒惰标记，lz是set操作的懒惰标记
}node[maxn << 2];
char s[maxn];
int v[maxn];
void push_up(int p,int ls,int rs)
{
node[p].sum=node[ls].sum+node[rs].sum;
node[p].mx=max(node[ls].mx,node[rs].mx+node[ls].sum);
node[p].mi=min(node[ls].mi,node[rs].mi+node[ls].sum);
}
void push_down(int p,int ls,int rs)//结点，左儿子，右儿子
{
if(node[p].lz!=0)//如果该区间有set的懒惰标记
{
node[ls].sum=(node[ls].r-node[ls].l+1)*node[p].lz;
node[ls].mi=min(node[p].lz,node[ls].sum);
node[ls].mx=max(node[p].lz,node[ls].sum);
node[ls].lz=node[p].lz;
if(node[ls].lz_r!=0)node[ls].lz_r=0;//lz向左右传递的时候顺便覆盖之前reverse懒惰标记的值
node[rs].sum=(node[rs].r-node[rs].l+1)*node[p].lz;
node[rs].mi=min(node[p].lz,node[rs].sum);
node[rs].mx=max(node[p].lz,node[rs].sum);
node[rs].lz=node[p].lz;
if(node[rs].lz_r!=0)node[rs].lz_r=0;
node[p].lz=0;//释放该节点的标记值
}
else if(node[p].lz_r!=0)//如果有reverse懒惰标记
{
node[ls].sum=-node[ls].sum;
int temp=node[ls].mi;
node[ls].mi=-node[ls].mx;
node[ls].mx=-temp;
if(node[ls].lz!=0)//将set懒惰标记置反，同时reverse标记清零
{
node[ls].lz=-node[ls].lz;
node[ls].lz_r=0;
}
else node[ls].lz_r^=1;//如果遇到reverse标记，取异或值
node[rs].sum=-node[rs].sum;
temp=node[rs].mi;
node[rs].mi=-node[rs].mx;
node[rs].mx=-temp;
if(node[rs].lz!=0)
{
node[rs].lz=-node[rs].lz;
node[rs].lz_r=0;
}
else node[rs].lz_r^=1;
node[p].lz_r=0;
}
}
void make_tree(int p,int a,int b)//建树区间1~n，所以操作的时候区间端点加1
{
node[p].l=a;node[p].r=b;
node[p].lz=node[p].lz_r=0;
if(a==b)
{
node[p].sum=node[p].mi=node[p].mx=v[a];
return;
}
int ls=p << 1,rs=ls+1;
int mid=(node[p].l+node[p].r) >> 1;
make_tree(ls,a,mid);
make_tree(rs,mid+1,b);
push_up(p,ls,rs);
}
void modify_set(int p,int a,int b,int x)//set操作
{
if(node[p].l==a && node[p].r==b)//如果找到该区间
{
node[p].sum=(b-a+1)*x;
node[p].mi=min(x,node[p].sum);
node[p].mx=max(x,node[p].sum);
node[p].lz=x;
if(node[p].lz_r!=0)node[p].lz_r=0;//将reverse的标记覆盖
return;
}
int ls=p << 1,rs=ls+1;
int mid=(node[p].l+node[p].r) >> 1;
push_down(p,ls,rs); //向下释放懒惰标记
if(b<=mid)modify_set(ls,a,b,x);
else if(a>=mid+1)modify_set(rs,a,b,x);
else
{
modify_set(ls,a,mid,x);
modify_set(rs,mid+1,b,x);
}
push_up(p,ls,rs);
}
void modify_rev(int p,int a,int b)//reverse操作
{
if(node[p].l==a && node[p].r==b)
{
node[p].sum=-node[p].sum;
int temp=node[p].mi;
node[p].mi=-node[p].mx;
node[p].mx=-temp;
if(node[p].lz!=0)//改变set标记
{
node[p].lz=-node[p].lz;
node[p].lz_r=0;
}
else//或者与之前的reverse操作取异或值
{
node[p].lz_r^=1;
}
return;
}
int ls=p << 1,rs=ls+1;
int mid=(node[p].l+node[p].r) >> 1;
push_down(p,ls,rs);
if(b<=mid)modify_rev(ls,a,b);
else if(a>=mid+1)modify_rev(rs,a,b);
else
{
modify_rev(ls,a,mid);
modify_rev(rs,mid+1,b);
}
push_up(p,ls,rs);
}
int query_sum(int p,int a,int b)
{
if(node[p].l==a && node[p].r==b)
{
return node[p].sum;
}
int ls=p << 1,rs=ls+1;
int mid=(node[p].l+node[p].r) >> 1;
push_down(p,ls,rs);
if(b<=mid)return query_sum(ls,a,b);
else if(a>=mid+1)return query_sum(rs,a,b);
else return query_sum(ls,a,mid)+query_sum(rs,mid+1,b);
}
int query_max(int p,int a,int b)
{
if(node[p].l==a && node[p].r==b)
{
return node[p].mx;
}
int ls=p << 1,rs=ls+1;
int mid=(node[p].l+node[p].r) >> 1;
push_down(p,ls,rs);
if(b<=mid)return query_max(ls,a,b);
else if(a>=mid+1)return query_max(rs,a,b);
else return max(query_max(ls,a,mid),query_sum(ls,a,mid)+query_max(rs,mid+1,b));
//一定是左区间的和+右区间的max值，wa了2次
}
void convert(char *s,int n)//转换成数组
{
for(int i=0;i<n;i++)
{
if(s[i]=='(')v[i+1]=-1;
else v[i+1]=1;
}
}
int main()
{
int t,n,m,a,b;
char ss[10],ch[2];
//freopen("in","r",stdin);
scanf("%d",&t);
for(int kk=1;kk<=t;kk++)
{
printf("Case %d:\n",kk);
scanf("%d",&n);
scanf("%s",s);
convert(s,n);
make_tree(1,1,n);
scanf("%d",&m);
while(m--)
{
scanf("%s",ss);
if(ss[0]=='s')
{
scanf("%d %d %s",&a,&b,ch);
int ans=ch[0]=='('?-1:1;
modify_set(1,a+1,b+1,ans);
}
else if(ss[0]=='r')
{
scanf("%d %d",&a,&b);
modify_rev(1,a+1,b+1);
}
else if(ss[0]=='q')
{
scanf("%d %d",&a,&b);a++;b++;
int ans_sum=query_sum(1,a,b);
int ans_max=query_max(1,a,b);
if(ans_sum==0 && ans_max<=0)printf("YES\n");
else printf("NO\n");
}
}
printf("\n");
}
return 0;
}