题目链接：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: ",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 ",query(T[L-1],T[R],H,1,cnt)); 64 } 65 } 66 return 0; 67 }