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 3
2 3
2 1
()
1 2
Sample Output
No
Yes
No
HINT
题意：
给你长度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+, M = 1e6+, mod = 1e6+, inf = ; 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 = ;
pos[] = ;
memset(b,,sizeof(b));
memset(sum,,sizeof(sum));
memset(add,,sizeof(add));
for(int i = ; i <= n; ++i) b[i] = a[i];
for(int i = ; i <= n; ++i) sum[i] = sum[i-] + b[i];
for(int i = ; i < N; ++i) mi[i] = inf;
for(int i = ; i <= n; ++i) {
if(pos[i] != pos[i-]) s = ;
s += b[i];
mi[pos[i]] = min(mi[pos[i]],s);
}
for(int i = ; i <= n; ++i) add[pos[i]] += b[i];
f[] = ;
s = ;
for(int i = ; i <= n; ++i) {
s+=b[i];
if(s < ) f[i] = ;
else f[i] = f[i-];
}
}
int solve(int l,int r) {
int OK = ;
swap(b[l],b[r]);
if(pos[l] == pos[r]) {
int s = sum[block * (pos[l]-)];
for(int i = block * (pos[l]-) + ; i <= min(pos[l] * block,n); ++i) {
s += b[i];
if(s < ) OK = ;
}
for(int i = pos[l]+; i <= m; ++i) {
if(s + mi[i] < ) OK = ;
s += (add[i]);
}if(s < ) OK = ;
} else {
int s = sum[block * (pos[l]-)];
for(int i = block*(pos[l]-) + ; i <= min(pos[l] * block,n); ++i) {
s += b[i];
if(s < ) OK = ;
}
for(int i = pos[l]+; i <= pos[r]-; ++i) {
if(s + mi[i] < ) OK = ;
s += (add[i]);
}
for(int i = block * (pos[r]-) + ; i <= min(pos[r]*block,n); ++i) {
s += b[i];
if(s < ) OK = ;
}
for(int i = pos[r]+; i <= m; ++i) {
if(s + mi[i] < ) OK = ;
s += (add[i]);
}
}
swap(b[l],b[r]);
if(OK == ) return ;
else return ;
}
int main() {
while(scanf("%d%d",&n,&q)!=EOF) {
scanf("%s",ch);
block = int(sqrt(n));
memset(a,,sizeof(a));
memset(pos,,sizeof(pos));
for(int i = ; i <= n; i++) {if(ch[i-] == '(') a[i] = ; else a[i] = -; pos[i]=(i-)/block+;}
if(n%block) m = n/block + ; else m = n/block;
init();
for(int i = ; i <= q; ++i) {
int l,r;
scanf("%d%d",&l,&r);
if(l > r) swap(l,r);
if(solve(l,r) == ) printf("Yes\n");
else printf("No\n");
}
}
return ;
}