Link https://www.acmicpc.net/problem/18798 2020 SciOI #1 A번 Tag 세그먼트 트리 Time Complexity $O(NlgX+QlgN)$ 길이 $N$ 인 수열 $A$ 가 주어지고, 음이 아닌 정수가 $K$ 가 주어진다. 구간 bitwise OR 쿼리와 구간 내 $K$ 와 같은 수의 개수를 묻는 쿼리에 응답해야한다. 2번 쿼리는 구간 합 세그먼트 트리를 만들어 쿼리를 날리면 되므로, 1번 쿼리를 처리하는 방법을 알아보자. 풀이의 핵심은 bitwise OR의 성질에 있다. 어떤 비트가 1이 되고 나면, 다시 0이 되는 일이 없다. 위 성질을 이용해 적절한 가지치기를 해 주자. 레이지 느낌으로, 구간 내 업데이트를 기록해주는 세그먼트 트리를 구성하자. 2번 쿼리가..
Link https://www.acmicpc.net/problem/4002 APIO 2010 1번 Tag 트리 오일러 투어 테크닉 세그먼트 트리 Time Complexity $O(NlgN)$ 트리 형태로 닌자 조직이 주어진다. 각각의 닌자는 받아야 하는 월급, 리더십 레벨 속성을 가지고 있다. 우리는 '매니저' 닌자를 선택해, 매니저를 루트로 하는 서브트리에서 닌자들을 선택할 수 있다. 선택된 닌자들의 월급의 합은 $M$ 이하가 되어야 한다. 이때 (매니저의 리더십 레벨) * (선택된 닌자들의 수) 를 최대화 해야 한다. 임의의 매니저를 정했으면, 그리디하게 월급이 적은 닌자들부터 선택하는게 최적이다. 나이브하게 모든 닌자들을 매니저로 시도해보면서, 서브트리의 닌자들 중 월급이 작은 순서대로 정렬 후 $..