Đoạn Con Chia Hết Cho 3
Points
60
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Cho dãy N số nguyên không âm. Với mỗi truy vấn [l, r], hãy đếm số đoạn con liên tiếp [x, y] với l ≤ x ≤ y ≤ r có tổng các phần tử chia hết cho 3. Giá trị các phần tử có thể thay đổi giữa các truy vấn.
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ố nguyên a_1..a_N. Q dòng tiếp theo, mỗi dòng là một trong hai dạng:
1 i x: gán a_i = x.2 l r: truy vấn trên đoạn [l, r].
Dữ liệu ra
Với mỗi truy vấn loại 2, in ra số đoạn con [x, y] ⊆ [l, r] có a_x + ... + a_y chia hết cho 3.
Ví dụ
| Input | Output |
|---|---|
| 5 4\n2 8 1 1 3\n1 5 8\n1 3 1\n2 1 5\n1 4 1 | 4 |
Giới hạn
- 1 ≤ N, Q ≤ 10^5
- 0 ≤ a_i, x ≤ 10^9
Community Discussion