![]()
思路
![]()
求解代码
publicstaticvoidmain(String[]args)throwsIOException{// 使用BufferedReader读取输入，PrintWriter输出结果BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));PrintWriterout=newPrintWriter(newOutputStreamWriter(System.out));// 读取第一行输入，分割成字符串数组String[]strA=br.readLine().trim().split("\\s+");// 解析数组长度n和查询次数qintn=Integer.parseInt(strA[0]);intq=Integer.parseInt(strA[1]);// 创建数组a并读取输入数据int[]a=newint[n];String[]strB=br.readLine().trim().split("\\s+");for(inti=0;i<n;i++){a[i]=Integer.parseInt(strB[i]);}// 对数组进行排序，为后续查询做准备Arrays.sort(a);// 处理q次查询while(q-->0){// 读取每次查询的左右边界String[]strC=br.readLine().trim().split("\\s+");intl=Integer.parseInt(strC[0]);intr=Integer.parseInt(strC[1]);// 使用二分查找计算下界和上界intleft=lowerBound(a,l);intright=upperBound(a,r);// 输出结果：范围内的元素个数out.println(right-left);}// 关闭IO资源out.flush();out.close();br.close();}/** * 二分查找下界函数 * * @param a 已排序的数组 * @param target 目标值 * @return 第一个大于等于target的元素的索引 */privatestaticintlowerBound(int[]a,inttarget){// 初始化查找范围的 low 和 high 指针// low 从数组的起始位置 0 开始// high 从数组长度开始（不包括该位置）intlow=0,high=a.length;// 当 low 小于 high 时，继续查找// 这是循环查找的条件，确保查找范围有效while(low<high){// 计算中间位置 mid// 使用位运算 (high-low)>>1 代替除法 2，提高效率// 防止整数溢出，同时确保 mid 总是在 low 和 high 之间intmid=low+((high-low)>>1);// 如果中间位置的元素大于等于目标值// 说明目标值可能在左半部分，或者 mid 就是我们要找的位置// 因此将 high 设置为 mid，继续在左半部分查找if(a[mid]>=target){high=mid;}else{// 如果中间位置的元素小于目标值// 说明目标值一定在右半部分// 因此将 low 设置为 mid+1，继续在右半部分查找low=mid+1;}}// 当循环结束时，low 指向第一个大于等于 target 的元素的位置// 如果所有元素都小于 target，则返回数组长度returnlow;}/** * 二分查找上界函数 * * @param a 已排序的数组 * @param target 目标值 * @return 第一个大于target的元素的索引 */privatestaticintupperBound(int[]a,inttarget){// 初始化查找范围的左右边界，左边界为0，右边界为数组长度intlow=0,high=a.length;// 当左边界小于右边界时，继续查找while(low<high){// 计算中间位置，使用位运算防止溢出intmid=low+((high-low)>>1);// 如果中间位置的值大于目标值，则上界在左半部分if(a[mid]>target){high=mid;}else{// 否则上界在右半部分，且不包括中间位置low=mid+1;}}// 返回第一个大于target的元素的索引returnlow;}
