유니온파인드 (2) 썸네일형 리스트형 [BOJ 27014] Cube Stacking https://www.acmicpc.net/problem/27014 27014번: Cube Stacking Farmer John and Betsy are playing a game with N (1 ≤ N ≤ 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1≤ P ≤ 100,000) operation. There are two types of ope www.acmicpc.net Tag : DSU 스몰투라지, 세그 등... 뇌절각은 잔뜩 보이는데 그냥 \(O(logN)\) 이하의 유니온 파인드로 생각을 했을 .. Path Comprssion DSU의 amortized O(logN) 증명 Weighted union rule, Path compression 중 하나만 사용하면 amotized \(O(logN)\), 둘 모두를 사용하면 amortized \(O(\alpha(N))\)임이 잘 알려져있습니다. Path compression만을 사용했을 때 시간복잡도의 증명은 한글 자료가 잘 없는 것 같아 작성합니다. Heavy Light Decomposition스러운 논리를 사용합니다. 정점 u가 v의 자식일 때 sz[v] \(\leq\) sz[u] / 2이면 u->v간선은 light edge, 나머지는 heavy edge라고 해봅시다. 당연하게도 heavy edge는 정점당 하나만 생깁니다 (sz[x] := x의 서브트리의 크기) 임의의 정점 (u, v)에 대해 u->v로 가는 경로는 최대 \.. 이전 1 다음
