동적 세그먼트 트리 구현 예시

dst.cpp

// BOJ 15816 - 퀘스트 중인 모험가
// https://www.acmicpc.net/problem/15816
// 풀이는 맞지만 MLE가 나옴. BBST를 사용해야 하는 문제임.
#include <iostream>

constexpr int SL = -1'000'000'000;
constexpr int SR = +1'000'000'000;

struct Node {
    Node *l, *r;
    int   x;
    Node(int p = 0) : l(nullptr), r(nullptr), x(p) {}
};

int getx(const Node *x) { return (x == nullptr ? 0 : x->x); }

void query1(Node *&x, int qn, int l = SL, int r = SR)
{
    if (x == nullptr) x = new Node();
    if (l == r) {
        x->x = 1;
        return;
    }

    const int mid = (l + r) / 2;
    if (qn <= mid)
        query1(x->l, qn, l, mid);
    else
        query1(x->r, qn, mid + 1, r);

    x->x = getx(x->l) + getx(x->r);
}

int query2(const Node *x, int ql, int qr, int l = SL, int r = SR)
{
    if (x == nullptr) return 0;
    if (ql <= l && r <= qr) return x->x;
    if (qr < l || r < ql) return 0;

    const int mid = (l + r) / 2;
    return query2(x->l, ql, qr, l, mid) + query2(x->r, ql, qr, mid + 1, r);
}

int main()
{
    using namespace std;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Node *rt = nullptr;
    int   n, m;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        query1(rt, x);
    }

    cin >> m;
    for (int i = 0; i < m; ++i) {
        int qn, x, y;
        cin >> qn;
        switch (qn) {
        case 1:
            cin >> x;
            query1(rt, x);
            break;
        case 2:
            cin >> x >> y;
            cout << ((y - x + 1) - query2(rt, x, y)) << '\n';
            break;
        default:;
        }
    }
}