901 . 斷層考察

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

alvingogo

User's AC Ratio

50.0% (5/10)

Submission's AC Ratio

13.5% (12/89)

Tags

ioicamp ioicamp-2025

Description

這天，巴已己、巴已已、和巴已巳結伴去一座小島上旅行。他們在島上發現了一道長達五十萬公里的大斷層，每天都在活躍著，而且斷層的活動居然是他們一念之間就可以掌控的！

巴已己說，要有山，便有了山。他在心裡想好兩個數字 $a, b$，對於斷層起始處開始算 $x$ 公里的位置，該處的海拔會被抬升到至少 $ax + b$ 公尺。

巴已已說，山不該如此高聳，於是巴已已一記手刀，山峰被夷平了。他手刀將會砍在海拔為 $c$ 的地方，所有海拔高度高過 $c$ 公尺的地方都會被巴已已大手一揮砍成 $c$ 公尺。

在巴已己和巴已已互鬥的過程中，巴已巳想實地考察斷層活動。喜歡登高山的他會走過斷層中間的一小段，並紀錄下海拔最高的位置。

每一天，他們在旅行日記上記下當天是巴已己造出了一座山、巴已已揮出一記手刀、還是巴已巳出門進行了一次考察。旅程結束之後，巴已巳發現他的斷層考察紀錄居然弄丟了！好在他們的旅行日記還保留著，你能根據他們的旅行日記幫巴已巳還原出他的考察紀錄嗎？

（以上情節純屬虛構，如有雷同實為巧合）

請你維護一個序列。這個序列一開始都是 $0$，請支援 $Q$ 次操作：

  1. 序列所有數字跟直線 $ax + b$ 取 $\max$
  2. 序列所有數字跟常數 $c$ 取 $\min$
  3. 詢問區間內的最大值

Input Format

第一行有兩個正整數 $N, Q$，代表斷層長度和旅行日記上有幾筆紀錄，也就是序列長度和接下來的操作數量。

接下來的 $Q$ 行，每行代表一次操作，形如：

  • 1 a b：巴已己造出了一座山，序列所有數字跟直線 $ax + b$ 取 $\max$
  • 2 c：巴已已砍出一記手刀，序列所有數字跟常數 $c$ 取 $\min$
  • 3 l r：巴已巳出門考察斷層活動，詢問序列中區間 $[l, r]$ 的最大值
  • $1 \leq N, Q \leq 5 \times 10^ 5$
  • $|a| \leq 10^ {12}$
  • $|b|, |c| \leq 10^ {18}$
  • $1 \leq l \leq r \leq N$

Output Format

對於巴已巳每次的斷層考察，請回答那次考察紀錄下的最高海拔（公尺）。

換句話說，對於每次的第三種詢問，請輸出詢問結果。

Sample Input 1

5 12
1 2 4
3 1 5
3 1 3
3 4 4
1 -3 16
3 1 5
3 1 3
3 4 4
2 11
3 1 5
3 1 3
3 4 4

Sample Output 1

14
10
12
14
13
12
11
11
11

Sample Input 2

2 8
1 2 0
3 1 1
3 2 2
2 3
1 1 0
1 1 -1
3 1 1
3 2 2

Sample Output 2

2
4
2
3

Sample Input 3

10 20
1 -453353365212 674873070581144417
1 -85160889177 269787146516281711
1 -930606453139 825606402140251908
3 1 2
3 3 3
1 617371516011 -624022640298407667
1 -888181834668 953248485257432197
1 715351850672 -76635650028418802
1 73081726339 -538387878798345572
2 -615715699483791915
3 4 5
3 1 4
1 -596772663595 -424950645442517140
2 -446076358334831415
1 -71965294359 -113670135348127706
3 5 6
2 -596446837547520399
1 891165226159 830876300085435778
2 -391653930343521915
3 2 3

Sample Output 3

825605471533798769
825603610320892491
-615715699483791915
-615715699483791915
-113670495174599501
-391653930343521915

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~9 $N, Q \leq 5000$ 10
3 10~14 只有第一、三種操作 20
4 15~22 $a \geq 0$ 40
5 0~35 無額外限制 30

Testdata and Limits

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