Searching_3

Description

They declared Sonam as bewafa. Although she is not, believe me! She asked a number of queries to people regrading their position in a test. Now its your duty to remove her bewafa tag by answering simple queries. All the students who give test can score from 1 to 10^18. Lower the marks, better the rank. Now instead of directly telling the marks of student they have been assigned groups where marks are distributed in continuous intervals, you have been given l(i) lowest mark of interval i and r(i) highest marks in interval i. So marks distribution in that interval is given as l(i), l(i)+1, l(i)+2 . . . r(i)

Now Sonam ask queries in which she gives rank of the student (x) and you have to tell marks obtained by that student

Note: rank1 is better than rank2 and rank2 is better than rank3 and so on and the first interval starts from 1.

Constraints:1<=T<=50,1<=N<=10^5,1<=Q<=105,1<= l(i) < r(i) <=10^18,1<=x<=1018

（这道题真是，理解题目讲啥半小时，解题5分钟）

意思就是，给你一个个区间，表示已有的数，然后查询，找出第q大的数

比如这个例子，给了3个区间[1,10], [12, 20], [22, 30]，表示存在的数，区间外（除了 > 30）的数是不存在的。

1 10 12 20 22 30

查询第5个数，第15个数，第25个数

5 15 25

第5个数是5，由于11不存在，所以第15个数是16，由于11和13不存在，所以第25个数是27

理解了题目就很容易想到一个暴力的解法，对每一个查询，遍历区间，计算已有的数的个数，当到达查询个数时返回结果。

暴力解法使用二叉搜索后，可以优化为O(logn)的解法。

1. 计算每个区间之前有多少个数，放在counts中
2. 对于查询q，在counts中二叉搜索最后一个比q小的数，得到该数的坐标idx
3. 得到第q个数就是：intervals[idx][0] + q - counts[idx] intervals表示所有的区间

python

import bisect
def solve(intervals, query):
    intervals.sort()
    counts = [1]
    for i in range(1, len(intervals)):
        counts.append(counts[-1] + intervals[i-1][1] - intervals[i-1][0] + 1)
    ans = []
    for q in query:
        idx = bisect.bisect(counts, q) - 1
        ans.append(intervals[idx][0] + q - counts[idx])
    return ans