138. Day 2 PH. 魔貫光殺砲

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
      表示比克要消滅區間$[l,r]$的魔物,請告訴比克大魔王他最少需要多少能量值才能達到大界王神的要求,保證$1 \leq l \leq r \leq n$
    • 1 x y
      表示編號$x$的魔物損毀,大界王神將其用等級值為$y$的魔物替換,保證$1 \leq x \leq n$,$y$為int範圍

輸出說明

  • 輸出每次比克發射魔貫光殺砲最少需要多少能量值才能達到大界王神的要求。

範例輸入

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

配分方法

  • 10% $n \leq 1000$
  • 30% $n \leq 7000$
  • 60% $n \leq 10^4$

Judge Setting

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