11932 트리와 K번째 수 https://www.acmicpc.net/problem/11932
Persistent Segment tree는 개념은 간단한편이지만 아직은
구현에 대해서 정확히 이해하지 못했다.
1. K번째 숫자
부분배열을 오름차순으로 정렬했을 때 K번째 숫자를 구하는 query를 해결하는 문제이다.
배열을 좌표압축시키고 tree[$i$] 는 0부터 arr[$i$]까지 저장하는 segment tree를 N개 만들면 된다.
실제로 N개를 만들면 N*N으로 메모리가 당연히 초과되므로
Persistent Segment Tree를 만들어야한다.
개념은 간단하다.
tree를 구축할 때 이미 만들어진 부분은 넘어가고 update해야할 곳만 update하는 것이다.
그 후 이분탐색으로 두 Node에서 어떠한 지점까지 개수가 K개인 지점을 찾는다.
그 지점이 K번째 수의 index가 된다.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct Node {
int v;
Node *l, *r;
Node() :v(0), l(nullptr), r(nullptr) {}
Node(int vv, Node *ll, Node *rr) :v(vv), l(ll), r(rr) {}
Node *makeTree(int nl, int nr, int val) {
if (nl <= val && val <= nr) {
if (nl == nr) return new Node(v + 1, nullptr, nullptr);
int mid = (nl + nr) >> 1;
return new Node(v + 1, l->makeTree(nl, mid, val), r->makeTree(mid + 1, nr, val));
}
else return this;
}
}*root[100001], *null;
int query(int nl, int nr, Node *u, Node *v, int val) {
if (nl == nr) return nl;
int diff = v->l->v - u->l->v;
int mid = (nl + nr) >> 1;
if (diff >= val) return query(nl, mid, u->l, v->l, val);
else return query(mid + 1, nr, u->r, v->r, val - diff);
}
int N, M;
int arr[100001], Copy[100001];
int main() {
scanf("%d%d", &N, &M);
for (int n = 0;n < N;n++) scanf("%d", &arr[n]), Copy[n] = arr[n];
sort(Copy, Copy + N);
for (int n = 0;n < N;n++)
arr[n] = lower_bound(Copy, Copy + N, arr[n]) - Copy;
null = new Node(0, nullptr, nullptr);
null->l = null->r = null;
for (int n = 0;n < N;n++) {
if (!n) root[n] = null->makeTree(0, N - 1, arr[n]);
else root[n] = root[n - 1]->makeTree(0, N - 1, arr[n]);
}
while (M--) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
u--, v--;
int iter = query(0, N - 1, u == 0 ? null : root[u - 1], root[v], d);
printf("%d\n", Copy[iter]);
}
return 0;
}
| cs |
2. 트리와 K번째 수
서로다른 가중치가 주어지는 트리에서 u, v 정점에서 가중치가 K번째인 수를 구하는
query를 처리해야하는 문제이다.
위와 비슷한 풀이인데 LCA를 이용하면 풀 수 있다.
함수 F(p, val)를 트리의 루트 노드부터 p번 노드까지의 경로 상에서 val보다 작거나 같은 원소의
개수를 리턴하는 함수라고 정의하자.
그리고 x를 u와 v의 LCA이고, p(x)를 x의 부모 노드라고 정의하자.
두 정점 u와 v 사이의 경로에서 Ans보다 작거나 같은 원소의 개수
Q(u, v, Ans) = F(u, ans) + F(v, ans) - F(x, ans) - F(p(x), ans)이다.
http://hongjun7.tistory.com/64 [Note. Hongjun Jang]
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct Node {
int v;
Node *l, *r;
Node() : Node(0, nullptr, nullptr) {}
Node(int vv, Node *ll, Node *rr) :v(vv), l(ll), r(rr) {}
Node *makeTree(int nl, int nr, int val) {
if (nl <= val && val <= nr) {
if (nl == nr) return new Node(v + 1, nullptr, nullptr);
int mid = (nl + nr) >> 1;
return new Node(v + 1, l->makeTree(nl, mid, val), r->makeTree(mid + 1, nr, val));
}
else return this;
}
}*root[100001], *null;
int N, M;
int cost[100001], Copy[100001];
vector<int> adj[100001];
int depth[100001];
int par[100001][21];
void dfs(int here, int p) {
root[here] = p == -1 ? null->makeTree(0, N - 1, cost[here]) : root[p]->makeTree(0, N - 1, cost[here]);
for (int next : adj[here]) {
if (next == p) continue;
depth[next] = depth[here] + 1;
par[next][0] = here;
dfs(next, here);
}
}
void init() {
for (int m = 1;m < 21;m++) {
for (int n = 0;n < N;n++) {
par[n][m] = par[par[n][m - 1]][m - 1];
}
}
}
int getLCA(int u, int v) {
if (depth[u] > depth[v]) swap(u, v);
for (int n = 20;n >= 0;n--) {
if (depth[v] - depth[u] >= (1 << n))
v = par[v][n];
}
if (u == v) return u;
for (int n = 20;n >= 0;n--) {
if (par[u][n] != par[v][n]) {
u = par[u][n];
v = par[v][n];
}
}
return par[u][0];
}
int query(int nl, int nr, Node *a, Node *b, Node *lca, Node *plca, int val) {
if (nl == nr) return nl;
int len = a->l->v + b->l->v - lca->l->v - plca->l->v;
int mid = (nl + nr) >> 1;
if (len >= val) return query(nl, mid, a->l, b->l, lca->l, plca->l, val);
else return query(mid + 1, nr, a->r, b->r, lca->r, plca->r, val - len);
}
int main() {
scanf("%d%d", &N, &M);
for (int n = 0;n < N;n++) scanf("%d", &cost[n]), Copy[n] = cost[n];
sort(Copy, Copy + N);
for (int n = 0;n < N;n++) cost[n] = lower_bound(Copy, Copy + N, cost[n]) - Copy;
for (int n = 0;n < N - 1;n++) {
int u, v;
scanf("%d%d", &u, &v);
u--, v--;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
null = new Node();
null->l = null->r = null;
dfs(0, -1);
init();
while (M--) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
u--, v--;
int lca = getLCA(u, v);
int iter = query(0, N - 1, root[u], root[v], root[lca], lca == 0 ? null : root[par[lca][0]], d);
printf("%d\n", Copy[iter]);
}
return 0;
}
| cs |
<참고>
