題干：

Mario is world-famous plumber. His “burly” figure and amazing jumping ability reminded in our memory. Now the poor princess is in trouble again and Mario needs to save his lover. We regard the road to the boss’s castle as a line (the length is n), on every integer point i there is a brick on height hi. Now the question is how many bricks in [L, R] Mario can hit if the maximal height he can jump is H.

Input

The first line follows an integer T, the number of test data.?
For each test data:?
The first line contains two integers n, m (1 <= n <=10^5, 1 <= m <= 10^5), n is the length of the road, m is the number of queries.?
Next line contains n integers, the height of each brick, the range is [0, 1000000000].?
Next m lines, each line contains three integers L, R,H.( 0 <= L <= R < n 0 <= H <= 1000000000.)

Output

For each case, output "Case X: " (X is the case number starting from 1) followed by m lines, each line contains an integer. The ith integer is the number of bricks Mario can hit for the ith query.?

Sample Input

1 10 10 0 5 2 7 5 4 3 8 7 7 2 8 6 3 5 0 1 3 1 1 9 4 0 1 0 3 5 5 5 5 1 4 6 3 1 5 7 5 7 3

Sample Output

Case 1: 4 0 0 3 1 2 0 1 5 1

題目大意：

馬里奧是一個舉世聞名的管道工，他的跳躍能力讓我們欽佩。在一條長度為n的道路上，在每個整數點i的位置都有一個高度為hi的障礙物。現在的問題是：假設馬里奧可以跳躍的最高高度為H，在道路的[L,R]?區間內他可以跳躍過的障礙物有多少個（不要考慮他被擋住）？

Input

第一行是數據個數T。

對于每組數據：

第一行包含兩個整數n, m (1 <= n <=10^5, 1 <= m <= 10^5), n?表示道路的程度,?m是詢問的個數.

第二行包含n個整數，表示每個障礙物的高度,?高度范圍是?[0, 1000000000].?
接著?m?行，每行3個整數?L, R,H.( 0 <= L <= R < n 0 <= H <= 1000000000.)

Output

對于每組數據, 先輸出"Case X: " (?X表示組數)?然后有m行,?每行包含一個整數.?第i個整數表示第i個詢問的答案。

解題報告：

? 首先這題是可以離線做的（先對h排序優化掉一維，這樣就只剩下一維偏序了，直接樹狀數組就ok），極其方便。

但是為了練習這個神奇的數據結構emmm、、寫了一發主席樹。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 1e5 + 5; struct TREE {int l,r;int val; } tr[MAX*40];int tot; int a[MAX],b[MAX]; int root[MAX]; int build(int l,int r) {int cur = ++tot;tr[cur].val = 0;if(l == r) {tr[cur].l = tr[cur].r = 0;//這一步好像沒啥用？ return cur;}int m = (l+r)>>1;tr[cur].l = build(l,m);tr[cur].r = build(m+1,r);return cur; } void pushup(int cur) {tr[cur].val = tr[tr[cur].l].val + tr[tr[cur].r].val; } int update(int pre,int tar,int l,int r) {int cur = ++tot;tr[cur] = tr[pre];if(l == r) {tr[cur].val++;return cur;}int m = (l+r)>>1;if(tar <= m) tr[cur].l = update(tr[pre].l,tar,l,m);else tr[cur].r = update(tr[pre].r,tar,m+1,r);pushup(cur);return cur; } int query(int pl,int pr,int l,int r,int H) {if(l == r) return tr[pr].val - tr[pl].val;int m = (l+r)>>1;if(H <= m) return query(tr[pl].l,tr[pr].l,l,m,H);else return tr[tr[pr].l].val - tr[tr[pl].l].val + query(tr[pl].r,tr[pr].r,m+1,r,H); } int main() {int n,m;int t,iCase=0;cin>>t;while(t--) {printf("Case %d:\n",++iCase);cin>>n>>m;tot=0;for(int i = 1; i<=n; i++) scanf("%d",a+i),b[i] = a[i];root[0] = build(1,n);sort(b+1,b+n+1);int LEN = unique(b+1,b+n+1) - b - 1;for(int i = 1; i<=n; i++) {int pos = lower_bound(b+1,b+LEN+1,a[i]) - b;root[i] = update(root[i-1],pos,1,n);}while(m--) {int l,r,H;scanf("%d%d%d",&l,&r,&H);l++,r++;int pos = upper_bound(b+1,b+LEN+1,H) - b - 1;if(pos) printf("%d\n",query(root[l-1],root[r],1,n,pos));else printf("0\n");}} return 0 ; }

總結：

注意這里是因為可能在做前綴差的時候用到0（比如輸入的L=1，R=1的情況，則需要用到root[1]-root[0])，所以你需要先建一個空樹備用。這也是主席樹當區間差機制用的時候需要這樣用，但是一般的動態開點或許就不需要這樣？

所以你這里pos==0的情況一定要特判，不能因為建了一棵root==0的樹就可以不特判，因為可以這么理解：他那是線段樹開了一個0號版本，但是你這個pos是要映射到值域上的，也正因為是權值線段樹，所以必須要特判。也就是這倆=0不是一個東西。

第二個要注意的地方，那就是你build，update和query三個函數傳參的時候一定是用的同一個右端點，別一會用離散化之后的一會用離散化之前的。因為你對應的l和r區間長度都不同了，怎么同時二分往下找？

總結

以上是生活随笔為你收集整理的【HDU - 4417】Super Mario（查询区间小于K的数的个数，主席树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。