换个角度思考

显然是可以离线之后fenwick维护。

因为不喜欢离线，所以直接主席树了。

每次找到对应区间，然后相当于就是区间sum的问题了。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=N*40;
int n,m,rt[N],lc[M],rc[M],sum[M],cnt;
#define mid (l+r>>1)
void change(int l,int r,int &x,int y,int k){
    sum[x=++cnt]=sum[y]+1,lc[x]=lc[y],rc[x]=rc[y];
    if(l==r)    return ;
    if(k<=mid)    change(l,mid,lc[x],lc[y],k);
    else    change(mid+1,r,rc[x],rc[y],k);
}
int ask(int l,int r,int x,int y,int ql,int qr){
    if(l==ql&&r==qr)    return sum[y]-sum[x];
    if(qr<=mid)    return ask(l,mid,lc[x],lc[y],ql,qr);
    else if(ql>mid)    return ask(mid+1,r,rc[x],rc[y],ql,qr);
    else return ask(l,mid,lc[x],lc[y],ql,mid)+ask(mid+1,r,rc[x],rc[y],mid+1,qr);
}
signed main(){
    cin>>n>>m;
    for(int i=1,x;i<=n;i++)    scanf("%d",&x),change(1,1e5,rt[i],rt[i-1],x);
    for(int i=1,l,r,k;i<=m;i++)    scanf("%d %d %d",&l,&r,&k),printf("%d\n",ask(1,1e5,rt[l-1],rt[r],1,k));
    return 0;
}