52. 區間最大值

0 Judge

Code: 0


區間最大值

題目敘述

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