Query-Max
Xem PDF
Điểm:
400 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\). Cho \(Q\) thao tác thực hiện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:
- \(1\) \(u_i\) \(v_i\) \(x_i\): Tăng mỗi phần tử từ vị trí \(u_i\) tới vị trí \(v_i\) lên \(x_i\) đơn vị.
- \(2\) \(u_i\) \(v_i\): Tìm giá trị lớn nhất trong các phần tử từ vị trí \(u_i\) tới vị trí \(v_i\).
Yêu cầu: Thực hiện tất cả lần lượt \(Q\) thao tác, và in ra kết quả của thao tác loại \(2\).
Input
- Dòng thứ nhất gồm hai số nguyên dương \(N, Q\).
- Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((A_i \leq 10^9)\).
- \(Q\) dòng tiếp theo, với dòng thứ \(i\): số đầu tiên trên dòng là \(1\) hoặc \(2\). Số \(1\) theo sau bởi ba số nguyên dương \(u_i\), \(v_i\) và \(x_i\) \((1 \leq u_i \leq v_i \leq N\), \(1 \leq x_i \leq 10^9)\). Số \(2\) theo sau bởi hai số nguyên dương \(u_i\) và \(v_i\) \((1 \leq u_i \leq v_i \leq N)\).
Output
- Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra giá trị lớn nhất trong các phần tử từ vị trí \(u\) tới vị trí \(v\).
Scoring
- Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3\), \(Q \leq 10^3\).
- Subtask \(2\) (\(20\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\), chỉ có các thao tác loại \(2\).
- Subtask \(3\) (\(20\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\), các thao tác \(1\) luôn được thực hiện trước các thao tác \(2\).
- Subtask \(4\) (\(30\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\).
Example
Test 1
Input
5 4
2 6 3 5 8
1 2 5 3
2 1 4
1 3 4 2
2 3 5 Output
9
11
Bình luận
Dạng bài CTDL là dạng gì thế anh :v
-
0
lqdcoder11991
8:08 a.m. 5 Tháng 6, 2021
-
-1
n3nhannxt
11:36 a.m. 10 Tháng 10, 2020
-
2
BeTapDi
7:22 p.m. 14 Tháng 9, 2020
4 bình luận nữasegment tree có vẻ ổn
Data-structure that means: Cấu trúc dữ liệu :))
ở dưới a hoàng có viết á :), mà nói thẳng là cấu trúc dữ liệu :v