Cộng đoạn và tìm giá trị nhỏ nhất

Buổi 27 — Segment Tree cơ bản
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho mảng $A$ gồm $n$ số nguyên và $q$ truy vấn thuộc một trong hai loại:

  • 1 l r v: Cộng thêm $v$ vào tất cả các phần tử $A[i]$ với $l \le i \le r$.
  • 2 l r: Tìm giá trị nhỏ nhất trong đoạn $A[l..r]$.
Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $n, q$.
  • Dòng thứ hai chứa $n$ số nguyên $A[1], A[2], \dots, A[n]$.
  • $q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn.
Dữ liệu ra

Với mỗi truy vấn loại 2, in ra giá trị nhỏ nhất tìm được trên một dòng.

Ví dụ
Input Output
5 4
5 2 8 1 4
2 1 5
1 3 5 4
2 3 5
2 1 2
1
5
2
Giới hạn
  • $1 \le n, q \le 10^5$
  • $|A[i]|, |v| \le 10^9$
  • $1 \le l \le r \le n$
Draft saved