题解 | 【模板】整数域二分

import sys
input=sys.stdin.readline

def solve():
    n,q=map(int,input().split())
    nums=list(map(int,input().split()))
    nums.sort()
    ans=[]

    def query_right(tar):#计算坐标(包含)
        l,r=0,n
        while l<r:
            mid=(l+r)>>1
            if nums[mid]>tar:
                r=mid
            else:
                l=mid+1
        return l-1
    for _ in range(q):
        l,r=map(int,input().split())
        ans.append(query_right(r)-query_right(l-1))
    print("\n".join(map(str,ans)))
solve()

既然是模板题，那么实现一下手写二分

统计[l,r]的数量，二分查找需要数组单调性，所以先对数组排序

可以拆成左区间[-inf,l-1]与右区间[-inf,r]

query_right函数实现的是左闭右开的下标查找，找到第一个严格大于target的下标并减一即返回target最右面数字的下标

右区间-左区间即为答案