整数域二分
整数域二分
描述
对于给定的长度为
n
n 的数组 ，你需要实现:
区间元素个数查询：输出数组中大于等于 l且小于等于r 的元素个数；
你一共需要处理q 次操作。
输入描述：
第一行输入两个整数 n,q(1≦n,q≦2×10^5 ) 代表数组中的元素数量、操作次数。
第二行输入 n 个整数代表初始数组。
此后 q 行，每行输入两个整数 代表区间的边界。
输出描述：
对于每一次查询操作，在一行上输出一个整数代表区间中的元素个数。
示例1
输入：
7 3
-7 -1 3 6 2 -4 9
0 3
-1 4
-10 10
复制
输出：
2
3
7
实现代码（Python）:
importsysimportbisectdefmain():lines=sys.stdin.read().splitlines()idx=0n,q=map(int,lines[idx].split())idx+=1#print(n,q)nums=list(map(int,lines[idx].split()))idx+=1#print(nums)nums.sort()#print(nums)for_inrange(q):l,r=map(int,lines[idx].split())idx+=1#print(l,r)l_seq=bisect.bisect_left(nums,l)r_seq=bisect.bisect_right(nums,r)count=r_seq-l_seqprint(count)if__name__=="__main__":main()分析
本题使用库函数bisect可快速解决以下是整理后的Markdown表格格式内容：
函数与使用场景对照表
| 函数 | 作用 | 返回值 | 机试使用场景 |
|---|---|---|---|
bisect.bisect_left(a, x) | 找第一个 ≥ x 的元素的下标（左边界） | 整数下标 | 查区间[l, r]的左边界（≥l） |
bisect.bisect_right(a, x) | 找第一个 > x 的元素的下标（右边界） | 整数下标 | 查区间[l, r]的右边界（>r） |
bisect.bisect(a, x) | 等价于bisect_right(a, x) | 整数下标 | 简化写法，和bisect_right通用 |
bisect.insort_left(a, x) | 将 x 插入数组 a 并保持升序 | 无（直接修改数组） | 需要插入元素并保持有序时使用 |
排序 + 二分查找是处理「区间元素计数」的最优解