入门级的莫队，时间复杂度O(n√n)

解题思路:入门级的莫队，不会的可以看看这篇莫队入门文章：https://www.cnblogs.com/WAMonster/p/10118934.html

注意事项:

参考代码:

#include<bits/stdc++.h>//普通莫队

using namespace std;

#define maxn 100010

#define maxm 100010

int n,m;

int a[maxn];

struct query{

    int l,r;

    int k;

    int id;//第几个被查询

}q[maxm];

int siz,bnum,belong[maxn];

int cnt[maxn],ans[maxm],cal[maxn];//cnt[a[i]]表示a[i]在区间[l,r]出现的次数,cal[i]表示在区间[l,r]出现次数为i的不同数的个数

//比如[l,r]为 2 2 2 1 2 3 3 1 4 时，cal[1]=1,cal[2]=2,cal[3]=0,cal[4]=1

bool cmp(query& x,query& y){

    return belong[x.l]==belong[y.l]?x.r<y.r:belong[x.l]<belong[y.l];

}

void add(int pos) {

    cal[cnt[a[pos]]]--;

    ++cnt[a[pos]];

    cal[cnt[a[pos]]]++;

}

void del(int pos) {

    cal[cnt[a[pos]]]--;

    --cnt[a[pos]];

    cal[cnt[a[pos]]]++;

}

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++)scanf("%d",&a[i]);

    scanf("%d",&m);

    for(int i=1;i<=m;i++){

        scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);

        q[i].id=i;

    }

    siz=sqrt(n);

    bnum=ceil((double)n/siz);

    for(int i=1;i<=bnum;i++){

        for(int j=(i-1)*siz+1;j<=i*siz;j++){

            belong[j]=i;

        }

    }

    sort(q+1,q+1+m,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) del(l++);//等价于{del(l);l++;}

        while(l > ql) add(--l);

        while(r < qr) add(++r);

        while(r > qr) del(r--);

        ans[q[i].id]=cal[q[i].k];

    }

    for(int i=1;i<=m;i++){

        printf("%d\n",ans[i]);

    }

    //system("pause");

    return 0;

}