题意：
求区间里< = h的数的个数
思路：
排序后二分查找小于等于h的最大位置pos
问题转化为区间[ l , r ]里有多少个数在[ 1 , p o s ]之间。
主席树维护某个数出现的次数
注意多组输入要清空数组
要离散化
代码：
const int maxn=1e5+7,mod=1e9+7,inf=0x3f3f3f3f; int n,m,a[maxn],b[maxn]; int root[maxn],idx; struct node{ int l,r,cnt; }tr[maxn*40]; int build(int l,int r){ int p=++idx; tr[p].l=tr[p].r=tr[p].cnt=0; if(l==r) return p; int mid=(l+r)/2; 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)/2; 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 s,int e,int ql,int qr,int l,int r){ if(ql<=l&&r<=qr) return tr[e].cnt-tr[s].cnt; int mid=(l+r)/2,res=0; if(ql<=mid) res+=query(tr[s].l,tr[e].l,ql,qr,l,mid); if(qr>mid) res+=query(tr[s].r,tr[e].r,ql,qr,mid+1,r); return res; } int main(){ int _=read,Case=0; while(_--){ n=read,m=read; rep(i,1,n) a[i]=read,b[i]=a[i]; sort(b+1,b+1+n); int siz=unique(b+1,b+1+n)-(b+1); rep(i,1,n) a[i]=lower_bound(b+1,b+1+siz,a[i])-(b); idx=0; root[0]=build(1,siz); rep(i,1,n) root[i]=insert(root[i-1],1,siz,a[i]); printf("Case %d:\n",++Case); while(m--){ int l=read+1,r=read+1,h=read; int pos=upper_bound(b+1,b+1+siz,h)-b; pos--; if(!pos) puts("0"); else{ printf("%d\n",query(root[l-1],root[r],1,pos,1,siz)); } } } return 0; }
