首页 > 代码库 > 2016年湖南省第十二届大学生计算机程序设计竞赛---Parenthesis（线段树求区间最值）
2016年湖南省第十二届大学生计算机程序设计竞赛---Parenthesis（线段树求区间最值）
原题链接
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1809
Description
Bobo has a balanced parenthesis sequence P=p1 p2…pn of length n and q questions.
The i-th question is whether P remains balanced after pai and pbi swapped. Note that questions are individual so that they have no affect on others.
Parenthesis sequence S is balanced if and only if:
1. S is empty;
2. or there exists balanced parenthesis sequence A,B such that S=AB;
3. or there exists balanced parenthesis sequence S‘ such that S=(S‘).
Input
The input contains at most 30 sets. For each set:
The first line contains two integers n,q (2≤n≤105,1≤q≤105).
The second line contains n characters p1 p2…pn.
The i-th of the last q lines contains 2 integers ai,bi (1≤ai,bi≤n,ai≠bi).
Output
For each question, output "Yes" if P remains balanced, or "No" otherwise.
Sample Input
4 2(())1 32 32 1()1 2Sample Output
NoYesNoSource
湖南省第十二届大学生计算机程序设计竞赛
题意：给了一个平衡的括号序列s（平衡是指括号匹配正常） 现在q次询问，每次输入两个数a、b 问将s[a] s[b]交换后是否任然平衡，平衡则输出“Yes” 否则输出“No”；
思路：定义数组num[] ，num[i]表示s[1]到s[i]中左括号数减去右括号数的差值，分析可知因为s是平衡括号序列，那么num[i]>=0 令a<b ,那么交换s[a] s[b]后，只对num[a]~num[b-1]产生影响，并且交换后当num[k]<0（a<=k<b）时表示不平衡,而只有s[a]=‘(‘ s[b]=‘)‘ 交换后才可能使num[k]<0 。所以特判当s[a]=‘(‘ s[b]=‘)‘时，用线段树求区间a~b-1的最小值，当最小值小于2时，即交换后不平衡，为什么呢？ s[a]=‘(‘ s[b]=‘)‘交换后num[a]~num[b-1]都减2；
代码如下：
#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>#define eps 1e-8#define maxn 105#define inf 0x3f3f3f3f3f3f3f3f#define IN freopen("in.txt","r",stdin);using namespace std;char s[100005];int num[100005];int a,b; struct Node{ //int l,r; int v;}node[100005*4]; void build(int l,int r,int i){ if(l==r) { node[i].v=num[l]; return; } int mid=(l+r)>>1; build(l,mid,i<<1); build(mid+1,r,i<<1|1); node[i].v=min(node[i<<1].v,node[i<<1|1].v);} void query(int l,int r,int &tmp,int i){ if(l>=a&&r<=b) { tmp=node[i].v; return; } int mid=(l+r)>>1; if(mid>=b) query(l,mid,tmp,i<<1); else if(mid<a) query(mid+1,r,tmp,i<<1|1); else { int tmp2; query(l,mid,tmp,i<<1); query(mid+1,r,tmp2,i<<1|1); tmp=min(tmp,tmp2); }} int main(){ int n,q; while(scanf("%d%d",&n,&q)!=EOF) { scanf("%s",s+1); num[0]=0; for(int i=1;i<=n;i++) { num[i]=num[i-1]; if(s[i]==‘(‘) num[i]++; else num[i]--; } build(1,n,1); while(q--) { scanf("%d%d",&a,&b); if(a>b) swap(a,b); if(s[a]==s[b]||s[a]==‘)‘&&s[b]==‘(‘) puts("Yes"); else { b--; int tmp=99999999; query(1,n,tmp,1); if(tmp<2) puts("No"); else puts("Yes"); } } } return 0;}/**8 8(())(())2 7*/
2016年湖南省第十二届大学生计算机程序设计竞赛---Parenthesis（线段树求区间最值）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。