Công Tắc Đảo Chiều

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

Một dãy N công tắc, mỗi công tắc đang bật (1) hoặc tắt (0). Một thao tác đảo trạng thái tất cả công tắc trong một đoạn liên tiếp. Hãy đếm số công tắc đang bật trong các đ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: đảo (0↔1) mọi a_i với i ∈ [l, r].
  • 2 l r: hỏi số lượng số 1 trong a_l..a_r.
Dữ liệu ra

Với mỗi thao tác loại 2, in ra số lượng số 1 trong đoạn.

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