a823. Kevin 去夜唱 - 旦旦解題農場

內容

Kevin 是一位身高 $189$ 的肥宅，他在進入大學之後加入了籃球隊因此變成夯哥，而今天他和球隊的人一起去 KTV 夜唱，在包廂裡他們玩了一個遊戲。

在桌子上總共擺了 $N$ 個容量為 $10^{100}$ ml 的酒杯，每個酒杯一開始都是空的，在遊戲進行中，會對酒杯進行 $3$ 種操作:

將由左邊數來第 $l$ 到第 $r$ 個酒杯各添上 $k$ ml 的酒
將由左邊數來第 $l$ 到第 $r$ 個酒杯的酒都倒到 $k$ ml (比 $k$ 少就添加，太多則倒掉)
讓 Kevin 將由左邊數來第 $l$ 到第 $r$ 個酒杯裡的酒都喝掉，並倒回原本的量

但 Kevin 已經連直線都走不穩了，怕自己回不了家，所以有時他也會對這些酒杯進行另一個操作:

將由左邊數來第 $l$ 到第 $r$ 個酒杯中倒最滿的那杯藏起來(如有多個最滿的取第一個)

隔天， Kevin 想要知道他前一天晚上每次喝到底喝了多少，透過昨天夯哥們的限動可以得知所有 $Q$ 個操作的詳細內容，但他正經歷宿醉的痛苦，所以請你寫一個程式幫他計算吧。

輸入說明

第一列有兩個正整數 $N,Q$ $(1\leq N,Q\leq 2\times 10^5)$

接著有 $Q$ 列，每列有一個操作，對應到題目敘述中 $4$ 種操作，每種操作輸入格式依序如下:

1 l r k (將第 $[l,r]$ 個酒杯添加 $k$ ml)
2 l r k (將第 $[l,r]$ 個酒杯倒到恰好 $k$ ml)
3 l r (將第 $[l,r]$ 個酒杯的酒喝掉)
4 l r (將第 $[l,r]$ 個酒杯中酒最多的藏起來)

($1\leq l \leq r\leq N,\ \ 0\leq k\leq 10^8)$
保證 $l,r$ 不會超出當前剩餘酒杯的數量

輸出說明

對於每筆第 $3$ 種操作，輸出一數代表 Kevin 在那次喝了多少 ml

範例輸入

範例輸出

9
3

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (1%): 1.0s , <10M
公開測資點#1 (1%): 1.0s , <1K
公開測資點#2 (1%): 1.0s , <1K
公開測資點#3 (1%): 1.0s , <1K
公開測資點#4 (1%): 1.0s , <1K
公開測資點#5 (1%): 1.0s , <1K
公開測資點#6 (1%): 1.0s , <1M
公開測資點#7 (1%): 1.0s , <1M
公開測資點#8 (1%): 1.0s , <1M
公開測資點#9 (1%): 1.0s , <1M
公開測資點#10 (1%): 1.0s , <1M
公開測資點#11 (1%): 1.0s , <1M
公開測資點#12 (1%): 1.0s , <1M
公開測資點#13 (1%): 1.0s , <1M
公開測資點#14 (1%): 1.0s , <1M
公開測資點#15 (1%): 1.0s , <1M
公開測資點#16 (1%): 1.0s , <1M
公開測資點#17 (1%): 1.0s , <1M
公開測資點#18 (1%): 1.0s , <1M
公開測資點#19 (1%): 1.0s , <1M
公開測資點#20 (1%): 1.0s , <1M
公開測資點#21 (1%): 1.0s , <1M
公開測資點#22 (1%): 1.0s , <1M
公開測資點#23 (1%): 1.0s , <1M
公開測資點#24 (1%): 1.0s , <1M
公開測資點#25 (1%): 1.0s , <1M
公開測資點#26 (1%): 1.0s , <1M
公開測資點#27 (1%): 1.0s , <1M
公開測資點#28 (1%): 1.0s , <1M
公開測資點#29 (1%): 1.0s , <1M
公開測資點#30 (1%): 1.0s , <1M
公開測資點#31 (1%): 1.0s , <1M
公開測資點#32 (1%): 1.0s , <1M
公開測資點#33 (1%): 1.0s , <1M
公開測資點#34 (1%): 1.0s , <1M
公開測資點#35 (1%): 1.0s , <1M
公開測資點#36 (1%): 1.0s , <10M
公開測資點#37 (1%): 1.0s , <10M
公開測資點#38 (1%): 1.0s , <10M
公開測資點#39 (1%): 1.0s , <10M
公開測資點#40 (1%): 1.0s , <10M
公開測資點#41 (1%): 1.0s , <10M
公開測資點#42 (1%): 1.0s , <10M
公開測資點#43 (1%): 1.0s , <10M
公開測資點#44 (1%): 1.0s , <10M
公開測資點#45 (1%): 1.0s , <10M
公開測資點#46 (1%): 1.0s , <10M
公開測資點#47 (1%): 1.0s , <10M
公開測資點#48 (1%): 1.0s , <10M
公開測資點#49 (1%): 1.0s , <10M
公開測資點#50 (1%): 1.0s , <10M
公開測資點#51 (1%): 1.0s , <10M
公開測資點#52 (1%): 1.0s , <10M
公開測資點#53 (1%): 1.0s , <10M
公開測資點#54 (1%): 1.0s , <10M
公開測資點#55 (1%): 1.0s , <10M
公開測資點#56 (1%): 1.0s , <10M
公開測資點#57 (1%): 1.0s , <10M
公開測資點#58 (1%): 1.0s , <10M
公開測資點#59 (1%): 1.0s , <10M
公開測資點#60 (1%): 1.0s , <10M
公開測資點#61 (1%): 1.0s , <10M
公開測資點#62 (1%): 1.0s , <10M
公開測資點#63 (1%): 1.0s , <10M
公開測資點#64 (1%): 1.0s , <10M
公開測資點#65 (1%): 1.0s , <10M
公開測資點#66 (1%): 1.0s , <10M
公開測資點#67 (1%): 1.0s , <10M
公開測資點#68 (1%): 1.0s , <10M
公開測資點#69 (1%): 1.0s , <10M
公開測資點#70 (1%): 1.0s , <10M
公開測資點#71 (1%): 1.0s , <10M
公開測資點#72 (1%): 1.0s , <10M
公開測資點#73 (1%): 1.0s , <10M
公開測資點#74 (1%): 1.0s , <10M
公開測資點#75 (1%): 1.0s , <10M
公開測資點#76 (1%): 1.0s , <10M
公開測資點#77 (1%): 1.0s , <10M
公開測資點#78 (1%): 1.0s , <10M
公開測資點#79 (1%): 1.0s , <10M
公開測資點#80 (1%): 1.0s , <10M
公開測資點#81 (1%): 1.0s , <10M
公開測資點#82 (1%): 1.0s , <10M
公開測資點#83 (1%): 1.0s , <10M
公開測資點#84 (1%): 1.0s , <10M
公開測資點#85 (1%): 1.0s , <10M
公開測資點#86 (1%): 1.0s , <10M
公開測資點#87 (1%): 1.0s , <10M
公開測資點#88 (1%): 1.0s , <10M
公開測資點#89 (1%): 1.0s , <10M
公開測資點#90 (1%): 1.0s , <10M
公開測資點#91 (1%): 1.0s , <10M
公開測資點#92 (1%): 1.0s , <10M
公開測資點#93 (1%): 1.0s , <10M
公開測資點#94 (1%): 1.0s , <10M
公開測資點#95 (1%): 1.0s , <10M
公開測資點#96 (1%): 1.0s , <10M
公開測資點#97 (1%): 1.0s , <10M
公開測資點#98 (1%): 1.0s , <10M
公開測資點#99 (1%): 1.0s , <10M

提示：

Subtask 1 : $1\leq N,Q\leq 2\times 10^3$

Subtask 2 : 對於第 $1,2,4$ 種操作保證 $l=r$

Subtask 3 : 沒有第 $4$ 種操作

Subtask 4 : 無特殊限制

標籤:

data structure

出處:

2022 復旦校內初選複賽 [管理者：

fdhs107_KonChin... (konchin)

]

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