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<=105,1<=Q<=105,1<= l(i) < r(i) <=1018,1<=x<=1018
（這道題真是，理解題目講啥半小時(shí)啡省，解題5分鐘）
意思就是咆繁，給你一個(gè)個(gè)區(qū)間驯杜，表示已有的數(shù)袍冷，然后查詢袖迎，找出第q大的數(shù)
比如這個(gè)例子季眷，給了3個(gè)區(qū)間[1,10], [12, 20], [22, 30]余蟹，表示存在的數(shù)，區(qū)間外（除了 > 30）的數(shù)是不存在的子刮。
1 10 12 20 22 30
查詢第5個(gè)數(shù)客叉，第15個(gè)數(shù)，第25個(gè)數(shù)
5 15 25
第5個(gè)數(shù)是5话告，由于11不存在兼搏，所以第15個(gè)數(shù)是16，由于11和13不存在沙郭，所以第25個(gè)數(shù)是27
理解了題目就很容易想到一個(gè)暴力的解法佛呻，對(duì)每一個(gè)查詢，遍歷區(qū)間病线，計(jì)算已有的數(shù)的個(gè)數(shù)吓著，當(dāng)?shù)竭_(dá)查詢個(gè)數(shù)時(shí)返回結(jié)果鲤嫡。
暴力解法使用二叉搜索后，可以優(yōu)化為O(logn)的解法绑莺。
- 計(jì)算每個(gè)區(qū)間之前有多少個(gè)數(shù)暖眼，放在
counts中 - 對(duì)于查詢q，在counts中二叉搜索最后一個(gè)比q小的數(shù)纺裁，得到該數(shù)的坐標(biāo)idx
- 得到第q個(gè)數(shù)就是：
intervals[idx][0] + q - counts[idx]intervals表示所有的區(qū)間
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
