Query-Max

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
hhoangcpascal
Dạng bài
Đ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