문제
운하도시 풀스하임은 가운데에 큰 강이 자리잡은 무역도시로, 옛날부터 지리적 이점을 활용하여 운하를 통한 무역 활동을 꾸준히 하고 있다. 피아는 운하도시 풀스하임의 물자 수송 관리직을 맡아 도시의 발전에 큰 기여를 하고 있다.
최근 피아는 무역을 하는 배들이 강에 대한 정보가 없어 비효율적으로 움직인다는 것을 파악했다. 그래서 무역을 하는 배들이 빠르고 효율적으로 이동할 수 있도록, 출발과 도착 항구의 정보가 입력되면 제일 빠른 길을 알려주는 프로그램을 작성하였다. 하지만 강에 서식하는 거대한 용 때문에 배의 이동시간이 바뀌는 일이 다반사였고, 피아의 프로그램은 이런 상황에서 매우 느렸다. 결국 피아는 알고리즘을 매우 잘 아는 여러분에게 도움을 요청했다.
구체적으로 운하도시 풀스하임에서 항구는 그림과 같이 강 위쪽에 n개, 아래쪽에 n개가 나란히 위치해 있다. 또한, 강이 혼잡해지지 않도록 배는 그림에서 인접한 항구끼리만 이동할 수 있다.
항구와 뱃길에는 번호가 붙어있다. 왼쪽 위 항구가 1번, 왼쪽 아래가 n+1번이고, 오른쪽으로 가면서 순서대로 번호가 붙는다. 뱃길도 왼쪽 위 뱃길이 1번, 왼쪽 가운데 뱃길이 n번, 왼쪽 아래 뱃길이 2n번이고, 오른쪽으로 가면서 순서대로 번호가 붙는다. 그림에서 n=7인 경우의 예시를 확인할 수 있다.
피아는 구체적으로 다음과 같은 쿼리를 수행할 수 있는 프로그램을 원한다.
1. 특정 뱃길의 소요 시간이 바뀐다.
2. 주어진 두 항구 사이를 이동하는 데 소요되는 최단시간을 출력한다.
피아를 도와 프로그램을 작성해주자!
입력
첫 번째 줄에 두 자연수 n과 q가 주어진다. 이 때, 항구의 개수는 2n개이고, 질의 개수는 q개이다. (2 ≤ n, q ≤ 200,000)
두 번째 줄에 뱃길의 소요 시간을 의미하는 수 3n-2개가 뱃길의 번호 순서대로 주어진다.
세 번째 줄부터 q개의 줄에 다음과 같은 형식으로 질의가 주어진다.
1번 질의인 경우, 가장 먼저 1이 주어지고, 순서대로 뱃길의 번호 x와 바뀐 소요 시간 d가 주어진다. (1 ≤ x ≤ 3n-2)
2번 질의인 경우, 가장 먼저 2가 주어지고, 두 항구 u와 v의 번호가 주어진다. (1 ≤ u, v ≤ 2n, u ≠ v)
모든 뱃길의 소요 시간은 항상 0 이상, 109 이하이다.
출력
모든 2번 질의에 대해, 두 항구 사이의 최단시간을 각 줄에 출력한다.
예제
3 8
1 2 3 4 5 6 7
2 1 4
2 2 5
1 4 100
2 2 5
2 1 4
1 3 100
2 1 4
2 1 6
3
4
10
3
21
8
로그인해야 코드를 작성할 수 있어요.