62. 好多盤子喔~!

0 Judge

Code: 0


好多盤子喔~!

題目敘述

「電競牙刷,你一定要擁有的電競好夥伴!」一旁的海報寫著實用商品的宣傳話語。

這裡是電競專賣會,販賣各種實用又炫砲的電競商品。你現在人在電競牙刷的賣場,有$N$個人排隊著,打算搶購待會即將開賣的電競牙刷。不過現在還不知道電競牙刷的售價為何,而每個人$i$都有自己的預估花費金額$P_i$元,表示他們分別願意花多少錢來買電競牙刷。

心動動的你冒出了一個疑問:「如果知道每個人的預估花費金額,能不能有效地求得連續一群人的盤子度呢?」(盤子度的定義請參考下面)

將一群人$[l,r]$分成前後兩群人$[l,m]$和$[m+1,r]$,則這群人$[l,r]$的盤子切割值為:前半群人$[l,m]$的最大預估花費金額減去後半群人$[m+1,r]$的最小預估花費金額,也就是$\max_{P_l,P_{l+1}...P_m} - \min_{P_{m+1},P_{m+2}...P_r}$。

一群人$[l,r]$的盤子度為他們最大的盤子切割值。(根據切割人群的方法不同,盤子切割值也會不一樣,你需要找出最大的那個!)

你想要多次地求得連續一群人的盤子度,而有時候有些人的預估花費金額可能會改變。

輸入說明

第一行給定兩個整數$N(2\leq N\leq 10^5)$與$Q(1\leq Q\leq 10^5)$,以空白間隔,表示有$N$個人排隊及有$Q$筆事件。

第二行有$N$個以空白間隔的整數$P_1,P_2...P_N (0\leq |P_i|\leq 2*10^9)$,表示每個人的預估花費金額。

接下來$Q$行,每行先給定一個整數$t(1\leq t\leq 2)$,表示事件類型。若$t=1$,表示有人預估花費金額改變了,接著會有兩個整數$p(1\leq p\leq N)$和$v(0\leq |v|\leq 2*10^9)$,表示隊伍中第$p$個人的預估花費金額更改為$v$;若$t=2$,接著給定兩個整數$l$和$r(1\leq l<r\leq N)$表示你想要知道連續的一群人$[l,r]$的盤子度。

輸出說明

對於所有$t=2$的事件,輸出一個整數表示他們的盤子度並換行。

範例輸入

8 5
8 3 7 1 1 4 2 5
2 1 6
1 3 -3
2 1 6
2 4 5
2 5 8

範例輸出

7
11
0
2

子任務

  • 子任務一($5\%$):$N,Q\leq 500$

  • 子任務二($15\%$):$N,Q\leq 3000$

  • 子任務三($15\%$):任意時刻所有人的預估花費金額非嚴格遞減,即 $P_i\geq P_{i+1}$

  • 子任務四($27\%$):所有人的預估花費金額皆不會改變

  • 子任務五($38\%$):無限制

提示

好大隻的姆咪


Judge Setting

run-time limit: 1000 ms
memory limit: 538443776 byte
測資數量: 25