Count Even-Digit-Sum in Range

Difficulty: 1300 5000 ms 128 MB

prefix-sums

Answer Q range queries: how many elements of a_l..r have an even digit sum?

Input: the first line has N and Q; the second line has the array; each of the next Q lines has l and r.

Output: one line per query.

Constraints:

• 1 ≤ N, Q ≤ 10⁵
• |values| ≤ 10⁹

Sample Tests

5 2
2 3 4 9 16
1 3
2 5

2
1

1 1
7
1 1

0

Read the Editorial