in this problem you are given a
number sequence p consisting of n integer and pi is the ith element in
the sequence. now you task is to answer a list of queries, for each query,
please tell us among [l, r], how many pi is not less than a and not greater
than b( l<= i <= r). in other words, your task is to count the number of
pi (l <= i <= r, a <= pi <= b).
in the first line there is
an integer t (1 < t <= 50), indicates the number of test
cases.
for each case, the first line contains two
numbers n and m (1 <= n, m <= 50000), the size of sequence p, the number
of queries. the second line contains n numbers pi(1 <= pi <= 10^9),
the number sequence p. then there are m lines, each line contains four number l,
r, a, b(1 <= l, r <= n, 1 <= a, b <= 10^9)
for each case, at first output a
line ‘case #c:’, c is the case number start from 1. then for each query output a
line contains the answer.
2013年山东省第四届acm大学生程序设计竞赛
划分树 +
二分（据说归并树也可以做）。
题意：给你t组测试数据，每一组测试数据开始有两个整数n和m。分别表示下一行要输入n个整数，后面接着有m行询问，每行询问有4个整数
l,r,a,b，表示在区间 [l,r] 中查找 a<=pi<=b 的数有多少个，输出数的个数。
思路：
这道题最直接的思路是对要求的区间排一下序，然后依次判断比较，记录下在范围[a,b]之内的数有多少个，即为结果。但是m即询问的次数范围在[1,50000]，如果每询问一次都要排一次序的话，时间消耗过大，所以上来直接pass掉这种思路。
因为这道题是基于区间查询，所以接下来我很自然的就想到了“”。线段树的每一个节点代表一个区间，节点中存储的值为区间的特定值，在这里我用节点区间中的最大值，最小值，即数值范围，来表示这个特定值。查询的时候，先找到要找的区间，然后递归下去寻找这个区间内的值有多少个是在数值范围内。如果找到这个区间，发现这个区间的最小值都比[a,b]中的上限b要大，或者最大值都比下限a要小。说明这个区间内没有一个是符合要求的，这个节点代表的整个子树就不用找了。如此，会节约不少时间。
但是线段树的方法也会超时，比赛的时候看到tle可是苦思冥想了好久，想了各种优化的方法。无奈，还是没能用线段树解出这道题。
后来比赛结束后查题解，才知道原来还有"划分树"这种神奇的东西。划分树是基于线段树的，但是我感觉它只继承了线段树“基于区间”的特点，其他的感觉我觉得倒没有什么联系。划分树主要是用来解决“区间第k大的数”问题。下面就让我具体的来讲讲如何用划分树解决这道题。
大家需要先大体了解一下什么是“”，它的作用是“快速求出某一区间内第k大的元素”，例如数列“1,2,3,4,5,6,7,8"，区间[3,6]内第1大的值就是3。
那么如何用这个特性求出某一区间内数值在[a,b]范围内的数有多少个呢？
举个例子：数列“1,5,6,3,8,4,4,2”，l,r,a,b分别为3,6,4,7，即在区间[3,6]范围内查找数值在[4,7]的数有多少个。很显然，这里要查找的区间就是"6,3,8,4"，4<=pi<=7的数有2个。
用划分树的思路来解决这个问题。先求出这个区间范围内第1大的数是多少，这里是3,拿它和下限 4(a)
来比较，比这个数小，说明不在这个数值范围内。然后求出第2大的数是4,和下限4(a)比较，在这个范围内，记录下它是第几大的数，标记为down，代表
>= 下限a的第一个数是第几大的数，这里为2（第二大的数）。同理，再依次和上限7(b)比较，求出第一个
<= 上限b的数是第几大的数，标记为up，代表 <=
上限b的数是第几大的数，这里为3。这之间包含了多少个数即为要求得的结果，即（up-down+1） 。
刚才的思路利用划分树顺序查找锁定up和down的值，这样未免会太慢。这道题对速度的要求还是比较高的，所以这里就要用到“"的思想。什么是二分呢？举个例子，如果查询区间为[1,8]，要求数值范围为[3,6]的数有多少个，先求down。可以先用中间那个数来和下限3比较，即用第4大的数和下限比较，如果比下限小，说明个要找的数在第4大的数右边，下一步再用4和8的中间值，即第6大的数和下限比较，最后得到down的值。同理可以求出up的值。这样一来，速度上又进行了一次优化。
参考资料：
代码（带注释）：
freecode :