DEV/PS
[BOJ/2912] 백설공주와 난쟁이, c++
www.acmicpc.net/problem/2912 2912번: 백설공주와 난쟁이 첫째 줄에 난쟁이의 수 N과 모자 색상의 수 C가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ C ≤ 10,000) 둘째 줄에는 각 난쟁이가 쓰고 있는 모자의 색상이 줄을 서 있는 순서대로 주어진다. 셋째 줄에는 사진 www.acmicpc.net 한줄 후기 : 세그 트리라도 푼게 어디야.. 원래 확률적 알고리즘 파트라서 Mo's Algorithm 을 이용해 풀어봐야 하는 것 같다. 하지만.. 도저히 못풀겠음 구글링 좀 해서 봤는데 계속 시간 초과 나서 못 풀었다. 그래서 이 문제를 또 풀 수 있는 방법인 세그먼트 트리를 이용해 풀었다. 세그먼트 트리로 푸는 법은 간단하다. 그냥 처음 트리를 생성할 때, 트리에는 해당 ..
