回『原創/不分類題庫』
r302. 河谷守護者（Valley Keeper）
標籤 :
通過比率: 4人/ 4人 ( 100%) [非即時]
評分方式：
Tolerant

最近更新 : 2025-10-04 22:25

內容

在遙遠的王國邊境，有一排古老的石板路，每塊石板都有一個魔力數值。某天，暴雨襲來，守護者需要在石板上施放魔法，降低（把數值截斷到某上限）、增益（整段增加固定數值），或查詢石板魔力總和以確保橋樑穩固。你要幫助守護者快速處理大量的魔法指令。

要求：給定初始數列，支援三種操作：

  1. 0 l r x：對區間 [l, r] 執行 a_i = min(a_i, x)（range chmin）。

  2. 1 l r x：對區間 [l, r] 執行 a_i += x（range add）。

  3. 2 l r：查詢區間 [l, r] 的元素總和（range sum）。

索引從 1 開始，所有操作都是左右端點包含（inclusive）。

輸入說明

第一行：兩個整數 n q，分別為石板數與操作數。
第二行：n 個整數，為初始陣列 a_1 ... a_n。
接下來 q 行，每行為一個操作：

  • 若操作種類為 0 或 1：三個整數 t l r x（t = 0 或 1）。

  • 若操作種類為 2：三個整數 t l r（t = 2，無 x）。

注意輸入皆用空白分隔。

  • 1 ≤ n, q ≤ 2*10^5

  • |a_i| ≤ 10^{18}

  • 對於操作：1 ≤ l ≤ r ≤ n

  • |x| ≤ 10^{18}

  • 輸出與中間計算請以 64-bit signed（例如 C++ 的 long long）處理。

輸出說明

對每個 t = 2 的查詢輸出一行，表示對應區間的總和（以 64-bit 有號整數表示）。

範例輸入 #1 
5 5
5 3 7 1 9
2 1 5
0 2 4 4
2 1 5
1 3 5 2
2 3 3
範例輸出 #1 
25
22
6
測資資訊：
記憶體限制： 512 MB
不公開 測資點#0 (1%): 1.0s , <1K
不公開 測資點#1 (19%): 1.0s , <1K
不公開 測資點#2 (19%): 1.0s , <1K
不公開 測資點#3 (19%): 1.0s , <1K
不公開 測資點#4 (1%): 1.0s , <1K
不公開 測資點#5 (1%): 1.0s , <1K
不公開 測資點#6 (19%): 1.0s , <1K
不公開 測資點#7 (1%): 1.0s , <1K
不公開 測資點#8 (19%): 1.0s , <1K
不公開 測資點#9 (1%): 1.0s , <1K
提示 ：
標籤:
出處:
Zaim [管理者： chenwei98050 ... (陳維（Z）) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」