[BOJ] 백준 13544 - 수열과 쿼리 3

문제 링크

www.acmicpc.net/problem/13544

13544번: 수열과 쿼리 3

 

풀이

예전에 Persistent Segment Tree 연습한다고 풀었던 문젠데, 이번엔 Merge Sort Tree를 연습한다고 풀어보게 되었습니다.

 

머지 소트 트리는 트리의 각 노드마다 항상 아래 두 노드의 리스트를 정렬된 상태로 갖고 있도록 저장하는 세그먼트 트리입니다.

PST는 개념상 2차원 세그먼트 트리인데, 공간 효율을 높인 세그먼트 트리라고 보시면 됩니다.

이에 대한 더 자세한 설명은 다른 블로그를 참고해주세요.

 

정답 코드

Merge Sort Tree

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;

int n, m;
int p[111'111];

struct Seg {
    vvi tree;

    void init(int node, int s, int e) {
        if (s == e) {
            tree[node] = {p[s]};
            return;
        }
        int mid = (s + e) / 2;
        init(node * 2, s, mid);
        init(node * 2 + 1, mid + 1, e);
        vi &l = tree[node * 2];
        vi &r = tree[node * 2 + 1];

        for (int i = 0, j = 0; i < l.size() || j < r.size();) {
            if (j == r.size() || (i < l.size() && l[i] < r[j])) tree[node].push_back(l[i++]);
            else tree[node].push_back(r[j++]);
        }
    }

    Seg() {
        tree.resize(4 * n);
        init(1, 1, n);
    }

    int query(int i, int j, int k) {
        return query(1, 1, n, i, j, k);
    }

    int query(int node, int s, int e, int i, int j, int k) {
        if (j < s || i > e) return 0;
        if (i <= s && e <= j) {
            return tree[node].end() - upper_bound(all(tree[node]), k);
        }
        int mid = (s + e) / 2;
        return query(node * 2, s, mid, i, j, k) + query(node * 2 + 1, mid + 1, e, i, j, k);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i < n + 1; i++) {
        cin >> p[i];
    }
    Seg tree;
    cin >> m;
    int last = 0;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        int l = a ^last;
        int r = b ^last;
        int k = c ^last;
        last = tree.query(l, r, k);
        cout << last << '\n';
    }
}

 

 

Persistent Segment Tree

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Node {
	int v = 0;
	Node *left = 0, *right = 0;
} *tree[100001];

Node* init(Node *prev, int s, int e, int v) {
	if (v < s || e < v) return prev;
	Node *now = new Node;
	if (s == e) {
		now->v = prev->v + 1;
		return now;
	}
	if (!prev->left) prev->left = new Node;
	if (!prev->right) prev->right = new Node;
	int m = (s + e) / 2;
	now->left = init(prev->left, s, m, v);
	now->right = init(prev->right, m + 1, e, v);
	now->v = now->left->v + now->right->v;

	return now;
}

int query(Node *now, int s, int e, int v) {
	if (e <= v || !now) return 0;
	if (v < s) return now->v;
	int m = (s + e) / 2;
	return query(now->left, s, m, v) + query(now->right, m + 1, e, v);
}
int last, n, m, x;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	tree[0] = new Node;
	for (int i = 1; i < n + 1; i++) {
		cin >> x;
		tree[i] = init(tree[i - 1], 1, 1e9, x);
	}
	cin >> m;
	int a, b, c;
	while (m--) {
		cin >> a >> b >> c;
		a ^= last;
		b ^= last;
		c ^= last;
		last = query(tree[b], 1, 1e9, c) - query(tree[a - 1], 1, 1e9, c);
		cout << last << '\n';
	}
}