Tòa Nhà Nhìn Thấy
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề 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
Community Discussion