题目链接：Super Mario
题解：几乎跟第K大查不多的主席树，先把按数组建好主席树，然后询问的时候注意L，R,它范围是从0到n-1，然后二分找到H是原数组中的第几大=K，查询1~k的sum[]
的和就可以
#include<bits/stdc++.h> #include<set> #include<cstdio> #include<iomanip> #include<iostream> #include<string> #include<cstring> #include<algorithm> #define pb push_back #define ll long long #define PI 3.14159265 //#define ls l,m,rt<<1 //#define rs m+1,r,rt<<1|1 #define eps 1e-7 typedef unsigned long long ull; const int mod=1e9+9; const ll inf=0x3f3f3f3f3f3f3f; const int maxn=1e5+5; using namespace std; int a[maxn],b[maxn],sum[maxn*30],rt[maxn],n,m,sz,t; int ls[maxn*30],rs[maxn*30],tot; void build(int &o,int l,int r) { o=++tot; sum[o]=0; if(l==r)return; int m=(l+r)>>1; build(ls[o],l,m); build(rs[o],m+1,r); } void update(int &o,int pre,int l,int r,int x) { o=++tot; sum[o]=sum[pre]+1; ls[o]=ls[pre]; rs[o]=rs[pre]; if(l==r)return; int m=(l+r)>>1; if(x<=m)update(ls[o],ls[pre],l,m,x); else update(rs[o],rs[pre],m+1,r,x); } int query(int pl,int pr,int l,int r,int x) { if(r==l) { return sum[pr]-sum[pl]; } int m=(l+r)>>1; if(x<=m)return query(ls[pl],ls[pr],l,m,x); else return sum[ls[pr]]-sum[ls[pl]]+query(rs[pl],rs[pr],m+1,r,x); } int main() { scanf("%d",&t); int num=1; while(t--) { scanf("%d %d",&n,&m); tot=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]);b[i]=a[i]; } sort(b+1,b+n+1); int sz=unique(b+1,b+1+n)-b-1; for(int i=1;i<=n;i++) { a[i]=lower_bound(b+1,b+1+sz,a[i])-b; } build(rt[0],1,sz); for(int i=1;i<=n;i++)update(rt[i],rt[i-1],1,sz,a[i]); printf("Case %d: ",num++); while(m--) { int l,r,h; scanf("%d %d %d",&l,&r,&h); if(h<b[1]) { printf("0 ");continue; } else if(h>=b[sz]) { printf("%d ",r-l+1);continue;} int p=lower_bound(b+1,b+sz+1,h)-b; if(b[p]>h)p--; // printf("####%d ",p); printf("%d ",query(rt[l],rt[r+1],1,sz,p)); } } return 0; }