CSU 1809 Parenthesis（线段树+前缀和）

2023-08-30 18:10:09

Parenthesis

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:

S is empty;
or there exists balanced parenthesis sequence A,B such that S=AB;
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

【题目链接】CSU 1809 Parenthesis

【题目类型】线段树+前缀和

&题意：

给了一个平衡的括号序列s（平衡是指括号匹配正常）现在q次询问，每次输入两个数a、b;问将s[a]和s[b]交换后是否仍然平衡（即是否正常匹配）平衡则输出“Yes”，否则输出“No”

&题解：

这种括号的题目有一种经典的套路就是遇到'('加一，遇到')'减一，这样整个序列最后的前缀和一定是非负的，同样的这里贪心一下就会发现只有把'(' 和')'交换的时候才会出问题，这时我们就要想一下了，有了括号的套路，你只给一个数组赋值正负一是没什么意义的，所以你要求他的前缀和，放在pre数组中，这样假设每次修改的区间是u，v，也就是只有当s[u] == '(' && s[v] == ')'才需要判断，且u<=v，那么要判断什么呢？你想，正确情况下他的pre是不会有<0的情况的，但如果换了之后，前面u的位置换成了'('就要减1，后面v的位置是加1的，所以不用管，这时候pre在区间[u,v-1]的最小值>=2才可以。

【时间复杂度】O(nlogn)

&代码：

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

#define SII(N,M) scanf("%d %d",&(N),&(M))

#define rep(i,b) for(int i=0;i<(b);i++)

#define rez(i,a,b) for(int i=(a);i<=(b);i++)

const int MAXN = 100000 + 5 ;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

int sum[MAXN << 2], pre[MAXN];

inline void Pushmin(int rt) {

	sum[rt] = min(sum[rt << 1], sum[rt << 1 | 1]);

}

void Build(int l, int r, int rt) {

	if (l == r) {

		sum[rt] = pre[l];

		return;

	}

	int m = (l + r) >> 1;

	Build(lson);

	Build(rson);

	Pushmin(rt);

}

int Query(int L, int R, int l, int r, int rt) {

	if (L <= l && r <= R) {

		return sum[rt];

	}

	int m = (l + r) >> 1;

	int ans = INF;

	if (L <= m)

		ans = min(ans, Query(L, R, lson));

	if (R > m)

		ans = min(ans, Query(L, R, rson));

	return ans;

}

int n, q;

char s[MAXN];

void Solve() {

	while (~SII(n, q)) {

		scanf("%s", s + 1);

		rez(i, 1, n) if (s[i] == '(') pre[i] = pre[i - 1] + 1;

		else  pre[i] = pre[i - 1] - 1;

		Build(1, n, 1);

		rep(i, q) {

			int u, v;

			SII(u, v);

			if (v < u) swap(u, v);

			if (s[u] == '(' && s[v] == ')') {

				int d = Query(u, v - 1, 1, n, 1);

				if (d < 2) puts("No");

				else puts("Yes");

			}

			else puts("Yes");

		}

	}

}

int main() {

	Solve();

	return 0;

}

码农公寓