문제 링크
- http://icpc.me/17731 (일본어 원문)
- https://oj.uz/problem/view/JOI14_historical (한국어 번역)
문제 출처
- 2013/2014 JOISC Day1 3번
사용 알고리즘
- 모스 알고리즘
- 세그먼트 트리
시간복잡도
- $O((N+Q) \sqrt N log N)$
풀이
업데이트가 없고 구간의 어떤 값을 구해야 하기 때문에 모스 알고리즘을 생각할 수 있습니다.
세그먼트 트리의 각 리프노드에 사건 유형의 중요도를 저장한 뒤, 구간 최댓값을 구하는 것으로 문제를 풀 수 있습니다.
구간에 사건 유형 X가 추가되면 X번째 리프노드에 X를 더하고, 사건 유형 X가 제거되면 X번째 리프노드에 X를 빼주면 됩니다.