풀이는 http://weeklyps.com/entry/%ED%8A%B8%EB%A6%AC%EC%97%90%EC%84%9C%EC%9D%98-%EB%AA%A8%EC%8A%A4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%99%9C%EC%9A%A9-Mos-algorithm-on-tree 이 곳에 서술 되어 있으므로, 상세한 사항은 아래의 소스로 대신한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979..
Table of Contents 개요 쿼리 처리 쿼리 정렬 문제 1. 개요 https://www.acmicpc.net/problem/13547 먼저 위의 문제를 읽어주시길 바랍니다. 범위 쿼리를 처리하는 상황에서 가끔 이런 상황들이 있습니다. 배열 Array[1...N], 함수 Function, 범위 [L, R] 이 주어질 때 Function(Array[L], Array[L+1], ..., Array[R]) 계산하는데, 배열에 저장된 값을 고치는 update 연산은 없는 상황입니다. 위의 문제가 그 예시이지요. 이런 상황을 만나면 Segment tree 나 Sparse table 로 접근하는 경우가 많습니다. 하지만 이 두 자료구조를 활용한 접근은 대체로, 온라인 처리가 아닌 배치 처리가 가능하다는 점을..