백준 13538 XOR 쿼리

https://www.acmicpc.net/problem/13538

 

크기가 2의 제곱수인 세그먼트 트리 == 트라이

훈련소 때 불침번 서면서 생각했었다

이 문제는 먼가 자구벅벅하면 풀릴 것 같아서 큐에 넣어뒀는데

오랜만에 읽어 보니 이거였구나! 싶었다

탈출 불가능한 미로 이후로 이 문제 짜면서 pst 쓰는 법도 어느 정도 익히게 된 것 같다

 

+ 벡터에 원소를 삽입할 일이 있을 때는 벡터의 원소를 가리키는 레퍼런스나 포인터를 들고 있으면 안 된다

재할당되면 개망하기때문에

이거로 한참 디버깅했다 ..

아마 reserve 먼저 해 주면 괜찮을 것 같긴 한데 잘은 모르겟네요

 

#include <bits/stdc++.h>
using namespace std;
 
struct Node {
    int l, r, lNode, rNode, cnt;
    Node(int l, int r) : l(l), r(r), lNode(-1), rNode(-1), cnt(0) {}
};
 
vector<Node> v{Node(0, (1<<19)-1)};
vector<int> root{0}, h;
 
int add(int now, int i){
    Node ret = v[now];
    if (v[now].l == v[now].r){
        ret.cnt++;
        v.push_back(ret);    
 
        return v.size()-1;
    }
    int m = v[now].l + v[now].r >> 1;
    if (v[now].lNode == -1){
        v[now].lNode = v.size();
        v.push_back(Node(ret.l, m));
    }
    if (v[now].rNode == -1){
        v[now].rNode = v.size();
        v.push_back(Node(m+1, ret.r));
    }
    if (i <= m){
        ret.lNode = add(v[now].lNode, i);
        ret.rNode = v[now].rNode;
    }
    else{
        ret.lNode = v[now].lNode;
        ret.rNode = add(v[now].rNode, i);
    }
    ret.cnt = v[ret.lNode].cnt + v[ret.rNode].cnt;
    v.push_back(ret);
    return v.size()-1;
}
 
void del(int now, int i){
    Node& x = v[now];
    x.cnt--;
    if (x.l == x.r){
        return;
    }
    int m = x.l + x.r >> 1;
    if (i <= m)
        del(x.lNode, i);
    else
        del(x.rNode, i);
}
 
int op2(int ln, int rn, int x, int k){
    int l = v[ln].l, r = v[ln].r;
    if (k == -1) return l;
    int m = l+r >> 1;
    if (v[ln].lNode == -1) {
        v[ln].lNode = v.size();
        v.emplace_back(l, m);
    }
    if (v[ln].rNode == -1){
        v[ln].rNode = v.size();
        v.emplace_back(m+1, r);
    }
    if (v[rn].lNode == -1){
        v[rn].lNode = v.size();
        v.emplace_back(l, m);
    }
    if (v[rn].rNode == -1){
        v[rn].rNode = v.size();
        v.emplace_back(m+1, r);
    }
    int li[] = {v[ln].lNode, v[ln].rNode}, ri[] = {v[rn].lNode, v[rn].rNode}, t = x >> k & 1 ^ 1;
    if (v[ri[t]].cnt - v[li[t]].cnt) return op2(li[t], ri[t], x, k-1);
    else return op2(li[t^1], ri[t^1], x, k-1);
}
 
int op4(int ln, int rn, int x, int _t = 0){
    int l = v[ln].l, r = v[ln].r;
    if (l > x) return 0;
    if (r <= x) return v[rn].cnt - v[ln].cnt;
    int m = l+r >> 1;
    if (v[ln].lNode == -1) {
        v[ln].lNode = v.size();
        v.emplace_back(l, m);
    }
    if (v[ln].rNode == -1){
        v[ln].rNode = v.size();
        v.emplace_back(m+1, r);
    }
    if (v[rn].lNode == -1){
        v[rn].lNode = v.size();
        v.emplace_back(l, m);
    }
    if (v[rn].rNode == -1){
        v[rn].rNode = v.size();
        v.emplace_back(m+1, r);
    }
    return op4(v[ln].lNode, v[rn].lNode, x) + op4(v[ln].rNode, v[rn].rNode, x);
}
 
int op5(int ln, int rn, int k, int _t = 0){
    int l = v[ln].l, r = v[ln].r;
    if (l == r) return l;
    int m = l+r >> 1;
    if (v[ln].lNode == -1) {
        v[ln].lNode = v.size();
        v.emplace_back(l, m);
    }
    if (v[ln].rNode == -1){
        v[ln].rNode = v.size();
        v.emplace_back(m+1, r);
    }
    if (v[rn].lNode == -1){
        v[rn].lNode = v.size();
        v.emplace_back(l, m);
    }
    if (v[rn].rNode == -1){
        v[rn].rNode = v.size();
        v.emplace_back(m+1, r);
    }
    if (v[v[rn].lNode].cnt - v[v[ln].lNode].cnt >= k) return op5(v[ln].lNode, v[rn].lNode, k);
    else return op5(v[ln].rNode, v[rn].rNode, k - (v[v[rn].lNode].cnt - v[v[ln].lNode].cnt));
}
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    
    function<int(int,int,int,int)> f[] = {op2, op2, op4, op4, op5};
    int M;
    cin >> M;
    while (M--){
        int op, l, r, x;
        cin >> op;
        if (op == 1){
            cin >> x;
            root.push_back(add(root.back(), x));
            h.push_back(x);
        }
        else if (op == 3){
            cin >> x;
            while (x--){
                del(root.back(), h.back());
                root.pop_back();
                h.pop_back();
            }
        }
        else {
            cin >> l >> r >> x;
            cout << f[op-1](root[l-1], root[r], x, 18) << '\n';
        }
    }
}