前言:

这题假如用树状数组的话,还是很不错的一个题的.

思路:

直接把两个序列都按权值排序,把查询的以及原序列,这样做的好处就是保证我插入的一定是合法的,然后直接查询即可.

代码:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
struct Query{
    int l,r,k,id,ans;//询问区间[l,r]小于等于k的个数.存下查询时间轴以及答案.
}q[N],w[N];
int n,m,c[N];
int lowbit(int x)    { return x&(-x); }
void add(int u,int x)
{
    while(u<=n)
    {
        c[u]+=x;
        u+=lowbit(u);
    }
}

int ask(int u)
{
    int res=0;
    while(u)
    {
        res+=c[u];
        u-=lowbit(u);
    }return res;
}

bool cmp(Query A,Query B)
{
    return A.id<B.id;
}

bool cnp(Query A,Query B)
{
    return A.k<B.k;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i].k);
        w[i].id=i;
    }sort(w+1,w+1+n,cnp);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
        q[i].id=i;
    }sort(q+1,q+1+m,cnp);int id=1;
    for(int i=1;i<=m;i++)
    {
        while(w[id].k<=q[i].k&&id<=n)    add(w[id].id,1),id++;
        q[q[i].id].ans=ask(q[i].r)-ask(q[i].l-1);
    }sort(q+1,q+1+m,cmp);
    for(int i=1;i<=m;i++)    printf("%d\n",q[i].ans);
    return 0;
}