Lật Đoạn Chuỗi Dài Nhất

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

Cho xâu nhị phân độ dài N. Thao tác lật (0 thành 1, 1 thành 0) mọi ký tự trong một đoạn, và truy vấn độ dài dãy 1 liên tiếp dài nhất trong một đoạn. Lưu ý rằng sau khi lật, dãy 0 dài nhất cũng trở thành dãy 1 dài nhất, nên mỗi nút cần lưu thông tin cho cả hai loại.

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ố 0/1 a_1..a_N. Q dòng tiếp theo, mỗi dòng là một thao tác:

  • 1 l r: lật mọi a_i với i ∈ [l, r].
  • 2 l r: hỏi độ dài dãy 1 liên tiếp dài nhất trong a_l..a_r.
Dữ liệu ra

Với mỗi thao tác loại 2, in ra độ dài tìm được.

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