Mô tả
Trạm phát sóng 5G của Viettel tại quận Cầu Giấy liên tục ghi nhận chuỗi bit kiểm thử từ thiết bị đầu cuối. Một khung tin được xem là hợp lệ nếu giá trị bit tại vị trí đó là 1.
Kỹ sư truyền dẫn cần phân tích đoạn sóng [L, R] để kiểm tra vùng nhiễu. Cụ thể, với mỗi truy vấn từ hệ thống giám sát, bạn phải đếm xem trong đoạn chỉ số từ L đến R (bao gồm cả hai đầu) có tổng cộng bao nhiêu khung tin hợp lệ.
Vì số lượng truy vấn có thể lên đến hàng vạn, việc duyệt tuyến tính từng bit cho mỗi truy vấn là không khả thi. Hãy giúp kỹ sư xây dựng một phương pháp trả lời nhanh chóng!
Đầu vào
Dòng đầu tiên chứa số nguyên n (số lượng bit của chuỗi kiểm thử) và q (số lượng truy vấn).
Dòng thứ hai chứa n số nguyên, mỗi số là 0 hoặc 1, biểu diễn chuỗi bit.
q dòng tiếp theo, mỗi dòng chứa hai số nguyên L và R (chỉ số của đoạn cần kiểm tra).
Đầu ra
Với mỗi truy vấn, in ra một số nguyên trên một dòng tương ứng: tổng số bit 1 trong đoạn [L, R].
Ràng buộc
- 1 ≤ n ≤ 10^5
- 1 ≤ q ≤ 10^5
- 0 ≤ L ≤ R < n
Ví dụ
Đầu vào:
6 3 1 1 0 1 0 1 0 2 1 4 0 5
Đầu ra:
2 2 4
Giải thích:
- Truy vấn
0 2: Xét đoạn[1, 1, 0]. Có 2 bit1. In ra2. - Truy vấn
1 4: Xét đoạn[1, 0, 1, 0]. Có 2 bit1. In ra2. - Truy vấn
0 5: Xét toàn bộ mảng[1, 1, 0, 1, 0, 1]. Có 4 bit . In ra .