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

bonelee 阅读:81 2023-05-01 21:59:20 评论:0

题目描述

给定一个长度为 $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++ 代码


标签:程序员
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

关注我们

一个IT知识分享的公众号