换个角度思考 题解

看样子，应该有比较好的做法，不过，这道题，肯定要上主席树辣！！

如果打算用主席树做这道题的话，这道题就是一个主席树的纯板子问题了。。。

相当于查询区间l-r中1-x的数字的个数

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
struct node{
    int lson,rson,w;
}t[N<<5];
int rt[N],cnt;
inline void insert(int &now,int pas,int l,int r,int x){
    now=++cnt;
    t[now]=t[pas];
    ++t[now].w;
    if(l==r){
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid){
        insert(t[now].lson,t[pas].lson,l,mid,x);
    }else{
        insert(t[now].rson,t[pas].rson,mid+1,r,x);
    }
}
inline int find(int now,int pas,int l,int r,int lc,int rc){
    if(lc<=l&&r<=rc){
        return t[now].w-t[pas].w;
    }
    int mid=(l+r)>>1,res=0;
    if(lc<=mid){
        res+=find(t[now].lson,t[pas].lson,l,mid,lc,rc);
    }
    if(rc>mid){
        res+=find(t[now].rson,t[pas].rson,mid+1,r,lc,rc);
    }
    return res;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        int x;
        scanf("%d",&x);
        insert(rt[i],rt[i-1],1,1e5,x);
    }
    while(m--){
        int l,r,x;
        scanf("%d%d%d",&l,&r,&x);
        printf("%d\n",find(rt[r],rt[l-1],1,1e5,1,x));
    }
    return 0;
}