Giá trị lớn nhất

Xem PDF

Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một dãy gồm \(n\) phần tử có giá trị ban đầu bằng \(0\).

Cần thực hiện \(m\) thao tác thuộc hai loại:

  • Tăng giá trị của mỗi phần tử trong một đoạn con liên tiếp lên vài đơn vị.
  • Tìm giá trị lớn nhất trong đoạn con bất kỳ

Input

  • Dòng đầu tiên: Chứa hai số \(n,m\) \((1 \le n \le 50000, 1 \le m \le 10^5)\)
  • \(m\) dòng tiếp theo, mỗi dòng có thể có một trong hai định dạng sau:
  • 0 u v k: Tăng mỗi phần tử từ vị trí \(u\) đến vị trí \(v\) lên \(k\) đơn vị \((1 \le u \le v \le n, 0 < k)\)
  • 1 u v: Cho biết giá trị lớn nhất thuộc đoạn \([u, v]\) là bao nhiêu?

Dữ liệu vào đảm bảo giá trị của một phần tử không bao giờ vượt quá \(2^{31}-1\)

Output

  • Với mỗi câu hỏi, ghi ra đáp án trên từng dòng

Example

Test 1

Input
6 3
0 1 3 3
0 4 6 4
1 1 6
Output
4

Bình luận