BOJ#11932 트리와 K번째 수

PST 응용 문제 ~ 이 문제를 풀고 싶다면 #7469 K번째 수를 PST로 풀고 오자. 어차피 짜야하는 부분이 같다.

 

저 문제는 배열에서 K번째 수를 처리하는 것이고, 이 문제는 트리에서 처리해야한다. 그렇지만 선형 연산을 이용해서 풀 수 있다.

 

왜? root부터 다른 정점까지는 선형이며, 정답을 위한 쿼리는 (root부터 x) + (root부터 y) - (root부터 lca) - (root부터 parent[lca])로 돌릴 수 있다. parent[lca]를 빼는 이유는 lca는 한 번만 빼줘야하기 때문이다.

 

int query(int x, int y, int k) {
    int l = lca.query(x, y); int pl = lca.par[l][0];
    if(l==1 && pl == 1) pl = 0;
    return o2v[pst.f(x, y, l, pl, 1LL, n, k)];
}

 

이분탐색(lg^2 n)안 쓰고 탑다운(lg n)으로 쿼리를 처리할 수 있다.

 

int f(int ax, int ay, int alca, int aplca, ll l, ll r, int k) {
    if(l == r) return l;
    ll val = seg[seg[ax].left_node].req + seg[seg[ay].left_node].req - seg[seg[alca].left_node].req - seg[seg[aplca].left_node].req;
    if(val >= k) return f(seg[ax].left_node, seg[ay].left_node, seg[alca].left_node, seg[aplca].left_node, l, (l + r) / 2, k);
    else return f(seg[ax].right_node, seg[ay].right_node, seg[alca].right_node, seg[aplca].right_node, (l + r) / 2 + 1, r, k - val);
}