Description 我有很多（n条）珍珠项链，每天我都要从中挑一条戴上……挑哪条很有讲究，不能太难看也不能太好看。所以我希望你能帮帮我，解决这个问题――每天帮我算算，那天我能戴的项链有多少条。 Input 第1行为正整数n，表示项链的总条数(n≤100000)； 第2行有n个整数（代表每条项链晶的好看程度Xi，0≤Xi≤maxlongint）； 第3行为正整数m，表示总天数(也就是总询问次数，其中m≤100000)； 以下m行，每行两个整数Ai，Bi(1≤Ai，Bi≤maxlongint)，询问好看程度在Ai到Bi之间的项链条数（含等于Ai或Bi的，Ai与Bi大小关系不确定）。 Output 输出m行，对于每次询问输出一行，从Ai到Bi(含Ai，Bi)好看程度在Ai到Bi之间的项链条数。，要求C++实现，且使用scanf函数

Solution

题目要求求出好看程度在 $[A_i, B_i]$ 之间的项链条数，因此我们可以首先对所有的项链按照好看程度进行排序。然后对于每个询问 $[A_i, B_i]$，我们可以通过二分查找在排好序的项链中找到第一个好看程度大于等于 $A_i$ 的项链和第一个好看程度大于 $B_i$ 的项链，它们之间的项链就是我们需要的。具体实现可以参考下面的代码。

Code