TopCoder

餘切
pooh is 8

User's AC Ratio

93.3% (14/15)

Submission's AC Ratio

63.2% (74/117)

Tags

Description

瓜瓜因為非常討厭牙膏的味道所以很不喜歡刷牙,結果他的牙齒就全部都蛀牙了,牙齒就被蛀牙侵蝕,變得歪七扭八。
身為刷牙之神,施巨砲最討厭看到蛀牙和不整齊的牙齒,所以他決定把瓜瓜的牙齒都依照他喜歡的方式補整齊來拯救瓜瓜的牙齒。

瓜瓜有 n 顆牙齒,第 i (1in) 顆牙齒的座標為 (i,ai)

施巨砲身為數學家,他最喜歡的牙齒必須要滿足高度是非嚴格遞減的數列。具體地說,對於一個區間 [l,r],必須要滿足 aiai+1 (lir1)。並且施巨砲每次可以選一顆牙齒,進行補牙的動作讓他的 ai 增加 1

現在有 q 筆操作,每一個操作可能是將第 p 顆牙齒的高度修改為 x,或是詢問第 lr 顆牙齒總共需要修補幾次才能成為施巨砲喜歡的牙齒。你能幫助施巨砲補好瓜瓜的牙齒嗎?

Input Format

第一行會有一個正整數 n,q 代表瓜瓜有幾顆牙齒和總共有幾筆操作。
接下來會有 n 個正整數 a1an 代表 n 顆牙齒的高度。

接下來 q 行每行會有一個 t 代表操作的種類:
t=0 則是修改,會接著再有 p,x 代表第 p 顆牙齒的高度要改成 x
t=1 則是詢問,會接著再有 l,r 代表要詢問第 lr 顆牙齒最少要補幾次牙齒。

對於所有測試資料:

  • 1n,q2×105
  • 1ai,x109
  • 1p,l,rn

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

Sample Output 1

2
0
14
2

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~10 n,q5000 13
3 11~20 t=1 27
4 0~45 無其他限制 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2 4
1 2000 524288 65536 2 4
2 2000 524288 65536 2 4
3 2000 524288 65536 2 4
4 2000 524288 65536 2 4
5 2000 524288 65536 2 4
6 2000 524288 65536 2 4
7 2000 524288 65536 2 4
8 2000 524288 65536 2 4
9 2000 524288 65536 2 4
10 2000 524288 65536 2 4
11 2000 524288 65536 3 4
12 2000 524288 65536 3 4
13 2000 524288 65536 3 4
14 2000 524288 65536 3 4
15 2000 524288 65536 3 4
16 2000 524288 65536 3 4
17 2000 524288 65536 3 4
18 2000 524288 65536 3 4
19 2000 524288 65536 3 4
20 2000 524288 65536 3 4
21 2000 524288 65536 4
22 2000 524288 65536 4
23 2000 524288 65536 4
24 2000 524288 65536 4
25 2000 524288 65536 4
26 2000 524288 65536 4
27 2000 524288 65536 4
28 2000 524288 65536 4
29 2000 524288 65536 4
30 2000 524288 65536 4
31 2000 524288 65536 4
32 2000 524288 65536 4
33 2000 524288 65536 4
34 2000 524288 65536 4
35 2000 524288 65536 4
36 2000 524288 65536 4
37 2000 524288 65536 4
38 2000 524288 65536 4
39 2000 524288 65536 4
40 2000 524288 65536 4
41 2000 524288 65536 4
42 2000 524288 65536 4
43 2000 524288 65536 4
44 2000 524288 65536 4
45 2000 524288 65536 4