Count Negatives in a Range

Difficulty: 1100 3000 ms 128 MB

prefix-sums

Answer Q independent queries on a fixed array: each query gives L and R (1-based, inclusive) and asks for the number of strictly negative values of a_L..R.

Input: the first line has N and Q; the second line has N integers; each of the next Q lines has L and R.

Output: Q lines — the answer per query.

Constraints:

• 1 ≤ N, Q ≤ 10⁴
• −10⁹ ≤ a_i ≤ 10⁹

Sample Tests

5 2
1 -2 3 -4 5
1 3
2 5

1
2

1 1
7
1 1

0

Read the Editorial