알고리즘 공부방

문제 oj.uz/problem/view/JOI18_construction 문제 보기 - Construction of Highway (JOI18_construction) :: oj.uz 문제 보기 - Construction of Highway (JOI18_construction) oj.uz 트리가 주어지고, 처음에는 1번 노드밖에 없다. 한번의 업데이트 때마다, 지금 존재하는 트리에 하나의 간선을 추가하여 새로운 노드를 붙이는데, 이 때 루트에서부터 새로 붙인 노드까지의 경로의 정점들의 가중치를 일렬로 나열했을 때 만들어지는 수열의 inversion을 출력해야 한다. 또한, 업데이트 이후, 루트에서부터 새로 붙인 노드까지의 경로의 모든 정점들의 가중치는 모두 새로 붙인 정점의 가중치로 바뀌게 된다. $N

문제 https://oj.uz/problem/view/JOI13_synchronization 문제 보기 - 동기화 (JOI13_synchronization) :: oj.uz JOI Co., Ltd.는 전 세계에 무려 $N$대의 서버를 두고 있습니다. 각 서버에는 중요한 정보의 일부가 저장되어 있고, 서로 다른 서버에는 서로 다른 정보가 저장되어 있습니다. JOI Co., Ltd.는 서버들끼리 정보를 공유하기 위해 서버들 사이에 정보를 양방향으로 교환할 수 있는 회선을 설치하고 있습니다. 정보들은 회선을 통해 여러 서버를 거쳐갈 수 있습니다. 각 서버는 고성능 동기화 시스템을 갖추고 있습니다. 두 서버가 서로 정보를 교환할 수 oj.uz 트리에서 처음에는 각 노드가 자기 자신만을 들고 있고, 각 시간마다 ..

Heavy Light Decomposition 은 트리에서 segment tree 등의 자료 구조를 활용할 수 있도록 만드는 방법이다. 1차원에서 업데이트, 쿼리를 처리하는 문제는 segment tree 등의 자료구조를 활용하여 풀 수 있다. 하지만 트리에서는 이 과정이 어렵기 때문에 트리를 몇개의 체인으로 쪼갠 후 각 체인에서 segment tree 등을 사용하는 것이다. 하지만 만약 이 체인의 수가 많아지면 그만큼 시간이 많이 걸리기 때문에 체인의 개수를 적당히 적게 만드는 방법이 필요하다. HLD 는 다음과 같이 트리에서 각 노드에서 자식들 중 가장 서브트리가 큰 서브트리까지의 간선을 "무거운 간선"으로 분류한다.이렇게 해서 "무거운 간선"들로만 묶이면 체인들 몇개로 트리가 분해되게 된다. 이때 가..