import sys,bisect
input = sys.stdin.readline
N,Q = map(int,input().split())
town = []
for _ in range(N):
a,x = map(int,input().split())
town.append((x,a))
town.sort()
cnt = [-sum(town[i][1] for i in range(N))]
for i in range(N):
cnt.append(cnt[-1]+town[i][1]*2)
prefix = [sum((town[i][0]-town[0][0])*town[i][1] for i in range(N))]
for i in range(N-1):
prefix.append(prefix[-1]+(town[i+1][0]-town[i][0])*cnt[i+1])
for _ in range(Q):
x = int(input())
i = bisect.bisect(town,(x+1,0))
print(prefix[i-1]+(x-town[i-1][0])*cnt[i] if i else prefix[0]+(x-town[0][0])*cnt[0])누적합 응용문제이다.
제목에서 알 수 있듯이 누적합을 사용하는데, 아이디어는 간단하지만 구현이 살짝 까다로울 수 있다.
기본원리를 설명하면, x좌표에서 거리가 절댓값인 경우에는 현재 위치보다 작은지 큰지에 따라 거리의 변화가 양수일 수도 음수일 수도 있다. 이 문제에서는 a명의 사람들이 있기 때문에 목적지가 x인 경우 거리의 변화량이 x*a일 수도, -x*a일 수도 있다. 이는 마을의 위치를 기준으로 변화하므로 마을의 위치를 기준으로 각 구간마다 x의 변화량에 대한 누적거리의 변화량을 계산해줄 수 있다.
풀이를 설명하면,
1. 마을을 x를 기준으로 정렬한다.
2. 모든 마을의 인구수의 합*-1 을 시작으로 x가 작은 순으로 cnt 리스트에 마을인구수*2를 더한 값을 누적해서 저장한다. (마을인구수*2를 하는 이유는 현재 마을을 지나면 거리의 변화량이 -a에서 +a로 2a만큼 변하기 때문이다)
3. 2번에서 저장한 값을 이용해 각 마을의 위치가 모임장소일 때 누적거리를 prefix에 계산하여 저장한다.
4. x를 입력받으면 bisect 함수를 이용해서 x가 어느 구간에 속하는지 확인하고, (3에서 구한 해당구간에서 가까운 마을의 에서의 누적거리) + (2에서 구한 해당 구간에서의 변화량) * (가까운 마을과 x의 거리 차)를 출력한다.
오늘의 교훈) 누적합은 쓰임새가 다양하다