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 :