题意:
给你n个数，每个数都代表着高度。
给出m个询问 问[l,r]区间<=H 的个数？
解析:
主席树裸查询
对于<=H 的个数，我们可以二分去找
如果找到了H，那么就直接返回R-L两个版本主席树的左子树个数
如果H在右子树上，那么说明左子树都是满足条件的，所以必须要加上，然后再向右子树继续二分找到H
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1000;
int a[N];
int t,n,m,len,root[N],idx,l,r,x,tot;
int b[N];
struct node
{
int l,r,cnt;
}tr[N*46];
int find(int x)
{
return lower_bound(b+1,b+1+len,x)-b;
}
int build(int l,int r)
{
int p=++idx;if(l==r) return p;int mid=l+r>>1;tr[p].l=build(l,mid);tr[p].r=build(mid+1,r);return p;}
int insert(int p,int l,int r,int x)
{
int q=++idx;tr[q]=tr[p];if(l==r){
tr[q].cnt++;return q;}int mid=l+r>>1;if(x<=mid) tr[q].l=insert(tr[p].l,l,mid,x);else tr[q].r=insert(tr[p].r,mid+1,r,x);tr[q].cnt=tr[tr[q].l].cnt+tr[tr[q].r].cnt;return q;
}
int query(int q,int p,int l,int r,int x)
{
if(l==r){
return tr[q].cnt-tr[p].cnt;}int mid=l+r>>1;if(x<=mid){
// cout<<mid<<"--------"<<endl;return query(tr[q].l,tr[p].l,l,mid,x);}else{
int ans=tr[tr[q].l].cnt-tr[tr[p].l].cnt;ans=ans+query(tr[q].r,tr[p].r,mid+1,r,x);return ans;}}
int main()
{
scanf("%d",&t);while(t--){
scanf("%d %d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];sort(b+1,b+1+n);len=unique(b+1,b+1+n)-b-1;root[0]=build(1,n);for(int i=1;i<=n;i++) root[i]=insert(root[i-1],1,n,find(a[i]));printf("Case %d:\n",++tot);while(m--){
scanf("%d %d %d",&l,&r,&x);l++;r++;x=upper_bound(b+1,b+1+len,x)-b-1;if(x==0) puts("0");else printf("%d\n",query(root[r],root[l-1],1,n,x));}}
}