猴猴共和國面臨外族入侵，猴猴之王必須提升自己的實力才能帶領眾猴猴們抵禦敵人的入侵，於是猴猴之王來到了試煉場。
試煉場共有$N$個關卡，闖關的規則是要從第1個關卡開始，依序挑戰到第$N$個關卡。關卡有兩種類型，分別是戰鬥關卡，會扣除挑戰者的血量；以及休息關卡，會恢復挑戰者的血量。用長度為$N$的整數陣列$a$來表示每個關卡的資訊，若$a_i<0$，代表第i關是戰鬥關卡；若$a_i\geq0$，則代表第i關是休息關卡。不論第i關的關卡類型為何，挑戰第i關時，挑戰者的血量會變成（目前的血量$+a_{i}$），若中途血量$\leq 0$則死亡。
不過猴猴之王有特權，他可以選擇從第$l$關開始挑戰，並在挑戰完第$r$關後離開。猴猴之王不想死掉，他想知道一開始最少需要多少血量才能順利完成關卡，但猴猴之王數學不好，所以請你幫寫一個程式，程式需要有以下兩個功能：
1. 把$a_i$的值修改為$val$
2. 給定一組$l, r$，令一開始的血量為$k$，請輸出在「從第$l$關開始挑戰，至挑戰完第$r$關後離開，且中途不死亡」的前提下，$k$的最小值。
輸入第一行有一個整數N，代表陣列a的長度。
第二行有N個整數，第i個整數為$a_i$。
第三行為一個整數Q，代表操作次數。
接下來有Q行，第$i$行有三個整數，第一個整數$t_i$，代表操作的種類。
1. $t_i=1$時，代表修改操作，同一行的第二和第三個數分別為$p,val$，代表把$a_p$的值修改成$val$。
2. $t_i=2$時，代表詢問操作，同一行的第二和第三個數分別為$l,r$，請輸出「在能夠從第$l$關開始挑戰，挑戰完第$r$關時離開，且中途不死亡」的前提下，k的最小值。
測資限制
$1\leq N \leq 2\times 10^5$
$1\leq Q \leq 2\times 10^5$
$-10^9 \leq a_i, val \leq 10^9$
$1\leq l \leq r \leq N$
$1\leq p \leq N$
對於每筆詢問$(t_i = 2)$，請輸出一行，包含一個正整數$k$，代表最小的起始血量。
$k > 0$
5 3 -2 -5 4 -2 5 2 2 4 2 1 4 2 1 1 2 3 4 2 1 5
8 5 1 6 5
8 6 -2 3 6 -4 3 6 1 7 2 2 5 1 4 -2 2 2 5 2 6 8 2 1 3 1 3 -5 2 1 3
3 6 1 1 2
本題共有三組子任務，條件限制如下所示。
子題一 29%
$1\leq N, Q \leq 2000$
子題二 37%
$t_i = 2$ $(1\leq i \leq Q)$
子題三 34%
無額外限制
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||