[每日一题] 4.30 换个角度思考

题意：

解法：

时间复杂度：

std：

#include <bits/stdc++.h>
#define per(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn=100005;
int n,m;
int a[maxn];
vector<int>v[maxn<<2];
vector<int>::iterator it;
void build(int id,int l,int r)
{
    v[id].clear();
    per(i,l,r) v[id].push_back(a[i]);
    sort(v[id].begin(),v[id].end());
    if(l==r) return;
    int mid=(l+r)>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
}
int query(int id,int L,int R,int l,int r,int h)
{
    if(l<=L&&R<=r)
    {
        it=upper_bound(v[id].begin(),v[id].end(),h);
        return it-v[id].begin();
    }
    int mid=(L+R)>>1;
    int ans=0;
    if(l<=mid) ans+=query(id<<1,L,mid,l,r,h);
    if(mid<r) ans+=query(id<<1|1,mid+1,R,l,r,h);
    return ans;
}
int main()
{
    int T,t=1;
    scanf("%d%d",&n,&m);
    per(i,1,n) scanf("%d",&a[i]);
    build(1,1,n);
    int l,r,h;
    while(m--)
    {
        scanf("%d%d%d",&l,&r,&h);
        printf("%d\n",query(1,1,n,l,r,h));
    }
    return 0;
}