离散化版：

#include<bits/stdc++.h>
using namespace std;
#define lc(x) tr[x].ls
#define rc(x) tr[x].rs
#define mid ((l+r)>>1)
typedef long long LL;
const int N=1e5+10;
struct trnode{int ls,rs,siz;}tr[N*40]; int trlen,rt[N];LL a[N],lsh[N];
void change(int pre,int &now,int l,int r,int x)
{
    now=++trlen;tr[now]=tr[pre];
    tr[now].siz++;
    if(l==r){return ;}
    if(x<=mid) change(lc(pre),lc(now),l,    mid,x);
    else       change(rc(pre),rc(now),mid+1,r , x);
     
}
int query(int pre,int now,int l,int r,int k)
{
    if(!now)return 0;
    if(l==r && l<=k) return tr[now].siz-tr[pre].siz;
    int sum=tr[lc(now)].siz-tr[lc(pre)].siz;
    if(k<=mid) return query(lc(pre),lc(now), l, mid, k);
    else       return sum+query(rc(pre),rc(now), mid+1, r, k);
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) scanf("%lld",&a[i]),lsh[i]=a[i];
    sort(lsh+1,lsh+n+1);int ln=unique(lsh+1, lsh+n+1)-lsh-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+ln+1,a[i])-lsh;
       
    trlen=0;rt[0]=0;
    for(int i=1; i<=n; i++) change(rt[i-1],rt[i],1,ln,a[i]);
    for(int i=1,x,y; i<=m; i++)
    {
        LL k;scanf("%d%d%lld",&x,&y,&k);
        k=upper_bound(lsh+1,lsh+ln+1,k)-lsh-1; 
        printf("%d\n", query(rt[x-1],rt[y],1,ln,k));
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define lc(x) tr[x].ls
#define rc(x) tr[x].rs
#define mid ((l+r)>>1)
typedef long long LL;
const int N=1e5+10;
const LL inf=1e12;
struct trnode{int ls,rs,siz;}tr[N*200]; int trlen,rt[N];LL a[N],lsh[N];
void change(int pre,int &now,LL l,LL r,LL x)
{
    now=++trlen;tr[now]=tr[pre];
    tr[now].siz++;
    if(l==r){return ;}
    if(x<=mid) change(lc(pre),lc(now),l,    mid,x);
    else       change(rc(pre),rc(now),mid+1,r , x);
      
}
int query(int pre,int now,LL l,LL r,LL k)
{
    if(!now)return 0;
    if(l==r && l<=k) return tr[now].siz-tr[pre].siz;
    int sum=tr[lc(now)].siz-tr[lc(pre)].siz;
    if(k<=mid) return query(lc(pre),lc(now), l, mid, k);
    else       return sum+query(rc(pre),rc(now), mid+1, r, k);
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) scanf("%lld",&a[i]),a[i]+=inf;
    trlen=0;rt[0]=0;
    for(int i=1; i<=n; i++) change(rt[i-1],rt[i],0,2*inf,a[i]);
    for(int i=1,x,y; i<=m; i++)
    {
        LL k;scanf("%d%d%lld",&x,&y,&k);k+=inf;
        printf("%d\n", query(rt[x-1],rt[y],0,2*inf,k));
    }
    return 0;
}

离散化版：

#include<bits/stdc++.h>
using namespace std;
#define lc(x) tr[x].ls
#define rc(x) tr[x].rs
#define mid ((l+r)>>1)
typedef long long LL;
const int N=1e5+10;
struct trnode{int ls,rs,siz;}tr[N*40]; int trlen,rt[N];LL a[N],lsh[N];
void change(int pre,int &now,int l,int r,int x)
{
    now=++trlen;tr[now]=tr[pre];
    tr[now].siz++;
    if(l==r){return ;}
    if(x<=mid) change(lc(pre),lc(now),l,    mid,x);
    else       change(rc(pre),rc(now),mid+1,r , x);
     
}
int query(int pre,int now,int l,int r,int k)
{
    if(!now)return 0;
    if(l==r && l<=k) return tr[now].siz-tr[pre].siz;
    int sum=tr[lc(now)].siz-tr[lc(pre)].siz;
    if(k<=mid) return query(lc(pre),lc(now), l, mid, k);
    else       return sum+query(rc(pre),rc(now), mid+1, r, k);
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) scanf("%lld",&a[i]),lsh[i]=a[i];
    sort(lsh+1,lsh+n+1);int ln=unique(lsh+1, lsh+n+1)-lsh-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+ln+1,a[i])-lsh;
       
    trlen=0;rt[0]=0;
    for(int i=1; i<=n; i++) change(rt[i-1],rt[i],1,ln,a[i]);
    for(int i=1,x,y; i<=m; i++)
    {
        LL k;scanf("%d%d%lld",&x,&y,&k);
        k=upper_bound(lsh+1,lsh+ln+1,k)-lsh-1; 
        printf("%d\n", query(rt[x-1],rt[y],1,ln,k));
    }
    return 0;
} 

#include<bits/stdc++.h>
using namespace std;
#define lc(x) tr[x].ls
#define rc(x) tr[x].rs
#define mid ((l+r)>>1)
typedef long long LL;
const int N=1e5+10;
const LL inf=1e12;
struct trnode{int ls,rs,siz;}tr[N*200]; int trlen,rt[N];LL a[N],lsh[N];
void change(int pre,int &now,LL l,LL r,LL x)
{
    now=++trlen;tr[now]=tr[pre];
    tr[now].siz++;
    if(l==r){return ;}
    if(x<=mid) change(lc(pre),lc(now),l,    mid,x);
    else       change(rc(pre),rc(now),mid+1,r , x);
}
int query(int pre,int now,LL l,LL r,LL k)
{
if(!now)return 0;
if(l==r && l<=k) return tr[now].siz-tr[pre].siz;
int sum=tr[lc(now)].siz-tr[lc(pre)].siz;
if(k<=mid) return query(lc(pre),lc(now), l, mid, k);
else       return sum+query(rc(pre),rc(now), mid+1, r, k);
}
int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) scanf("%lld",&a[i]),a[i]+=inf;
trlen=0;rt[0]=0;
for(int i=1; i<=n; i++) change(rt[i-1],rt[i],0,2inf,a[i]);
for(int i=1,x,y; i<=m; i++)
{
LL k;scanf("%d%d%lld",&x,&y,&k);k+=inf;
printf("%d\n", query(rt[x-1],rt[y],0,2inf,k));
}
return 0;
}