首页 > 代码库 > 湖南省第十二届大学生计算机程序设计竞赛 G Parenthesis
湖南省第十二届大学生计算机程序设计竞赛 G Parenthesis
1809: Parenthesis
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
NoYesNoHINT
题意：
给你长度n的合法括号匹配和q个询问
每次询问你 交换ai,bi两个位置的符号，交换后是否还是合法的
题解：
分块
（转化为1，）转化为-1
合法括号序列满足前缀和永远大于等于0
利用这个每次修改两个位置
维护这个关系就好了
分块可过的
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>using namespace std; #pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pair typedef long long LL;const long long INF = 1e18;const double Pi = acos(-1.0);const int N = 2e5+10, M = 1e6+11, mod = 1e6+3, inf = 5000; int block,n,q,m;int sum[N],pos[N],mi[N],a[N],b[N],add[N],f[N];char ch[N];void init() { int s = 0; pos[0] = 0; memset(b,0,sizeof(b)); memset(sum,0,sizeof(sum)); memset(add,0,sizeof(add)); for(int i = 1; i <= n; ++i) b[i] = a[i]; for(int i = 1; i <= n; ++i) sum[i] = sum[i-1] + b[i]; for(int i = 0; i < N; ++i) mi[i] = inf; for(int i = 1; i <= n; ++i) { if(pos[i] != pos[i-1]) s = 0; s += b[i]; mi[pos[i]] = min(mi[pos[i]],s); } for(int i = 1; i <= n; ++i) add[pos[i]] += b[i]; f[0] = 1; s = 0; for(int i = 1; i <= n; ++i) { s+=b[i]; if(s < 0) f[i] = 0; else f[i] = f[i-1]; }}int solve(int l,int r) { int OK = 1; swap(b[l],b[r]); if(pos[l] == pos[r]) { int s = sum[block * (pos[l]-1)]; for(int i = block * (pos[l]-1) + 1; i <= min(pos[l] * block,n); ++i) { s += b[i]; if(s < 0) OK = 0; } for(int i = pos[l]+1; i <= m; ++i) { if(s + mi[i] < 0) OK = 0; s += (add[i]); }if(s < 0) OK = 0; } else { int s = sum[block * (pos[l]-1)]; for(int i = block*(pos[l]-1) + 1; i <= min(pos[l] * block,n); ++i) { s += b[i]; if(s < 0) OK = 0; } for(int i = pos[l]+1; i <= pos[r]-1; ++i) { if(s + mi[i] < 0) OK = 0; s += (add[i]); } for(int i = block * (pos[r]-1) + 1; i <= min(pos[r]*block,n); ++i) { s += b[i]; if(s < 0) OK = 0; } for(int i = pos[r]+1; i <= m; ++i) { if(s + mi[i] < 0) OK = 0; s += (add[i]); } } swap(b[l],b[r]); if(OK == 1) return 1; else return 0;}int main() { while(scanf("%d%d",&n,&q)!=EOF) { scanf("%s",ch); block = int(sqrt(n)); memset(a,0,sizeof(a)); memset(pos,0,sizeof(pos)); for(int i = 1; i <= n; i++) {if(ch[i-1] == ‘(‘) a[i] = 1; else a[i] = -1; pos[i]=(i-1)/block+1;} if(n%block) m = n/block + 1; else m = n/block; init(); for(int i = 1; i <= q; ++i) { int l,r; scanf("%d%d",&l,&r); if(l > r) swap(l,r); if(solve(l,r) == 1) printf("Yes\n"); else printf("No\n"); } } return 0;}
湖南省第十二届大学生计算机程序设计竞赛 G Parenthesis
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。