마라톤 (Gold)

열정적인 마라톤 러너인 베시는 마라톤 코스를 설계하는 것도 즐긴다. 그녀는 순서대로 방문해야 하는 N개의 체크포인트로 이루어진 경로를 설계했다 (1 <= N <= 100,000).

베시는 특정 부분 경로를 달리는 데 얼마나 걸리는지 알고 싶다. 부분 경로란 체크포인트들의 연속한 부분 수열을 말한다. 다른 소들은 게을러서 부분 경로를 달릴 때마다 체크포인트 하나를 건너뛸 수 있는데, 전체 이동 시간이 최소가 되는 체크포인트를 골라 건너뛴다. 부분 경로의 첫 번째와 마지막 체크포인트는 건너뛸 수 없다.

베시는 체크포인트 위치를 변경하는 것도 검토하려 한다. 특정 변경이 여러 부분 경로를 달리는 데 필요한 시간에 어떤 영향을 미치는지 (소들이 체크포인트 하나를 생략할 수 있음을 고려하여) 판단할 수 있도록 도와주자. (x1, y1)과 (x2, y2) 사이의 거리는 맨해튼 거리 |x1-x2| + |y1-y2|이다.

첫째 줄에 N과 Q가 주어진다 (1 <= Q <= 100,000).

둘째 줄부터 1+N번째 줄까지 N개의 체크포인트의 (x, y) 위치가 순서대로 주어진다. 모든 좌표는 -1000 .. 1000 범위이다.

2+N번째 줄부터 1+N+Q번째 줄까지 한 줄에 하나씩 갱신과 질의가 주어진다. "U I X Y"는 체크포인트 I의 위치를 (X, Y)로 변경한다. "Q I J"는 체크포인트 I에서 체크포인트 J까지의 부분 경로에서 (I <= J), 소들이 이 부분 경로의 체크포인트 하나를 (단, 양 끝점은 제외) 건너뛴다고 할 때의 최소 이동 시간을 묻는다.

각 질의마다 구하고자 하는 최소 부분 경로 길이를 한 줄에 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > December > Gold