此文章可以使用目录功能哟↑(点击上方[+])
CSU Problem 1809 Parenthesis
Accept: 0 Submit: 0
Time Limit: 5 Sec Memory Limit : 128 MB
Problem 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≤10^5,1≤q≤10^5).
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
(())
1 3
2 3
2 1
()
1 2
Sample Output
Yes
No
Hint
Problem Idea
解题思路:
【题意】
给你一串长度为n的已经成功匹配的括号串,q次询问
每次询问,问交换a,b两处的括号,该括号串是否仍能成功匹配
交换操作只对当前询问有效,即下一次询问开始,括号串还是最初给的那个括号串
【类型】
括号匹配,线段树,前缀和
【分析】
显然,对于位置i(?i∈[1,n]),前i个括号中,只有左括号个数≥右括号个数,才能保证括号串成功匹配
我们不妨将左括号记为1,右括号记为?1,记[1,i]的前缀和为sum[i]
那么,我们由上可知,括号串成功匹配?sum[i]≥0(?i∈[1,n])且sum[n]=0
因此,判断一个串是否是正确匹配的,只要去判断条件:sum[i]>=0(?i∈[1,n])且sum[n]=0是否满足即可
回到本题,对于交换a,b两处的括号,分三种情况讨论:
⒈如果ch[a]=ch[b](即,交换的两处同时为'('或同时为')'),那么换了和没换一样,肯定是Yes;
⒉如果ch[a]≠ch[b],但ch[a]=?1(即a处为')'),那么肯定也是Yes,这相当于把sum[i],i∈[a,b?1]区间上的前缀和都+2,想想也知道,本来就已经成功匹配的括号串,还把'('往前挪了,这意味着对于位置i(?i∈[1,n]),左括号个数更多了,那右括号必定能够匹配上;
⒊如果s[a]≠s[b],并且s[a]=1(即a处为'('),那么就要去判断区间[a,b?1]内前缀和的最小值是否≥2,如果是,那么就是Yes,否则就是No
因为对于区间[a,b-1],前缀和不仅少了1(a处的'('往后挪了),还多了-1(b处的')'移到前面来了),总共相当于减少了2
那为了满足"判断一个串是否是正确匹配的"的条件,那交换前该区间[a,b-1]内前缀和的最小值必须≥2
查询区间最小值可以用RMQ,也可以用线段树,前者时间复杂度为O(nlogn+q),后者时间复杂度为O(n+qlogn)
显然此题q和n的范围一致,所以两种做法都可以,本人采用的是线段树
【时间复杂度&&优化】
O(n+qlogn)
题目链接→CSU Problem 1809 Parenthesis
Source Code
/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 100005;
const int M = 2005;
const int inf = 1000000007;
const int mod = 1000003;
struct tree
{int left,right,Min;
}s[4*N];
char ch[N];
int sum[N];
void buildtree(int l,int r,int p)
{s[p].left=l,s[p].right=r;if(l==r){s[p].Min=sum[l];return ;}int mid=(l+r)/2;buildtree(l,mid,p*2);buildtree(mid+1,r,p*2+1);s[p].Min=min(s[p*2].Min,s[p*2+1].Min);
}
int query(int l,int r,int p)
{if(s[p].left==l&&s[p].right==r)return s[p].Min;int mid=(s[p].left+s[p].right)/2;if(l>mid)return query(l,r,p*2+1);if(r<=mid)return query(l,r,p*2);return min(query(l,mid,p*2),query(mid+1,r,p*2+1));
}
int main()
{int n,q,i,a,b;while(~scanf("%d%d",&n,&q)){memset(sum,0,sizeof(sum));scanf("%s",ch+1);for(i=1;ch[i]!='\0';i++)sum[i]=sum[i-1]+(ch[i]=='('?1:-1);buildtree(1,n,1);for(i=0;i<q;i++){scanf("%d%d",&a,&b);if(a>b)swap(a,b);if(ch[a]==ch[b]||ch[b]=='('||query(a,b-1,1)>=2)puts("Yes");elseputs("No");}}return 0;
}