Tòa Nhà Nhìn Thấy

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

N tòa nhà xếp thành hàng từ trái sang phải, tòa thứ i cao a_i. Một tòa nhà được gọi là 'nhìn thấy được' nếu nó cao hơn hẳn mọi tòa nhà đứng bên trái nó (tòa đầu tiên luôn nhìn thấy được). Có Q lần thay đổi chiều cao; sau mỗi lần, hãy cho biết số tòa nhà nhìn thấy được.

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, mỗi dòng chứa i và v: đặt a_i = v.

Dữ liệu ra

Sau mỗi thay đổi, in ra số lượng chỉ số i sao cho a_i > max(a_1..a_{i-1}) (với i = 1 luôn thỏa).

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