【ybt金牌导航6-3-2】区间计数（分块）（二分）

题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，有 $q$ 次询问，每次询问给定两个整数 $l,r$，求区间 $[l,r]$ 中有多少个数 $x$ 满足 $x^2\leq a_x$。

输入格式

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

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

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

输出格式

对于每个询问，输出区间 $[l,r]$ 中满足条件的数的个数。

数据范围

$1\leq n,q\leq 10^5$,

$1\leq a_i\leq 10^9$,

$1\leq l\leq r\leq n$

输入样例

5 3

1 2 3 4 5

1 5

2 4

3 5

输出样例

2

1

2

算法1

(分块) $O(n\sqrt n+q\sqrt n\log n)$

我们可以对 $a_i$ 进行分块，每块长度为 $\sqrt n$，对于每个询问 $[l,r]$，我们可以分别处理 $l$ 所在块和 $r$ 所在块以及中间的若干个完整块，对于每个块，我们可以使用二分查找来求出满足条件的数的个数，最后将所有块的答案加起来即可。

时间复杂度

总共有 $\sqrt n$ 个块，每个块内部二分查找的时间复杂度为 $\log n$，因此总时间复杂度为 $O(n\sqrt n+q\sqrt n\log n)$。

C++ 代码

算法2

(二分) $O(n\log^2 n+q\log^2 n)$

我们可以对 $a_i$ 进行排序，对于每个询问 $[l,r]$，我们可以在排序后的数组中二分查找满足条件的数的个数。

时间复杂度

排序的时间复杂度为 $O(n\log n)$，每个询问的时间复杂度为 $O(\log n)$，因此总时间复杂度为 $O(n\log^2 n+q\log^2 n)$。

C++ 代码