每日一题 4.30 换个角度思考

看题目后 不会呀数据结构 (巨佬队友说是主席树的板子题
果断向他学习了一下 下面是我的学习理解
主席树相当于线段树1-1,1-2,1-n的前缀和 于是这样就可以用来维护区间信息
将 l-r变为 1-l 1-r的减法
套上板子 这题维护的信息是区间的名次

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
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();
    for(int i=l;i<=r;++i) 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);
    for(int i=1;i<=n;++i) 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;
}