Mực Nước Thấp Nhất

Buổi 28 — Segment Tree Lazy
Points
18
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Một dòng sông được chia thành N đoạn, đoạn i có mực nước a_i. Mưa hoặc xả đập làm mực nước của một dãy đoạn liên tiếp thay đổi cùng một lượng x. Với mỗi truy vấn, hãy cho biết mực nước thấp nhất trong khoảng được hỏi và có bao nhiêu đoạn đạt mực nước đó.

Dữ liệu vào

Dòng đầu chứa hai số nguyên N và Q. Dòng thứ hai chứa N số nguyên a_1..a_N. Q dòng tiếp theo, mỗi dòng là một thao tác:

  • 1 l r x: cộng x vào a_l..a_r.
  • 2 l r: truy vấn.
Dữ liệu ra

Với mỗi thao tác loại 2, in ra hai số: giá trị nhỏ nhất trong a_l..a_r và số vị trí đạt giá trị đó.

Ví dụ
Input Output
5 4\n2 1 9 7 -5\n1 2 4 -1\n2 3 3\n1 5 5 3\n1 4 5 4 8 1
Giới hạn
  • 1 ≤ N, Q ≤ 10^5
  • |a_i|, |x| ≤ 10^9
Draft saved