알고리즘 공부방

문제 oj.uz/problem/view/IOI20_plants 문제 보기 - 식물 비교 (IOI20_plants) :: oj.uz 문제 보기 - 식물 비교 (IOI20_plants) oj.uz 원 위에 0~N-1의 N개의 수가 배열되어 있는 순열 $A$가 있다. 이 때 $R_i$는 i번째 칸부터 오른쪽으로 연속한 $K-1$개의 수들 중 $A_i$보다 큰 수들의 개수로 정의된다. 수열 $R_i$와 쿼리 (x, y)가 Q개 주어질 때, 가능한 모든 $A_i$에서 $A_xA_y$를 만족하는지, 아니면 두 경우 모두 가능한지 판별해야 한다. 단, 주어지는 $R$는 대응되는 $A$가 적어도 하나 존재하는 수열로 주어진다. $K1; init(node*2, tl, mid); init(node*2+1, mid+1, t..

LCA란, Lowest Common Ancestor 로, 트리에서의 최소 공통 조상이다. 공통 조상은 두 노드에 대해, 두 노드 모두의 자손인 조상 노드들을 의미하며, 그중 깊이가 최대인 것, 즉 가장 아래쪽에 위치한 노드를 두 노드에 대한 최소 공통 조상 이라 한다. 기본적인 아이디어는 두 노드에 대해서 1. 두 노드의 깊이가 같도록 하나의 노드를 올려준 후, 2. 두 노드가 같아질 때까지 올려준다. 이 연산을 그냥 실행하면, 최악의 경우에 $O(N)$의 시간이 걸릴 수 있다. 이는 Sparse Table 을 사용하여 LCA 연산을 $O(logN)$에 처리할 수 있다. 가장 먼저 dfs 한번을 돌면서 각 노드들의 깊이와, 노드들의 부모를 sparse table 안에 저장한다. 다음, $par[i][j]..