题目链接：https://vjudge.net/problem/HDU-4417
题目大意：
给出\(n\)个数，进行\(m\)次查询，每次询问在\([L,R]\)这个区间中小于或等于\(H\)的数有多少个。
知识点： 可持久化线段树
解题思路：
模板题。先建一棵空的权值线段树，线段树的第\(x\)枚叶子保存的是第\(x\)大的数的个数，然后再依次将\(n\)个数更新进去。查询时其实就是查第\(R\)个版本的树去掉第\(L-1\)个版本的树所得到的树中小于或等于\(H\)的数的个数。
AC代码：
1 #include <bits/stdc++.h>
2
3 using namespace std;
4 const int maxn = 1e5+3;
5 int lson[20*maxn],rson[20*maxn];
6 int sum[20*maxn];
7 int T[maxn];
8 int tot=0;
9 int num[maxn],san[maxn];
10
11 void build(int l,int r,int &rt){
12 rt=++tot;
13 sum[rt]=0;
14 if(l==r) return;
15 int m=(l+r)>>1;
16 build(l,m,lson[rt]); build(m+1,r,rson[rt]);
17 }
18 void update(int last,int pos,int l,int r,int &rt){
19 rt=++tot;
20 lson[rt]=lson[last]; rson[rt]=rson[last];
21 sum[rt]=sum[last]+1;
22 if(l==r) return;
23 int m=(l+r)>>1;
24 if(pos<=m) update(lson[last],pos,l,m,lson[rt]);
25 else update(rson[last],pos,m+1,r,rson[rt]);
26 }
27 int query(int L,int R,int H,int l,int r){
28 if(san[r]<=H) return sum[R]-sum[L]; //如果最右边的叶子所对应的数都小于或等于H的话
29 if(san[l]>H) return 0; //如果最左边的叶子所对应的数都大于H
30 int m=(l+r)>>1;
31 int ret=0;
32 if(san[m]<=H){
33 ret+=(sum[lson[R]]-sum[lson[L]]);
34 ret+=query(rson[L],rson[R],H,m+1,r);
35 }
36 else
37 ret+=query(lson[L],lson[R],H,l,m);
38 return ret;
39 }
40 int main(){
41 // freopen("in.txt","r",stdin);
42 int Ts,n,m;
43 scanf("%d",&Ts);
44 for(int t=1;t<=Ts;t++){
45 printf("Case %d:\n",t);
46 scanf("%d%d",&n,&m);
47 for(int i=1;i<=n;i++){
48 scanf("%d",&num[i]);
49 san[i]=num[i];
50 }
51 sort(san+1,san+1+n);
52 int cnt=unique(san+1,san+1+n)-san-1;
53 build(1,cnt,T[0]);
54 for(int i=1;i<=n;i++)
55 num[i]=lower_bound(san+1,san+1+cnt,num[i])-san;
56 for(int i=1;i<=n;i++)
57 update(T[i-1],num[i],1,cnt,T[i]);
58
59 int L,R,H;
60 while(m--){
61 scanf("%d%d%d",&L,&R,&H);
62 L++,R++; //题中的下标是从0开始的
63 printf("%d\n",query(T[L-1],T[R],H,1,cnt));
64 }
65 }
66 return 0;
67 }