Chuỗi Ngày Nắng Dài

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

Một nông dân ghi lại thời tiết N ngày: 1 là ngày nắng, 0 là ngày mưa. Dự báo có thể thay đổi: một ngày bị đảo trạng thái. Với mỗi câu hỏi [l, r], hãy cho biết chuỗi ngày nắng liên tiếp dài nhất trong khoảng đó.

Dữ liệu vào

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

  • 1 i: đảo giá trị a_i.
  • 2 l r: truy vấn.
Dữ liệu ra

Với mỗi truy vấn loại 2, in ra độ dài lớn nhất của dãy các số 1 liên tiếp trong a_l..a_r.

Ví dụ
Input Output
5 4\n1 1 1 1 0\n1 5\n2 3 5\n2 2 5\n2 4 4 3\n4\n1
Giới hạn
  • 1 ≤ N, Q ≤ 10^5
Draft saved