52. 區間最大值

區間最大值

題目敘述

Sylveon拿到了一個有N個數字的序列$a_1,a_2,a_3...a_n$，想對這些數列做一些奇怪的事情

指令

• 1 x y 查詢$a_x,a_{x+1},...a_y$的最大值是多少
• 2 x c 把$a_x$加上$c$

聰明的你可以完成$Sylveon$的指令嗎?

你可以聽聽最近的一首新歌放鬆心情，但是對你解這題一點幫助也沒有

輸入說明

有多筆測資，每筆測資第一行包含兩個數字$N,K$表示數列有$N$個數字，共有$K$條指令。下一行有兩$N$個數字，分別代表$a_1,a_2,a_3...a_n$一開始的數值，接下來有$K$行，每行的指令格式與題目敘述相同。

• $N\leq 10^5$
• $K\leq 10^4$
• $-100\leq An,c \leq 100$
• 所有操作都是合法的

輸出說明

對於每個查詢，輸出其結果，並換行。

範例輸入

10 3
-13 10 -99 -75 52 86 -52 -21 -44 -5 
1 7 10
2 9 87
1 7 10

範例輸出

-5
43

Judge Setting

run-time limit: 300 ms
memory limit: 65536000 byte
測資數量: 0