Chiếc Bể Đầy Đầu Tiên

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

Có N bể chứa xếp thành hàng, bể i đang chứa a_i lít nước. Người ta đổ thêm x lít vào mọi bể trong một đoạn (x có thể âm nếu rút bớt). Với mỗi câu hỏi, cho ngưỡng v, hãy tìm bể đầu tiên từ trái sang có lượng nước ít nhất v lít.

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 v: hỏi chỉ số nhỏ nhất i sao cho a_i ≥ v.
Dữ liệu ra

Với mỗi thao tác loại 2, in ra chỉ số i nhỏ nhất thỏa mãn, hoặc -1 nếu không tồn tại.

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