Count Single-Digit Values

Difficulty: 1300 5000 ms 128 MB

prefix-sums

Answer Q range queries: how many elements of a_l..r have absolute value below 10?

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
1 4 9 16 25
1 3
2 5

3
2

1 1
7
1 1

1

Read the Editorial