题目让求 L R区间 不大于H 的数有多少
数据太大需要离散化
#include<bits/stdc++.h>
using namespace std;
#define maxn 100010
int a[maxn],root[maxn],tot,n,m;
vector<int>q;
struct ac{
int va,l,r;
}tre[maxn*];
void init(){
memset(root,,sizeof(root));
memset(tre,,sizeof(tre));
tot=;q.clear();
}
int getid(int x){
;
}
void updata(int l,int r,int& x,int in,int z){
tre[++tot]=tre[in];
tre[tot].va++;
x=tot;
if(l==r) return ;
;
if(z>mid){
updata(mid+,r,tre[x].r,tre[in].r,z);
}else{
updata(l,mid,tre[x].l,tre[in].l,z);
}
}
int query(int x,int y,int l,int r,int z){
if(x==y) return(tre[r].va-tre[l].va);
;
if(z<=mid){
return query(x,mid,tre[l].l,tre[r].l,z);
}
int ans=tre[tre[r].l].va-tre[tre[l].l].va;
,y,tre[l].r,tre[r].r,z));
}
int main(){
;
cin>>t;
while(t--){
scanf("%d%d",&n,&m);
init();
;j<=n;j++){
scanf("%d",&a[j]);
q.push_back(a[j]);
}
sort(q.begin(),q.end());
q.erase(unique(q.begin(),q.end()),q.end());
int len=q.size();
;j<=n;j++){
int x=getid(a[j]);
updata(,len,root[j],root[j-],x);
}
printf("Case %d:\n",cnt++);
;j<m;j++){
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
l++,r++;
)-;
,len,root[l-],root[r],z));
else printf("0\n");// 如果要查的数不在 a数组中直接输出0 k<min(an)
}
}
}