Đảo bit trên đoạn nhị phân
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề bài
Cho xâu nhị phân $S$ độ dài $n$ (đánh số từ $1$ đến $n$) và $q$ truy vấn:
1 l r: Đảo tất cả các bit trong đoạn $[l, r]$ (0thành1,1thành0).2 l r: Đếm số lượng ký tự'1'trong đoạn $[l, r]$.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $n, q$.
- Dòng thứ hai chứa xâu nhị phân $S$ độ dài $n$.
- $q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn.
Dữ liệu ra
Với mỗi truy vấn loại 2, in ra số lượng ký tự '1' trên một dòng.
Ví dụ
| Input | Output |
|---|---|
| 6 4 101001 2 1 6 1 2 5 2 1 6 2 2 4 |
3 5 2 |
Giới hạn
- $1 \le n, q \le 10^5$
- $1 \le l \le r \le n$
Community Discussion