【模板】整数域二分【牛客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规模的数据与查询。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N2e510;constll INF1e18;constll M1e610;ll a[N];intmain(){ll n,q;cinnq;for(ll i1;in;i)cina[i];sort(a1,a1n);for(ll i1,l,r;iq;i){cinlr;ll Llower_bound(a1,a1n,l)-a;ll Rupper_bound(a1,a1n,r)-a-1;coutR-L1endl;}return0;}