题面:

给定一个序列,有多次询问,每次查询区间里小于等于某个数的元素的个数
即对于询问 (l,r,x),你需要输出 \sum_{i=l}^{r}[a_i \le x]∑ i=lr [a i ≤x] 的值
其中 [exp] 是一个函数,它返回 1 当且仅当 exp 成立,其中 exp 表示某个表达式


题解:

离线后树状数组OR主席树
我这里使用的是主席树的方法::
相当于预处理出,每个点的权值线段树。那么每次查询的时候直接查询r时刻前缀小于x的数量减去l-1时刻前缀小于x的数量就可以啦!


代码:

#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<int> VI;
const  ll inf  = 0x3f3f3f3f3f3f3f3f;
const int mod  = 998244353;
const int maxn = 1e5 + 6;
ll qpow(ll x,ll y){ll ans=1;x%=mod; while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;}

struct node{
    int l,r,sum;
}T[maxn*40];
int cnt=0;
void update(int l,int r,int &x,int y,int z){
    T[++cnt]=T[y];x=cnt;T[cnt].sum++;
    if(l==r) return ;
    int mid=l+r>>1;
    if(z<=mid) update(l,mid,T[x].l,T[y].l,z);
    else update(mid+1,r,T[x].r,T[y].r,z);
}

int ask(int l,int r,int x,int ql,int qr){
    if(ql<=l&&r<=qr){return T[x].sum;}

    int mid=l+r>>1,ans=0;
    if(ql<=mid) ans+=ask(l,mid,T[x].l,ql,qr);
    if(qr>mid) ans+=ask(mid+1,r,T[x].r,ql,qr);
    return ans;
}
int n,m,l,r,x,a[maxn],root[maxn];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        update(1,1e5,root[i],root[i-1],a[i]);
    }
    while(m--){
        scanf("%d%d%d",&l,&r,&x);
        printf("%d\n",ask(1,1e5,root[r],1,x)-ask(1,1e5,root[l-1],1,x));
    }
}