学步园

大意略。

思路：更新、查询比较好实现，关键是如何去判断左右括号是合法的序列呢？我参考了网上的思路，即把'('看做-1，')'看做1，只要询问区间总和为0，且区间连续最大和的值小于等于0，则说明该序列合法。

区间连续最大和的状态更新：

sumv[o] = sumv[lc]+sumv[rc];

maxv[o] = max(maxv[lc], sumv[lc]+maxv[rc]); 

minv[o] = min(minv[lc], sumv[lc]+minv[rc]);

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;

const int maxn = 100010;

#define lc o*2
#define rc o*2+1

int n, m;
char str[maxn+10];

int cover[maxn<<2], XOR[maxn<<2];

int sumv[maxn<<2], maxv[maxn<<2], minv[maxn<<2];

void FXOR(int o) //异或操作 
{
	if(cover[o] != 0) cover[o] = -cover[o];
	else XOR[o] ^= 1;
}

void pushup(int o) //区间从左往右连续最大值，要么是左边连续最大和，要么是左边总和与右边连续最大和相加。
{
	sumv[o] = sumv[lc] + sumv[rc];
	maxv[o] = max(maxv[lc], sumv[lc] + maxv[rc]);
	minv[o] = min(minv[lc], sumv[lc] + minv[rc]);
}

void pushdown(int o, int m)
{
	int temp;
	if(cover[o] != 0) //存在覆盖标记 
	{
		cover[lc] = cover[rc] = cover[o];
		sumv[lc] = cover[o] * (m-(m>>1));
		sumv[rc] = cover[o] * (m>>1);
		maxv[lc] = max(-1, sumv[lc]);
		maxv[rc] = max(-1, sumv[rc]);
		minv[lc] = min(1, sumv[lc]);
		minv[rc] = min(1, sumv[rc]);
		XOR[lc] = XOR[rc] = 0;
		cover[o] = 0;
	}
	if(XOR[o]) //如果存在异或标记，总和取反，最大值变为最小值的相反数，最小值类似。 
	{
		FXOR(lc), FXOR(rc);
		sumv[lc] = -sumv[lc];
		sumv[rc] = -sumv[rc];
		
		temp = maxv[lc];
		maxv[lc] = -minv[lc];
		minv[lc] = -temp;
		
		temp = maxv[rc];
		maxv[rc] = -minv[rc];
		minv[rc] = -temp;
		
		XOR[o] = 0;
	}
}

void build(int o, int L, int R)
{
	cover[o] = XOR[o] = 0;
	if(L == R)
	{
		if(str[L] == '(') { sumv[o] = maxv[o] = minv[o] = -1; }
		else { sumv[o] = maxv[o] = minv[o] = 1; }
		return ;
	}
	int M = L + (R-L)/2;
	build(lc, L, M);
	build(rc, M+1, R);
	pushup(o);
}

void update(int o, int y1, int y2, int L, int R, char op)
{
	if(y1 <= L && y2 >= R)
	{
		if(op == '(')
		{
			cover[o] = -1;
			maxv[o] = -1, minv[o] = -(R-L+1);
			sumv[o] = -(R-L+1);
			XOR[o] = 0;
		}
		else if(op == ')')
		{
			cover[o] = 1;
			maxv[o] = R-L+1, minv[o] = 1;
			sumv[o] = R-L+1;
			XOR[o] = 0;
		}
		else if(op == 'r') //取反 
		{
			FXOR(o);
			sumv[o] = -sumv[o];
			int temp = maxv[o];
			maxv[o] = -minv[o];
			minv[o] = -temp;
		}
		return ;
	}
	pushdown(o, R-L+1);
	int M = L + (R-L)/2;
	if(y1 <= M) update(lc, y1, y2, L, M, op);
	if(y2 > M) update(rc, y1, y2, M+1, R, op);
	pushup(o);
}

int query1(int o, int y1, int y2, int L, int R)
{
	if(y1 <= L && y2 >= R) return sumv[o];
	int ans = 0, M = L + (R-L)/2;
	pushdown(o, R-L+1);
	if(y1 <= M) ans += query1(lc, y1, y2, L, M);
	if(y2 > M) ans += query1(rc, y1, y2, M+1, R);
	//pushup(o);
	return ans;
}

int query2(int o, int y1, int y2, int L, int R) //定义变量为a, b, c,就错了，我嘞个去。 
{
	if(y1 <= L && y2 >= R) return maxv[o];
	int ans = 0, M = L + (R-L)/2;
	pushdown(o, R-L+1);
	//int a = query2(lc, y1, y2, L, M), b = query1(lc, y1, y2, L, M), c = query2(rc, y1, y2, M+1, R);
	if(y2 <= M) ans = query2(lc, y1, y2, L, M); //区间全在左边 
	else if(y1 > M) ans = query2(rc, y1, y2, M+1, R); //区间全在右边 
	else ans = max(query2(lc, y1, y2, L, M), query1(lc, y1, y2, L, M)+query2(rc, y1, y2, M+1, R)); //中间 
	//pushup(o);
	return ans;
}

void read_case()
{
	scanf("%d%s%d", &n, str, &m);
	build(1, 0, n-1);
}

void solve()
{
	read_case();
	char op[20];
	int y1, y2;
	while(m--)
	{
		scanf("%s", op);
		if(op[0] == 's')
		{
			scanf("%d%d%s", &y1, &y2, op);
			update(1, y1, y2, 0, n-1, op[0]);
		}
		else if(op[0] == 'r')
		{
			scanf("%d%d", &y1, &y2);
			update(1, y1, y2, 0, n-1, op[0]);
		}
		else
		{
			scanf("%d%d", &y1, &y2);
			if((y2-y1) & 1)
			{
				int o1, t2;
				o1 = query1(1, y1, y2, 0, n-1), t2 = query2(1, y1, y2, 0, n-1);
				if(o1 == 0 && t2 <= 0) printf("YES\n");
				else printf("NO\n");
			}
			else printf("NO\n");
		}
	}
	printf("\n");
}

int main()
{
	int T, times = 0;
	scanf("%d", &T);
	while(T--)
	{
		printf("Case %d:\n", ++times);
		solve();
	}
	return 0;
}