https://www.acmicpc.net/problem/2357

각 질의에 대해 선형적인 탐색으로 답을 찾으려고 한다면 시간복잡도는 O(NM)으로 시간 내에 풀 수 없습니다. 대신 segment tree를 활용하면 각 쿼리에 대해 O(lgN)의 시간이 필요하기 때문에 시간복잡도는 O(MlgN)으로 시간 내에 풀어낼 수 있습니다. segment tree가 구현이 조금 까다롭긴 하지만 숙달하면 쉽게 짤 수 있을 것 같습니다.

https://github.com/encrypted-def/BOJ/blob/master/2357.cpp