【模板】整数域二分【牛客tracker 每日一题】
【模板】整数域二分
时间限制：3秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
对于给定的长度为n nn的数组{ a 1 , a 2 , … , a n } \{a_1,a_2,…,a_n\}{a1,a2,…,an}，你需要实现：
- 区间元素个数查询：输出数组中大于等于l ll且小于等于r rr的元素个数；
你一共需要处理q qq次操作。
输入描述：
第一行输入两个整数n , q ( 1 ≦ n , q ≦ 2 × 10 5 ) n,q(1≦n,q≦2×10^5)n,q(1≦n,q≦2×105)代表数组中的元素数量、操作次数。
第二行输入n nn个整数a 1 , a 2 , … , a n ( − 10 9 ≦ a i ≦ 10 9 ) a_1,a_2,…,a_n(−10^9≦a_i≦10^9)a1,a2,…,an(−109≦ai≦109)代表初始数组。
此后q qq行，每行输入两个整数l , r ( − 10 9 ≦ l , r ≦ 10 9 ) l,r(−10^9≦l,r≦10^9)l,r(−109≦l,r≦109)代表区间的边界。
输出描述：
对于每一次查询操作，在一行上输出一个整数代表区间中的元素个数。
示例1
输入：
7 3 -7 -1 3 6 2 -4 9 0 3 -1 4 -10 10输出：
2 3 7解题思路
本题核心是排序预处理+二分查找，高效解决大规模数组的区间计数查询问题。由于需要处理高达2 × 10 5 2\times10^52×105次的区间查询，暴力遍历会超时，因此先将数组进行升序排序，利用有序数组的特性优化查询。对于每次查询[ l , r ] [l,r][l,r]，使用lower_bound找到数组中第一个大于等于l ll的元素下标，使用upper_bound找到第一个大于r rr的元素下标，两个下标做差即可得到区间内的元素个数。算法预处理复杂度为O ( n log n ) O(n\log n)O(nlogn)，单次查询复杂度为O ( log n ) O(\log n)O(logn)，完美适配题目大数据规模约束。
总结
核心逻辑：将无序数组排序，通过二分查找快速定位区间边界，计算元素数量。
关键操作：数组排序、lower_bound/upper_bound二分定位、下标差值计算。
效率保障：对数级的查询效率，轻松处理2 × 10 5 2\times10^52×105规模的数据与查询。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=2e5+10;constll INF=1e18;constll M=1e6+10;ll a[N];intmain(){ll n,q;cin>>n>>q;for(ll i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);for(ll i=1,l,r;i<=q;i++){cin>>l>>r;ll L=lower_bound(a+1,a+1+n,l)-a;ll R=upper_bound(a+1,a+1+n,r)-a-1;cout<<R-L+1<<endl;}return0;}