https://www.acmicpc.net/problem/22345 22345번: 누적 거리 KOI 나라는 수직선 위에 놓인 N개의 마을로 구성되어 있다. 이 중 i (1 ≤ i ≤ N)번째 마을은 xi 위치에 놓여 있으며 ai명이 거주 중이다. 또한 서로 다른 두 마을이 같은 위치에 놓인 경우는 없다. KOI www.acmicpc.net 이전에 포스팅한 Stadium이라는 문제와 매우 유사하다. 다만 이 문제에서는 x좌표가 정렬이 되어있지 않으므로 정렬을 해주어야 한다. 그리고 주어지는 후보지점에서의 값을 계산해주면 된다. Stadium에서는 변화량에 집중하였다면 이번에는 그냥 계산하면 된다. 누적 거리를 구하기 위해서는 각 쿼리가 어떠한 두 마을 사이에 있는지 알아야 하며, 이를 이분탐색을 통해 찾아..