题解

莫队+值域分块
把询问储存起来，然后套莫队的板子
然后每次加和减这里如果采取线段树/树状数组进行操作会T
可以改用值域分块

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+5;
struct Node
{
    int l,r;
    int x;
    int id;
}q[N];
int n,m,a[N];
int block,block2;
int res[N];
int *cnt;
int cnt2[N];

bool cmp(const Node &a,const Node &b)
{
    return (a.l/block)^(b.l/block)?a.l<b.l:(((b.l/block)&1)?a.r<b.r:a.r>b.r);
}

inline void add(int x)
{
    cnt[a[x]/block2]++;
    cnt2[a[x]]++;
}

inline void del(int x)
{
    cnt[a[x]/block2]--;
    cnt2[a[x]]--;
}

inline int ask(int x)
{
    int bk=x/block2;
    int ans=0;
    for(int i=0;i<bk;i++)
        ans+=cnt[i];
    for(int i=bk*block2;i<=x;i++)
        ans+=cnt2[i];
    return ans;
}

int main()
{
    block2=sqrt(N);
    int num=N/block2+5;
    cnt=new int[num];
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].x);
        q[i].id=i;
    }

    block=n/sqrt(m*2/3*1.0);
    sort(q+1,q+m+1,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;i++)
    {
        int ql=q[i].l,qr=q[i].r;
        while(l>ql)
            add(--l);
        while(l<ql)
            del(l++);
        while(r<qr)
            add(++r);
        while(r>qr)
            del(r--);
        res[q[i].id]=ask(q[i].x);
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",res[i]);
    return 0;
}