本文主要是介绍Contest1002 - HHU ACM 综合训练1 E题 Mouse and Parenthesis（线段树+括号匹配），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给定一个平衡序列（即左右括号完全匹配），询问其中两个位置的括号进行交换后是否仍为平衡序列
思路：看到题目完全想不到用线段树做(微笑）。
首先终于学会了判断括号匹配的方法：(为1，)为-1，依次相加，中间结果不能为负数（即前缀和不为负数）且最后和为0即可完全匹配。
所以听了许多人的讲解我也终于明白这道题怎么做了= =
首先如果两个位置的括号一样并不影响原有平衡，将)括号向右移动也不会影响原有平衡，主要在于（向右移动）向左移动的时候，因为）是-1，（是1，所以)向左移动之后，会导致交换的左右两个位置之间的前缀和都减少2，所以只要找到左右两个位置之间前缀和的最小值，看减去2之后是否为负数即可判断这个括号序列是否仍能完全匹配。
线段树即可以帮助存储一个区间内的前缀最小值，省去了每次遍历需要花费的时间。
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int a[100005];
char c[100005];struct tree{int l;int r;int sum;
}t[100005*4];void build(int l,int r,int num){t[num].l=l;t[num].r=r;t[num].sum=0;if(l==r){t[num].sum=a[r];return;}int mid=(l+r)/2;build(l,mid,num+num);build(mid+1,r,num+num+1);t[num].sum=min(t[num+num].sum,t[num+num+1].sum);
}int query(int l,int r,int num){if(t[num].l==l&&t[num].r==r){return t[num].sum;}int mid=(t[num].l+t[num].r)/2;if(r<=mid)return query(l,r,num+num);else if(l>mid)return query(l,r,num+num+1);else{return min(query(l,mid,num+num),query(mid+1,r,num+num+1));}
}int main(){int cnt;scanf("%d",&cnt); for(int ca=1;ca<=cnt;ca++){int n,m;scanf("%d%d",&n,&m); a[0]=0;scanf("%s",c+1); for(int i=1;i<=n;i++){if(c[i]=='(')a[i]=a[i-1]+1;elsea[i]=a[i-1]-1;}build(1,n,1);printf("Case #%d:\n",ca);while(m--){int l,r;scanf("%d%d",&l,&r); if(c[l]==c[r])printf("Yes\n"); else{if(r<l){int temp=r;r=l;l=temp;}if(c[l]==')')printf("Yes\n"); else{int minx=query(l,r-1,1);if(minx<2)printf("No\n"); elseprintf("Yes\n"); }}}}return 0;
}
这篇关于Contest1002 - HHU ACM 综合训练1 E题 Mouse and Parenthesis（线段树+括号匹配）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
