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 r1 x y13 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