티스토리 뷰
728x90
문제 링크
13544번: 수열과 쿼리 3
길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다.
www.acmicpc.net
풀이
예전에 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'; } }
728x90
'알고리즘 > 문제 풀이' 카테고리의 다른 글
[BOJ] 백준 10021 - Watering the Fields (0) | 2021.03.30 |
---|---|
[BOJ] 백준 1673 - 치킨 쿠폰 (0) | 2021.03.30 |
[BOJ] 백준 2616 - 소형기관차 (0) | 2021.03.30 |
[BOJ] 백준 2169 - 로봇 조종하기 (0) | 2021.03.30 |
[BOJ] 백준 2281 - 데스노트 (1) | 2021.03.30 |
댓글