c216: kevin 愛種樹
標籤 :
通過比率 : 64% (7 人 / 11 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2017-07-07 15:11

內容 :

kevin有n棵樹

每棵高度是 ai 公分  (1 <= i , ai <= 100000)

這些樹木很神奇

他們會在kevin不注意的時候

一起長高 k ( k < 10 ^ 6 ) 公分

但是一旦他們長超過 100000 公分

他們就會經不起強風而斷裂

( ex 100001 cm 的樹 會斷成 1cm ,  223456 cm 的樹會斷成 23456 cm

而kevin想記錄他們的身長狀況

所以他會記錄 第 aL~aR 的樹的高度和

但是樹太多了

所以他想請你幫忙計算 第 aL~aR 的樹的高度和 到底是多少

輸入說明

單筆輸入

第一行輸入兩個整數 n , m (( n < 10 ^ 5 , m < 5 * 10 ^ 5

分別代表有幾棵樹 跟 kevin 對樹的紀錄

第二行n個高度 ai  ((1 <= ai <= 10 ^ 5

第三行開始有m個紀錄op ((op = 1 or 2

如果 op = 1 輸入 k (( 1 <= k <= 10 ^ 6

每棵樹長高了k公分

如果 op = 2輸入 L , R (( 1 <= L <= R <= n

代表詢問 第 aL ~ aR 棵樹之間的高度和

輸出說明

對於每個詢問輸出一行 第 aL ~ aR 棵樹之間的高度和

範例輸入
5 3
1 2 3 4 5
2 1 5
1 99999
2 1 5
範例輸出
15
100010
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (6%): 1.0s , <1K
公開 測資點#1 (6%): 1.0s , <1K
公開 測資點#2 (6%): 1.0s , <1K
公開 測資點#3 (6%): 1.0s , <1K
公開 測資點#4 (6%): 1.0s , <1K
公開 測資點#5 (7%): 1.0s , <1M
公開 測資點#6 (7%): 1.0s , <1M
公開 測資點#7 (7%): 1.0s , <1M
公開 測資點#8 (7%): 1.0s , <1M
公開 測資點#9 (7%): 1.0s , <1M
公開 測資點#10 (7%): 1.0s , <10M
公開 測資點#11 (7%): 1.0s , <1M
公開 測資點#12 (7%): 1.0s , <10M
公開 測資點#13 (7%): 1.0s , <10M
公開 測資點#14 (7%): 1.0s , <10M
提示 :

第一次訊問 第1~5棵樹的高度和 所以是 1 + 2 + 3 + 4 + 5 = 15

然後他們一起長高了 99999 cm

所以 高度變為 100000 100001 100002 100003 100004

第2~5棵樹高度太高而斷裂 樹高變成 100000 1 2 3 4

第二次詢問第1~5棵樹的高度和 所以是 100000 + 1 + 2 + 3 + 4 = 100010

標籤:
出處:
妹妹0u0 [編輯:
justinO__o (Q//////////^////////...)
]
編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」