「ABC307D」珂朵莉树最強！

题目传送门 RMJ 传送门

题意简述

输入一个字符串，要删掉原字符串中左右匹配的括号及其中的内容。

例如 qwq(qwq)(quq(Q)AQ 的结果就是 qwq(quqAQ。

思路分析

赛时情况：先写了个括号匹配，然后发现需要标记被删除的区间。拿线段树糊了一个版本，交上去会 TLE，最后也不知道怎么就想到了一个这么可爱的珂朵莉树。然后 AC。上分（x）

本题可以使用「珂朵莉树 + 栈」解决。使用栈进行括号匹配，同时存储上一个左括号出现的位置。若出现右括号，则进行 assign 操作，以标记需要被删除的区间。最后遍历所有区间得到答案。具体参见代码。

代码

#include <iostream>
#include <set>
#include <stack>
using namespace std;

int n, m, u, v, w;
string s, res;

stack<int> st;

/* --- BEGIN ODT --- */

// 抄的 OI Wiki 的模板（x）
struct node {
    int l, r;
    mutable int v;
    node(const int& il, const int& ir, const int& iv)
        : l(il)
        , r(ir)
        , v(iv)
    {
    }

    bool operator<(const node& o) const { return l < o.l; }
};

set<node> odt;

auto split(int x)
{
    if (x > n)
        return odt.end();
    auto it = --odt.upper_bound(node { x, 0, 0 });
    if (it->l == x)
        return it;
    int l = it->l, r = it->r, v = it->v;
    odt.erase(it);
    odt.insert(node(l, x - 1, v));
    return odt.insert(node(x, r, v)).first;
}

void assign(int l, int r, int v)
{
    auto itr = split(r + 1), itl = split(l);
    odt.erase(itl, itr);
    odt.insert(node(l, r, v));
}

/* --- END ODT --- */

int main()
{
    cin >> n >> s;
    int ptr = 0;
    odt.insert({ 1, s.length(), 0 });
    while (ptr < s.length()) {
        // 括号匹配
        if (s[ptr] == '(') {
            st.push(ptr);
        } else if (s[ptr] == ')') {
            if (!st.empty()) {
                // 注意这里有 1 的偏移量
                assign(st.top() + 1, ptr + 1, 1);
                st.pop();
            }
        }
        ptr++;
    }
    for (node x : odt) {
        // 遍历区间
        if (x.v == 0) {
            for (int i = x.l; i <= x.r; i++)
                putchar(s[i - 1]);
        }
    }
    return 0;
}