Count Positives in Range

Difficulty: 1300 5000 ms 128 MB

prefix-sums

Answer Q range queries: how many elements of a_l..r are strictly positive?

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

2
2

1 1
7
1 1

1

Read the Editorial