首页 > 代码库 > 湖南省2016省赛题。1809: Parenthesis 线段树

湖南省2016省赛题。1809: Parenthesis 线段树

2024-08-19 13:44:09   220人阅读

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1809

给定一串平衡的序列，要求交换两个位置之后，问其是否还平衡。

首先要注意到交换的是两个位置，这两个位置没有大小之分，所以要判断是否swap他们，保持相对大小

 

然后如果我们把‘(‘当成是1，把‘)‘当成是-1，那么序列平衡，那么前缀和就是0了。

然后考虑下交换的时候，如果就交换相同的字符，那么肯定是Yes了，如果是‘)‘ 和 ‘(‘，那么也是Yes

因为本来序列就是平衡的，现在这样交换，只不过是把相对位置改了，比如()()，交换2和3，其中和2匹配的1，还是可以看成和交换后的那个字符匹配。

考虑交换的是‘(‘ 和 ‘)‘

因为本来在a位置（字符‘(‘）的时候，前缀和是+1了的，那么现在换了个‘)‘过去，所以[a, b - 1]这段区间的前缀和要-2

[b, lenstr]这段要+2

当然可以更新后，判断前缀和是否为0，+ 中途不能出现负数。

然后注意到只有-2那段区间才会产生负数，所以查询[a, b - 1]（注意相对大小）的最小值，如果小于2就NO了

技术分享 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;

#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#define root 1, n, 1
#define lson L, mid, cur << 1
#define rson mid + 1, R, cur << 1 | 1
int n, q;
const int maxn = 1e5 + 20;
int mi[maxn << 2];
int add[maxn << 2];
char str[maxn];
int pre_sum[maxn];
void pushUp(int cur) {
    mi[cur] = min(mi[cur << 1], mi[cur << 1 | 1]);
}
void build(int L, int R, int cur) {
    if (L == R) {
        mi[cur] = pre_sum[L];
        return;
    }
    int mid = (L + R) >> 1;
    build(lson);
    build(rson);
    pushUp(cur);
}
int query(int begin, int end, int L, int R, int cur) {
    if (L >= begin && R <= end) { //子图
        return mi[cur];
    }
    int mid = (L + R) >> 1;
    int lans = inf;
    int rans = inf;
    if (begin <= mid) {
        lans = query(begin, end, lson);
    }
    if (end > mid) rans = query(begin, end, rson);
    return min(lans, rans);
}
void work() {
    cin >> str + 1;
    for (int i = 1; str[i]; ++i) {
        if (str[i] == ‘(‘) {
            pre_sum[i] = pre_sum[i - 1] + 1;
        } else pre_sum[i] = pre_sum[i - 1] - 1;
    }
    build(root);
    for (int i = 1; i <= q; ++i) {
        int a, b;
        cin >> a >> b;
        if (a > b) swap(a, b);
        if (str[a] == str[b] || str[a] == ‘)‘ && str[b] == ‘(‘) {
            cout << "Yes" << endl;
        } else {
            int MI = query(a, b - 1, root);
//            cout << MI << endl;
            if (MI < 2) {
                cout << "No" << endl;
            } else cout << "Yes" << endl;
        }
    }
}

int main() {
#ifdef local
    freopen("data.txt","r",stdin);
#endif
    IOS;
    while (cin >> n >> q) work();
    return 0;
}
View Code

 

湖南省2016省赛题。1809: Parenthesis 线段树


联系
我们