상근이의 로봇
시간 제한1초메모리 제한128 MB
평면 위 고정된 여러 체크포인트에 대한 로봇의 맨해튼 거리 합을 각 명령 이후마다 구하는 문제로, x와 y좌표를 분리해 정렬된 누적합 구조로 동적으로 갱신해야 합니다.
문제
상근이는 새 로봇을 테스트 트랙에서 시험하려고 한다. 테스트 트랙은 2차원 평면이며, 로봇은 처음에 (0, 0)에서 시작한다. 상근이는 로봇에게 S, J, I, Z 중 하나의 명령을 순서대로 보낸다.
로봇이 현재 (x, y)에 있을 때 각 명령의 의미는 다음과 같다.
상근이는 로봇이 정확히 움직이는지 확인하려고 테스트 트랙 위에 N개의 고정 조사점을 설치했다. 로봇은 명령 하나를 수행할 때마다 현재 위치에서 모든 조사점까지의 맨해튼 거리 합을 전송한다.
각 명령을 수행한 직후 로봇이 전송하는 값을 구하라.
입력
첫째 줄에 조사점의 수 N과 명령의 수 M이 주어진다. (1 <= N <= 100,000, 1 <= M <= 300,000)
다음 N개 줄에는 각 조사점의 좌표 x, y가 주어진다. 모든 좌표는 절댓값이 1,000,000 이하인 정수이다. 같은 좌표의 조사점이 여러 개 있을 수 있으며, 그런 경우 각각을 별도의 조사점으로 계산한다.
마지막 줄에는 로봇에게 보낸 길이 M의 명령 문자열이 주어진다. 문자열은 S, J, I, Z로만 이루어진다.
출력
총 M줄을 출력한다. i번째 줄에는 i번째 명령을 수행한 직후, 현재 로봇 위치에서 모든 조사점까지의 맨해튼 거리 합을 출력한다.