题解：CF670E Correct Bracket Sequence Editor

_jxy · 2025-04-30 11:10:09 · 题解

首先预处理出每一个左括号和它匹配的右括号和每一个右括号和它匹配的左括号，这里用个栈维护就好。

之后考虑修改操作。显然这东西可以链表解决，但是链表太难写了，考虑别的做法。

我们可以用线段树。初始全部是 0，表示没有被删除。每次修改操作就是在一对括号中间的位置区间推平成 1，表示这些位置被删除了。最后输出中查询这个位置是否为 0 就行了。

如果是光标移动的话，假设当前光标的位置为 p，分两种情况。

第一种，向左移动。那只要找出 [1,p-1] 区间内在线段树上值为 0 的最大位置。

第二种，向右移动。那就是要找出 [p+1,n] 区间内在线段树上值为 0 的最小位置。

显然，这两种情况都可以用二分来找。

时间复杂度 O(n \log^2 n)，很好写，但是常数有点大，要稍微卡卡常。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 500005;
const int INF = 0x3f3f3f3f;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
char a[N], s[N];
int L[N], R[N];
int val[N << 2];
bool tag[N << 2];
void pushup(int u) {
    val[u] = val[u << 1] + val[u << 1 | 1];
}
void pushdown(int u, int len1, int len2) {
    if (!tag[u]) return;
    val[u << 1] = len1;
    tag[u << 1] = 1;
    val[u << 1 | 1] = len2;
    tag[u << 1 | 1] = 1;
    tag[u] = 0;
}
void update(int u, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
        val[u] = r - l + 1;
        tag[u] = 1;
        return;
    }
    int mid = l + r >> 1;
    pushdown(u, mid - l + 1, r - mid);
    if (x <= mid) update(u << 1, l, mid, x, y);
    if (y > mid) update(u << 1 | 1, mid + 1, r, x, y);
    pushup(u);
}
int query(int u, int l, int r, int x, int y) {
    if (x <= l && r <= y) return val[u];
    int mid = l + r >> 1;
    pushdown(u, mid - l + 1, r - mid);
    int res = 0;
    if (x <= mid) res += query(u << 1, l, mid, x, y);
    if (y > mid) res += query(u << 1 | 1, mid + 1, r, x, y);
    return res;
}
int n, m, p;
int find1(int x, int y) {
    int l = x, r = y, res = -1;
    while (l <= r) {
        int mid = l + r >> 1;
        if (query(1, 1, n, x, mid) == mid - x + 1) {
            l = mid + 1;
        } else {
            r = mid - 1;
            res = mid;
        }
    }
    return res;
}
int find2(int x, int y) {
    int l = x, r = y, res = -1;
    while (l <= r) {
        int mid = l + r >> 1;
        if (query(1, 1, n, mid, y) == y - mid + 1) {
            r = mid - 1;
        } else {
            l = mid + 1;
            res = mid;
        }
    }
    return res;
}
int main() {
    scanf("%d%d%d", &n, &m, &p);
    scanf("%s%s", a + 1, s + 1);
    stack<int> st;
    for (int i = 1; i <= n; i++) {
        if (a[i] == '(') {
            st.push(i);
        } else {
            int t = st.top();
            st.pop();
            R[t] = i, L[i] = t;
        }
    }
    for (int i = 1; i <= m; i++) {
        if (s[i] == 'L') {
            p = find2(1, p - 1);
        } else if (s[i] == 'R') {
            p = find1(p + 1, n);
        } else {
            if (a[p] == '(') {
                update(1, 1, n, p, R[p]);
                int k1 = find1(R[p] + 1, n), k2 = find2(1, p - 1);
                if (k1 != -1) {
                    p = k1;
                } else {
                    p = k2;
                }
            } else {
                update(1, 1, n, L[p], p);
                int k1 = find1(p + 1, n), k2 = find2(1, L[p] - 1);
                if (k1 != -1) {
                    p = k1;
                } else {
                    p = k2;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (query(1, 1, n, i, i) != 1) printf("%c", a[i]);
    }
    printf("\n");
    return 0;
}