本文主要是介绍G - Parenthesis （CSU - 1809） 湖南省赛平衡串交换（线段树+RMQ），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
找了半天的规律 发现居然是这样。。
- 序列中第 i 个字符是 ‘(‘, pre[i]=pre[i]+1 ;
- 序列中第 i 个字符是 ‘)’, pre[i]=pre[i]−1 ;
这样, 又因为最初的序列是平衡的。当序列不“平衡”当且仅当存在一个数k，使得 pre[k]<0(1≤k≤N) 。
只需要用线段树或者RMQ维护区间最小值。
当将第 a 个字符与第 b 个字符交换（假定 a<b ），如果第 buf[a]=buf[b] 或者是 buf[a]=′)′并且buf[b]=′(′ ，那么交换之后依旧会是“平衡的”。
我们单独考虑 buf[a]=′(′并且buf[b]=′)′ 的情况，这个时候，交换第 a 个字符与第 b 个字符， 将导致区间 [a,b−1] 的前缀和 pre 都要进行区间减 2 ,然后第 pre[b] 加二，[a, b]之外的区间没有影响。所以，如果区间 [a,b−1] 的最小值小于 2 ,那么减 2 之后就会出现负数。也就是说序列会变得“不平衡”。
/*给一个长度为n(<=1e5)的只有()的匹配字符串，q(<=1e5)次询问每次询问在原串上交换两个字符，问交换之后是否还是合法子串如果把(值为1，)值为-1,那么一个区间前缀和不存在<0，并且最终的和为0，肯定就是一个匹配字符串那么交换的两个字符是相同的，肯定是合法的如果交换的是 )(，那么肯定也是合法的如果交换的是()，那么就要考虑[l,r)之间在交换后是否会产生负数,交换的结果是，[l,r)都会-2，那么求[l,r)之间的最小值写个线段树就好了
*/#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e5+5;
char s[maxn];
int pre[maxn],Min[maxn<<2];
int n,q,u,v;void build(int rt,int l,int r){if(l==r){Min[rt]=pre[l];return ;}int mid=(l+r)/2;build(rt*2,l,mid);build(rt*2+1,mid+1,r);Min[rt]=min(Min[rt*2],Min[rt*2+1]);
}int query(int rt,int l,int r,int ql,int qr){if(ql<=l&&qr>=r)return Min[rt];int mid=(l+r)/2;int res=INT_MAX;if(ql<=mid)res=min(res,query(rt*2,l,mid,ql,qr));if(qr>mid)res=min(res,query(rt*2+1,mid+1,r,ql,qr));return res;
}int main(){int n,q,u,v;while(~scanf("%d%d",&n,&q)){getchar();gets(s);for(int i=1;i<=n;i++){if(s[i-1]=='(')pre[i]=1;else pre[i]=-1;pre[i]+=pre[i-1];}build(1,1,n);while(q--){scanf("%d%d",&u,&v);if(u>v)swap(u,v);if(s[u-1]==s[v-1])puts("Yes");else if(s[v-1]=='(')puts("Yes");else{int a=query(1,1,n,u,v-1);if(a>1)puts("Yes");else puts("No");}}}return 0;
}
这篇关于G - Parenthesis （CSU - 1809） 湖南省赛平衡串交换（线段树+RMQ）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
