0 Judge
Code: 0
.; ̄'';. .;'' ̄'; ヽ__ \ / .-'' \ ''`, / ,' '; l.'l´ ̄ ̄ ̄'';l ',lヽ / l l | | \ / |'| | . ヽ i '| .ノし '' 'l i | へ .| ,___ _| ,,,,,-' '-,,,,, V__, \'; -ゝ ,ィ。;、゙゙゙ ゙゙,ィ。; |,/ ヽ iヾ! ` ̄ ` ̄ // \ | / i、 i_/ 「| /`ー-‐´ ! !! rvェェv-, / 〉、 | ./ / / '\ ,|ェェシ / / \ ヾ--´ イ / ̄ ̄'\ 'ヽ、___/ | ̄ ̄三三三三三三三三三三 \ / \ 三三三三三三三三三三三三三三 ::::::::::::,,\ノ')' ̄ ̄'ヽ 〈 ̄''''\ ''';三三三三三三三三三三三三三二ニ-_ 二二'ヽ / ノ') ̄ ̄ ̄ ̄ヽ ̄ ̄ ''''''| '三三三三三三三三三三三三三ヽヽヽ、'--'--'--------; 弌弌弌弌弌弌弌弌弌弌弌弌弌弌弌弌弌弌弌弌⊃ 二二;ヽ'ヽ / / / l |/ .三三三三三三三三三三三三三 ) ') ')) -----;,--' 二二; ;| f / / \ | ./ 三三三三三三三三三三三三三 ノノ ノノ ノノ,--;_;----; 二二; ;| | ´ -'-‐へ .| ./ 三三三三三三三三三三三三二ニ--' 二二; ;| |`,、 ー-.〈' .| / 三三三三三三三三三三三三三 二二; ;' |ノし y ノ '\ .| ./ 三三三三三三三三 二二; ' / へ ./ '\ / '| 二; ;/ ./ ノ \ .|⊃
來源(我有改過圖了):http://viper.2ch.sc/test/read.cgi/news4vip/1455518611/
比克大魔王的魔貫光殺砲天下無敵是眾所周知的事,它能一擊貫穿所有的敵人。近日比克在大界王神門下修行,大界王神準備了$n$個練習用魔物排成一個序列$S$,編號由$1$開始,接著給一些區間$[l,r]$的魔物叫比克去消滅。但是因為魔物是練習用的,不管怎樣攻擊魔物都不會有任何的損壞,因此比克只要射出大於該區間能量值的魔貫光殺砲就算合格了。
一個區間能量值是這樣計算的:
每個魔物身上都有一個等級值,我們將該區間所有魔物的等級值由小到大做排名,將該區間的每個等級值用它們的名次取代之後加總起來,就是該區間的能量值
例如一個區間中按造順序魔物的等級值為: $$[9,100,30,20,30,1,20,9]$$ 將所有等級值由小到大排名為: $$rank\; 1: \; 1$$ $$rank\; 2: \; 9$$ $$rank\; 3: \; 20$$ $$rank\; 4: \; 30$$ $$rank\; 5: \; 100$$ 將原來區間的等級值用它們的名次取代: $$[2,5,4,3,4,1,3,2]$$ 將之加總起來就是該區間的能量值: $$2+5+4+3+4+1+3+2=24$$
雖然魔貫光殺砲無法摧毀魔物,但是可以用拉扯的方式將魔物破壞掉。當比克不爽的時候,一隻練習用魔物會被比克撕爛,大界王神會將該魔物用其他魔物替換掉,替換的說明請看「輸入說明」。由於比克數學不好,每次都花費過多的能量發射魔貫光殺砲,這種浪費能源的行為在實戰中是要不得的,請你幫忙比克算出每次他最少所需要花費的能量值。
第一行有兩個整數$n(1 \leq n \leq 10^4),q(1 \leq q \leq 2 \times 10^4)$
接著有$n$個整數,為序列$S[1] \sim S[n]$,依序為大界王神準備的$n$個魔物的等級值,保證數字都在int範圍。
接著有$q$行,表示接下來依序發生的事件,事件有兩種:
0 l r
1 x y
13 6
100 30 5 9 100 30 20 30 1 20 9 5 23
0 4 11
0 1 5
1 5 1
0 4 11
0 1 5
0 1 13
24
14
20
15
50