牛客小白月赛9 E.换个角度思考

分析:一个新的方法求任意区间小于等于k的个数.-------离散+树状数组.
将询问按照 大小从小到大排序,并且将 也从小到大排序，然后根据询问从小到大插入到树状数组对应编号中,当大于时候更新询问答案.复杂度可以做到O(nlogn).
十分优美的方法

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)

using namespace std;

const int maxn=1e5+10;
int cnt,sum[maxn];
void add( int x,int c ){ while( x<=cnt ) sum[x]+=c,x+=lowbit(x); }
int query( int x ,int ans=0 ) { while( x ) ans+=sum[x],x-=lowbit(x);return ans; }

struct quest{
    int l,r,k,id;
    bool operator < ( const quest &rhs ) const{ return k<rhs.k || k==rhs.k && id<rhs.id; }
}q[maxn];

vector<int>p;
struct node{
    int val,id;
    bool operator < ( const node &rhs ) const{ return val<rhs.val || val<rhs.val && id<rhs.id ; }
}a[maxn];
int ans[maxn];


int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for( int i=1;i<=n;i++ )
    {
        scanf("%d",&a[i].val);
        a[i].id=i;
    }

    sort(a+1,a+1+n);
    cnt=n;
    for( int i=1,l,r,k;i<=m;i++ )
    {
        scanf("%d%d%d",&l,&r,&k);
        q[i]={l,r,k,i};
    }
    sort(q+1,q+1+m);
    for( int i=1,j=1;i<=m;i++ )
    {
        int k=q[i].k;
        for( ;j<=n && a[j].val<=k;j++ ) add( a[j].id,1 );
        ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
    }
    for( int i=1;i<=m;i++ ) printf("%d\n",ans[i]);

}