Tòa Tháp Đầu Tiên

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

Có N tòa tháp xếp thành hàng, tháp thứ i cao a_i. Một người đứng trước tháp l muốn đi sang phải và dừng lại ở tòa tháp đầu tiên (từ l trở đi) có chiều cao không nhỏ hơn x. Chiều cao tháp có thể thay đổi.

Dữ liệu vào

Dòng đầu chứa N và Q. Dòng thứ hai chứa N số a_1..a_N. Q dòng tiếp theo:

  • 1 i v: đặt a_i = v.
  • 2 l x: truy vấn.
Dữ liệu ra

Với mỗi truy vấn loại 2, in ra chỉ số nhỏ nhất j ≥ l sao cho a_j ≥ x, hoặc -1 nếu không tồn tại.

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