CSU 1809 Parenthesis（线段树前缀和）_在前缀和上的线段树

思路：这种括号的题目有一种经典的套路就是遇到(加一，遇到)减一，这样整个序列最后的前缀和一定是非负的，同样的这里贪心一下就会发现只有把( 和 )交换的时候才会出问题，那么可以用一个线段树或者RMQ维护区间最小值，然后如果交换之后(a,b-1)这个区间有前缀和<2的话那么就是No

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define inf 1e9
int sum[maxn<<2],pre[maxn];
char s[maxn];
void push_up(int i)
{
	sum[i]=min(sum[i<<1],sum[i<<1|1]);
}
void build(int i,int l,int r)
{
	if(l==r)
	{
		sum[i]=pre[l];
		return;
	}
	int mid = (l+r)>>1;
	build(lson);
	build(rson);
	push_up(i);
}
int query(int ql,int qr,int i,int l,int r)
{
	if(ql<=l && qr>=r)
		return sum[i];
	int ans = inf;
	int mid = (l+r)>>1;
	if(ql<=mid)
		ans = min(ans,query(ql,qr,lson));
	if(qr>mid)
		ans = min(query(ql,qr,rson),ans);
	return ans;
 
}
int main()
{
	int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
	{
		scanf("%s",s+1);
		for(int i = 1;i<=n;i++)
			if(s[i]=='(')pre[i]=pre[i-1]+1;
		    else pre[i]=pre[i-1]-1;
		build(1,1,n);
		while(m--)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			if(a>b)swap(a,b);
			if(s[a]==s[b] || (s[a]==')'&&s[b]=='('))
				printf("Yes\n");
			else
			{
				if(query(a,b-1,1,1,n)<2)printf("No\n");
				else
					printf("Yes\n");
			}
		}
	}
}

Description

Input

Output

Sample Input

4 2
(())
1 3
2 3
2 1
()
1 2

Sample Output

No
Yes
No