Dải Đất Liền Mạch

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

Bản đồ một vùng đất là dãy N ô, mỗi ô là đất (1) hoặc nước (0). Có thể lấp hoặc đào cả một đoạn ô liên tiếp để mọi ô trong đoạn đều thành đất hoặc đều thành nước. Với mỗi câu hỏi, hãy tìm dải đất liền mạch dài nhất trong một đoạn được hỏ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 v: gán a_i = v (v ∈ {0, 1}) với mọ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 (0 nếu không có số 1).

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