【ybt金牌导航6-3-3】【luogu P4135】偶数个数 / 作诗（分块）

题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，有 $m$ 个询问，每个询问给定两个整数 $l,r$，求 $a_l,a_{l+1},\cdots,a_r$ 中偶数的个数。

输入格式

第一行包含两个整数 $n,m$。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

接下来 $m$ 行，每行包含两个整数 $l,r$，表示一个询问。

输出格式

对于每个询问，输出 $a_l,a_{l+1},\cdots,a_r$ 中偶数的个数。

数据范围

$1\leq n,m\leq 10^5$，$1\leq a_i\leq 10^9$。

输入样例1：

5 3

1 2 3 4 5

1 5

2 4

3 3

输出样例1：

2

1

0

输入样例2：

10 5

1 2 3 4 5 6 7 8 9 10

1 10

2 9

3 8

4 7

5 6

输出样例2：

5

4

3

2

1

算法1

(分块) $O(\sqrt{n}m)$

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(暴力枚举) $O(nm)$

blablabla

时间复杂度

参考文献

C++ 代码