题目大意为给定一个长度为n的区间，同时给出m个询问，每次询问在区间[l,r]中有多少个数小于或等于k。
同样考虑用主席树来维护，每次只需要找到序列b中第一个等于k的数，那么要求的数必定在b[1]~b[upper_bound(k)]这个范围内，接下来就像线段树统计区间个数那样，若完全包含则直接加上e[rr].sum-e[ll].sum,否则就分两边递归统计。而建树什么的就直接套模板即可。
还要注意一点，原题的区间默认从0开始，因此若像我一样写了区间从1开始的记得在query之前将l和r加上1。
最最最最后一点，hdu的老规矩，要注意处理好多组数据。
代码：
#include<cstdio> #include<cstring> #include<algorithm> const int N=1e5+5; using namespace std; struct point{ int rt,sum,ls,rs; }e[N*20]; int a[N],b[N],tot,n,m,sz,x,y; void build(int &rt,int le,int ri) { tot++;rt=tot; e[rt].sum=0; if(le==ri)return ; int mid=(le+ri)>>1; build(e[rt].ls,le,mid); build(e[rt].rs,mid+1,ri); } void up(int &rt,int l,int r,int last,int p) { rt=++tot; e[rt].ls=e[last].ls;e[rt].rs=e[last].rs; e[rt].sum=e[last].sum+1; if(l==r)return; int mid=(l+r)>>1; if(p<=mid)up(e[rt].ls,l,mid,e[last].ls,p); else up(e[rt].rs,mid+1,r,e[last].rs,p); } int query(int ll,int rr,int l,int r) { if(x>y)return 0; if(x<=l&&y>=r)return e[rr].sum-e[ll].sum; int mid=(l+r)>>1; int ret=0; if(x<=mid)ret+=query(e[ll].ls,e[rr].ls,l,mid); if(y>mid)ret+=query(e[ll].rs,e[rr].rs,mid+1,r); return ret; } void find() { int ll,rr,kk; scanf("%d %d %d",&ll,&rr,&kk); ll++;rr++; x=1;y=upper_bound(b+1,b+1+sz,kk)-(b+1); int an=query(e[ll-1].rt,e[rr].rt,1,sz); printf("%d ",an); } int main() { int T,ss=1; scanf("%d",&T); while(T--) { tot=0; scanf("%d %d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+n+1); sz=unique(b+1,b+n+1)-(b+1); build(e[0].rt,1,sz); for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+sz,a[i])-b; for(int i=1;i<=n;i++)up(e[i].rt,1,sz,e[i-1].rt,a[i]); printf("Case %d: ",ss);ss++; while(m--)find(); } return 0; }