4661 . 最短路問題
Description
給你一個正整數$N$以及一個無向圖，它有$N + 2$個頂點和$2N + 1$條邊。它的$N + 2$個頂點依序編號為$-1, 0, 1, 2, 3, \cdots , N$，且$2N + 1$條邊依序編號為$0, 1, 2, 3, \cdots , 2N$。對於編號是$i$的邊，其邊權一開始是$w_i$，若$i < N$，則其連接編號是$i$和$i + 1$的頂點，否則其連接連接編號是$i - N$和$-1$的頂點。
你要先找出這個圖上從編號$0$的頂點到編號$N$的頂點的最短路。接下來，這個圖會經歷$Q$次修改。第$i$次修改可以用兩個整數$e_i, x_i$表示，代表把編號是$e_i$的邊的邊權修改成$x_i$，每次修改的效果會持續到整個過程結束為止。在每次修改之後，你要找出這個圖上從編號$0$的頂點到編號$N$的頂點的最短路。
Input Format
每筆測資第零行是二個非負整數$N, Q$，以空格分開，意義如題目所述
第一行是$2N + 1$個非負整數，以空格分開，依序是$w_0, w_1, w_2, \cdots , w_{2N}$
接著的$Q$行，第$2 + i$行會有二個非負整數$e_i^ {\prime}, x_i^ {\prime}$，以空格分開，本題為強制在線，因此，假設前$i$次修改後，編號$0$的頂點到編號$N$的頂點的最短路是$ans_i$，則上方所述的$e_i = e_i^ {\prime} \oplus ans_i, x_i = x_i^ {\prime} \oplus ans_i$，其中$\oplus$是bitwise xor，注意$ans_0$是有意義的
$1 \le N \le 2 \times 10^ {5}, 0 \le Q \le 2 \times 10^ {5}$
$\forall 0 \le i \le 2N, 1 \le w_i \le 10^ {9}$
$\forall 0 \le i \le Q - 1, 0 \le e_i \le 2N, 1 \le x_i \le 10^ {9}$
Output Format
分成$Q + 1$行，每行輸出一個整數，代表一開始以及每次修改後編號$0$的頂點到編號$N$的頂點的最短路，第$i$行就是前$i$次修改後，編號$0$的頂點到編號$N$的頂點的最短路（事實上，第$i$行輸出的整數就是輸入說明中的$ans_i$）
Sample Input 1
5 7 1 1 1 1 1 1 1 1 1 1 1 8 777771451 6 777771450 13 777771453 3 777771452 13 777771452 2 777771452 7 777771452
Sample Output 1
2 3 4 5 5 5 5 777771453
Sample Input 2
7 6 4 4 4 4 4 4 4 14 14 14 14 14 14 14 14 31 31 28 19 24 5 23 89 24 93 21 88
Sample Output 2
28 27 22 26 27 27 30
Sample Input 3
7 0 7 7 7 7 7 14 49 67 67 67 67 67 67 67 67
Sample Output 3
98
Hints
以下為範例測資 $1$ 的各個$e_i, x_i$，方便測試：
10 777771449
5 777771449
9 777771449
6 777771449
8 777771449
7 777771449
2 777771449
以下為範例測資 $2$ 的各個$e_i, x_i$，方便測試：
3 3
7 8
14 19
13 67
3 70
14 67
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 3~12 | $N = 1$ | 1 |
| 3 | 2, 13~22 | $Q = 0$ | 4 |
| 4 | 0~42 | $N, Q \le 2300$ | 7 |
| 5 | 0~22, 43~62 | $N \le 55$或$Q \le 15$ | 7 |
| 6 | 0~42, 63~82 | $N, Q \le 7500$ | 7 |
| 7 | 0~22, 43~62, 83~102 | $N \le 300$或$Q \le 300$ | 7 |
| 8 | 0~122 | 無特別限制 | 67 |