题解：CF670E Correct Bracket Sequence Editor

Wyh_dailyAC · 2025-12-16 19:55:14 · 题解

思路

首先，我们给唯一配对的一对括号进行标号，这样我们在删除的时候就能确定删除区间范围。

之后，我们搞一个双向链表，在删除一个区间的时候，对于这个区间的左右端以及向左、右各扩展一格的点进行前驱后继的修改。

最后，我们可以选择依据链表关系进行逐个输出，也可以维护一个差分数组对区间进行标记，在最后的时候进行前缀和以还原标记，当未被标记时才输出括号，否则不。

细节见 Code。

Code

#include <bits/stdc++.h>
using namespace std;
// #define FILEIO "A"

int n, m, p;
string s = " ";
int cnt;
stack<int> stk;
int blg[500010];
vector<int> bbb[500010];
int lst[500010], nxt[500010];
int tag[500010];

signed main() {
    #ifdef FILEIO
        freopen(FILEIO ".in", "r", stdin);
        freopen(FILEIO ".out", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m >> p;
    char tch;
    for (int i = 1; i <= n; ++i) {
        cin >> tch;
        s += tch;
        if (tch == '(') { 
            stk.emplace(++cnt); 
            blg[i] = cnt; 
            bbb[cnt].emplace_back(i);
        } else { 
            int id = stk.top(); 
            blg[i] = id;
            bbb[id].emplace_back(i); 
            stk.pop(); 
        }
        lst[i] = i - 1;
        nxt[i] = i + 1;
    }
    lst[0] = 0;
    nxt[0] = 1;
    lst[n + 1] = n;
    nxt[n + 1] = n + 1;
    char ch;
    while (m--) {
        cin >> ch;
        if (ch == 'L') {
            p = lst[p];
        } else if (ch == 'R') {
            p = nxt[p];
        } else {
            int id = blg[p];
            int L = bbb[id][0];
            int R = bbb[id][1]; 
            tag[L]++;
            tag[R + 1]--;
            int prev_node = lst[L];
            int next_node = nxt[R]; 
            if (prev_node >= 1) nxt[prev_node] = next_node;
            if (next_node <= n) lst[next_node] = prev_node;
            if (next_node <= n) {
                p = next_node;
            } else {
                p = prev_node;
            }
            if (p < 1) p = 0;
            if (p > n) p = n + 1;
        }
    }
    for (int i = 1; i <= n; ++i) {
        tag[i] += tag[i - 1];
        if (tag[i] == 0) cout << s[i];
    }
}