2021第十二届蓝桥杯国赛-I翻转括号序列

题面

官网链接

c语言网

【问题描述】

给定一个长度为 $n$ 的括号序列，要求支持两种操作：

1. 将 $[L_i , R_i]$ 区间内（序列中的第 $L_i$ 个字符到第 $R_i$ 个字符）的括号全部翻转（左括号变成右括号，右括号变成左括号）。
2. 求出以 $L_i$ 为左端点时，最长的合法括号序列对应的 $R_i$ （即找出最大的 $R_i$ 使 $[L_i, R_i]$ 是一个合法括号序列）。

【输入格式】

输入的第一行包含两个整数 $n, m$，分别表示括号序列长度和操作次数。

第二行包含给定的括号序列，括号序列中只包含左括号和右括号。

接下来 $m$ 行，每行描述一个操作。如果该行为 “$1\ L_i\ R_i$”，表示第一种操作，区间为 $[L_i, R_i]$；如果该行为 “$2\ L_i$” 表示第二种操作，左端点为 $L_i$。

【输出格式】

对于每个第二种操作，输出一行，表示对应的 $R_i$。如果不存在这样的 $R_i$， 请输出 $0$。

【样例输入】

7 5
((())()
2 3
2 2
1 3 5
2 3
2 1

【样例输出】

4
7
0
0

【评测用例规模与约定】

对于 20% 的评测用例，$n, m ≤ 5000$；

对于 40% 的评测用例，$n, m ≤ 30000$；

对于 60% 的评测用例，$n, m ≤ 100000$；

对于所有评测用例，$1 ≤ n ≤ 10^6, 1 ≤ m ≤ 2 × 10^5$。

思路

将左括号看成 +1，右括号看成 -1，统计前缀其和 s，则对于一个合法的括号序列 $[l, r]$ 需要满足一下两点：

• $s[r] = s[l - 1]$
• $\forall i \in [l, r], s[i] \ge s[l-1]$

1. 暴力骗分，43% 样例（C语言网）
2. 线段树（本人写的垃圾线段树），52% 样例（C语言网），100% 样例（官网，数据有点水）

代码

暴力

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
int n, m, a[N];
char s[N];

int main() {
    cin >> n >> m;
    scanf("%s", s + 1);
    for (int i = 1; i <= n; i++) a[i] = (s[i] == '(' ? 1 : -1);
    int op, l, r;
    while (m--) {
        scanf("%d%d", &op, &l);
        if (op == 1) {
            scanf("%d", &r);
            if (l > r) swap(l, r);
            for (int i = l; i <= r; i++) a[i] *= -1;
        } else {
            int t = 0;
            int k = 0;
            for (int i = l; i <= n; i++) {
                t += a[i];
                if (t == -1) break;
                if (t == 0) k = i;
            }

            printf("%d\n", k);
        }
    }
    return 0;
}

垃圾线段树

#include<bits/stdc++.h>

using namespace std;

#define frein freopen("G:\\C++\\algo\\data\\in.txt", "r", stdin)
#define freout freopen("G:\\C++\\algo\\data\\out.txt", "w", stdout)
#define sync ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define gcd __gcd
#define pb push_back
#define fi first
#define se second
#define lowbit(x) (x & -x)
#define fir(i, a, b) for(int i = a; i <= b; i++)
#define rif(i, b, a) for(int i = b; i >= a; i--)
#define pl (p << 1)
#define pr (p << 1 | 1)
typedef pair<int, int> PII;
typedef long long LL;
// head

const int N = 1e6 + 5;
int n, m;
char s[N];

struct SegTree {
    int sum, max, min;
    int key;
} t[4 * N];

void pushup(int p) {
    t[p].sum = t[pl].sum + t[pr].sum;
    t[p].max = max(t[pl].max, t[pl].sum + t[pr].max);
    t[p].min = min(t[pl].min, t[pl].sum + t[pr].min);
}

void tran(int p) {
    t[p].sum = -t[p].sum;
    swap(t[p].min, t[p].max);
    t[p].min = -t[p].min;
    t[p].max = -t[p].max;
}

void pushdown(int p) {
    if (t[p].key == 0) return;
    t[p].key = 0; //消除标记

    t[pl].key ^= 1;
    tran(pl);
    t[pr].key ^= 1;
    tran(pr);
}

void build(int p, int l, int r) {
    if (l == r) {
        t[p].sum = (s[l] == '(' ? 1 : -1);
        t[p].min = t[p].max = t[p].sum;
        return;
    }

    int mid = l + r >> 1;
    build(pl, l, mid);
    build(pr, mid + 1, r);
    pushup(p);
}

//将 [x, y] 翻转
void modify(int p, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
        t[p].key ^= 1;
        tran(p);
        return;
    }

    pushdown(p);
    int mid = l + r >> 1;
    if (x <= mid) modify(pl, l, mid, x, y);
    if (y > mid) modify(pr, mid + 1, r, x, y);
    pushup(p);
}

//求区间 [x, y] 的 [前缀和，最小前缀和]
PII calc(int p, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
        return {t[p].sum, t[p].min};
    }

    pushdown(p);
    int mid = l + r >> 1;
    if (y <= mid) {
        return calc(pl, l, mid, x, y);
    } else if (x > mid) {
        return calc(pr, mid + 1, r, x, y);
    } else {
        PII a, b, res;
        a = calc(pl, l, mid, x, y);
        b = calc(pr, mid + 1, r, x, y);
        res.fi = a.fi + b.fi;
        res.se = min(a.se, a.fi + b.se);
        return res;
    }
}

int query(int x) {
    if (x >= n) return 0;
    PII res = calc(1, 1, n, x, n);
    if (res.se > 0) return 0;

    if (res.se <= -1) { //找第一个最小值小于等于-1的前一个位置
        int l = x, r = n;
        while (l < r) {
            int mid = l + r >> 1;
            PII a = calc(1, 1, n, x, mid);
            if (a.se <= -1) r = mid;
            else l = mid + 1;
        }
        if (l == x) return 0; //等于左端点，说明 a[l] = ')'
        return l - 1;
    } else { //最小值为0
        if (res.fi == 0) return n;

        int ans = 0;
        do {
            int l = x, r = n;
            while (l < r) {     //找第一个最小值小于等于0的前一个位置
                int mid = l + r >> 1;
                PII a = calc(1, 1, n, x, mid);
                if (a.se <= 0) r = mid;
                else l = mid + 1;
            }
            ans = max(ans, l);
            x = l + 1;
            res = calc(1, 1, n, x, n);
        } while (res.se == 0);
        return ans;
    }
}

int main() {
//    frein;
    cin >> n >> m;
    scanf("%s", s + 1);
//    s[++n] = ')';
    build(1, 1, n);
    int op, l, r;
    while (m--) {
        scanf("%d%d", &op, &l);
        if (op == 1) {
            scanf("%d", &r);
            if (l > r) swap(l, r);
//            if (l > 1) modify(1, 1, n, 1, l - 1);
            modify(1, 1, n, l, r);
        } else {
            printf("%d\n", query(l));
        }
    }
    return 0;
}