TopCoder

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

50.0% (5/10)

Tags

Description

西元 2147483647 年,若干變形黑洞開始在世界上到處出現,這些黑洞會將所有人們往它身上吸引過去,造成了前所未有的危機!

你,身為一個資訊科學家,其實根本不在意人們的死活,你只在乎排在 x=1N 上,N 個人的行為,他們由於太過於恐懼,無法離開自己所在的 x 座標,只能上下移動來改變他們的 y 座標,而他們的 y 座標一開始是 y1,y2,yN

你希望能夠寫一支程式,用來記錄並模擬依序發生的事件,好讓你能夠在途中隨時得到你想要的資訊。

事件的種類如下:

  • 1lrp:一個變形黑洞出現了!他形如一條出現在 (l,p)(r,p) 的線段,並將所有 x 座標介在 [l,r] 的人的 y 座標 yi,改成 fp(yi)。更改完畢後,這個黑洞就會消失。
  • 2lrdx 座標介在 [l,r] 的人產生了恐懼,他們決定一起平移,也就是讓自己的 y 座標加上 dd 可能為負)。
  • 3lr:你很好奇 x 座標介在 [l,r] 的人的 y 座標總和,請輸出之。
  • 4lr:你很好奇 x 座標介在 [l,r] 的人的 y 座標最大值,請輸出之。
  • 5lr:你很好奇 x 座標介在 [l,r] 的人的 y 座標最小值,請輸出之。

其中,fp(y)={p+ypif ypppyif y<p,意即變形黑洞會嘗試把指定區間的人全部往自己吸引過去。

Input Format

輸出首行有兩個正整數 N,Q,代表你觀察的人數以及事件的數量。

接下來一行共 N 個數字 y1,y2,yN,代表 x 座標是 i 的人,y 座標一開始是 yi

接下來 Q 行依序是事件發生的順序,每行先是一個 k 代表事件種類,接著兩個正整數 l,r,代表事件所對應到的區間,最後可能還有一個整數 pd,代表第一種或第二種事件的額外參數。

所有同行相鄰數字以單一空格隔開。

  • 1N,Q2×105
  • 0|yi|107
  • 1k5
  • 1lrN
  • 0|p|,|d|107

Output Format

對於每筆你好奇的資訊,請輸出正確的答案於一行。

Sample Input 1

7 8
3 5 4 6 1 8 2
3 2 5
5 6 7
1 1 5 0
3 3 6
2 4 7 -5
4 5 7
1 3 6 -3
3 1 7

Sample Output 1

16
2
13
3
-9

Hints

Problem Source

IOICamp 2021 Day5 pM

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~35 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 262144 65536 1 2
1 2000 262144 65536 2
2 2000 262144 65536 2
3 2000 262144 65536 2
4 2000 262144 65536 2
5 2000 262144 65536 2
6 2000 262144 65536 2
7 2000 262144 65536 2
8 2000 262144 65536 2
9 2000 262144 65536 2
10 2000 262144 65536 2
11 2000 262144 65536 2
12 2000 262144 65536 2
13 2000 262144 65536 2
14 2000 262144 65536 2
15 2000 262144 65536 2
16 2000 262144 65536 2
17 2000 262144 65536 2
18 2000 262144 65536 2
19 2000 262144 65536 2
20 2000 262144 65536 2
21 2000 262144 65536 2
22 2000 262144 65536 2
23 2000 262144 65536 2
24 2000 262144 65536 2
25 2000 262144 65536 2
26 2000 262144 65536 2
27 2000 262144 65536 2
28 2000 262144 65536 2
29 2000 262144 65536 2
30 2000 262144 65536 2
31 2000 262144 65536 2
32 2000 262144 65536 2
33 2000 262144 65536 2
34 2000 262144 65536 2
35 2000 262144 65536 2