2378 . 補牙
TopCoder
Tags
Description
瓜瓜因為非常討厭牙膏的味道所以很不喜歡刷牙，結果他的牙齒就全部都蛀牙了，牙齒就被蛀牙侵蝕，變得歪七扭八。
身為刷牙之神，施巨砲最討厭看到蛀牙和不整齊的牙齒，所以他決定把瓜瓜的牙齒都依照他喜歡的方式補整齊來拯救瓜瓜的牙齒。
瓜瓜有 $n$ 顆牙齒，第 $i$ $(1 \leq i \leq n)$ 顆牙齒的座標為 $(i,a_i)$ 。
施巨砲身為數學家，他最喜歡的牙齒必須要滿足高度是非嚴格遞減的數列。具體地說，對於一個區間 $[l,r]$，必須要滿足 $a_i \geq a_{i+1}$ $(l \leq i \leq r-1)$。並且施巨砲每次可以選一顆牙齒，進行補牙的動作讓他的 $a_i$ 增加 $1$。
現在有 $q$ 筆操作，每一個操作可能是將第 $p$ 顆牙齒的高度修改為 $x$，或是詢問第 $l \sim r$ 顆牙齒總共需要修補幾次才能成為施巨砲喜歡的牙齒。你能幫助施巨砲補好瓜瓜的牙齒嗎？
Input Format
第一行會有一個正整數 $n,q$ 代表瓜瓜有幾顆牙齒和總共有幾筆操作。
接下來會有 $n$ 個正整數 $a_1 \sim a_n$ 代表 $n$ 顆牙齒的高度。
接下來 $q$ 行每行會有一個 $t$ 代表操作的種類：
若 $t=0$ 則是修改，會接著再有 $p,x$ 代表第 $p$ 顆牙齒的高度要改成 $x$。
若 $t=1$ 則是詢問，會接著再有 $l,r$ 代表要詢問第 $l \sim r$ 顆牙齒最少要補幾次牙齒。
對於所有測試資料：
- $1 \leq n,q \leq 2 \times 10^ 5 $
- $1 \leq a_i,x \leq 10^ 9 $
- $1 \leq p,l,r \leq n $
Output Format
對於每個 $t=1$ 的詢問，輸出一個整數代表最少要補幾次牙齒
Sample Input 1
5 5
5 2 4 10 2
1 1 3
1 4 4
1 2 5
0 4 2
1 2 5
5 2 4 10 2
1 1 3
1 4 4
1 2 5
0 4 2
1 2 5
Sample Output 1
2
0
14
2
0
14
2
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~10 | $n,q\leq 5000$ | 13 |
| 3 | 11~20 | $t=1$ | 27 |
| 4 | 0~45 | 無其他限制 | 60 |