1719 測資加強 已 rejudge
2325 . 老鼠與貓咪
TopCoder
Tags
Description
老鼠是個天才兒童，在三歲時養了一隻貓咪，在五歲時學會了 LCT，七歲時成功用魔法趕走了兇巴巴的史萊姆，最近則順利拿到書卷獎。
貓咪每天都要舉 1000kg 的槓鈴，只是今天老鼠把槓鈴放在磅秤上後，發現槓鈴竟然少了 24g。
於是老鼠帶貓咪去地下格鬥場，總共有 $n+1$ 個選手，編號為 $0\sim n$。
編號 $i$（$0\leq i\leq n$）的選手的體力為 $a_i$，一開始編號 $0$ 的選手為衛冕者，剩下的選手會按照編號由小到大依序向衛冕者挑戰。
假設衛冕者的體力為 $x$，挑戰者的體力為 $y$，若 $x\geq y$，則挑戰者挑戰失敗，衛冕者繼續衛冕，且體力變成 $x-y$；若 $x<y$，則挑戰者挑戰成功，成為衛冕者，且體力變成 $y-x$。
$a_1\sim a_n$ 是固定的，但是 $a_0$ 會隨著編號 $0$ 參賽者的心情改變，貓咪總共有 $q$ 個疑問：如果編號 $0$ 的參賽者體力是 $a_0$，並且現在編號 $p$ 的選手挑戰完了，那麼此時衛冕者的體力是多少？
Input Format
第一行有兩個正整數 $n,q$，代表有 $n+1$ 位選手和 $q$ 個疑問。
第二行有 $n$ 個非負整數 $a_1\sim a_n$，代表編號 $1\sim n$ 選手的體力。
接下來 $q$ 行，每行有一個非負整數和一個正整數 $a_0,p$，代表編號 $0$ 選手的體力和現在編號 $p$ 的選手挑戰完了。
對於所有測試資料：
- $1\leq n,q\leq 10^ 6$
- $0\leq a_i\leq 10^ 6$（$1\leq i\leq n$）
- $0\leq a_0\leq 10^ 6$
- $1\leq p\leq n$
Output Format
對於每個疑問，回答若編號 $0$ 的參賽者體力是 $a_0$，且現在編號 $p$ 的選手挑戰完了，此時衛冕者的體力是多少。
Sample Input 1
3 4
7 10 2
2 1
13 2
20 2
5 3
7 10 2
2 1
13 2
20 2
5 3
Sample Output 1
5
4
3
6
4
3
6
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~5 | $n,q\le 3000$ | 17 |
| 3 | 1, 6~10 | $a_i\le a_{i+1}$（$0\le i<n$） | 19 |
| 4 | 0~15 | 無其他限制 | 64 |