时间限制：6秒

空间限制：524288K
给出一个长度为 n 的数列 { a[1] , a[2] , a[3] , … , a[n] }，以及 m 组询问 ( l[i] , r[i] , k[i])。
求数列下标区间在 [ l[i] , r[i] ] 中有多少数在该区间中的出现次数与 k[i] 互质（最大公约数为1）。
输入描述:

第一行，两个正整数 n , m (1 ≤ n, m ≤ 50000)。
第二行，n 个正整数 a[i] (1 ≤ a[i] ≤ n)描述这个数列。
接下来 m 行，每行三个正整数 l[i] , r[i] , k[i] (1 ≤ l[i] ≤ r[i] ≤ n, 1 ≤ k[i] ≤ n)，描述一次询问。

输出描述:

输出 m 行，即每次询问的答案。

输入例子:

10 5
1 1 1 1 1 2 2 2 2 2
4 7 2
4 7 3
4 8 2
4 8 3
3 8 3

输出例子:

0
2
1
1
0

解法：莫队莽

#include <bits/stdc++.h>
using namespace std;
const int maxn = 50005;
int n, m, block, a[maxn], cnt[maxn], ans[maxn], pos[maxn];
unordered_map <int,int> num;
struct node{
    int l, r, k, id;
    bool operator < (const node &rhs) const{
        if(l/block == rhs.l/block) return r<rhs.r;
        return l/block < rhs.l/block;
    }
}q[maxn];
void add(int x){
    int temp = cnt[a[x]];
    if(num.count(temp)){
        num[temp]--;
        if(num[temp]==0) num.erase(temp);
    }
    temp=++cnt[a[x]];
    num[temp]++;
}
void del(int x){
    int temp = cnt[a[x]];
    num[temp]--;
    if(num[temp]==0) num.erase(temp);
    temp = --cnt[a[x]];
    if(temp) num[temp]++;
}
int query(int x){
    int ret = 0;
    for(unordered_map<int,int>::iterator it=num.begin(); it!=num.end(); it++){
        if(__gcd(it->first,x)==1) ret+=it->second;
    }
    return ret;
}
int main()
{
    scanf("%d%d",&n,&m);
    block = sqrt(n);
    for(int i=0; i<n; i++) scanf("%d",&a[i]);
    for(int i=0; i<m; i++){
        scanf("%d %d %d", &q[i].l, &q[i].r, &q[i].k);
        q[i].l--;
        q[i].r--;
        q[i].id = i;
    }
    sort(q,q+m);
    int l = 0, r = -1;
    while(r<q[0].r) {++r;add(r);}
    while(l<q[0].l) {del(l);++l;};
    ans[q[0].id] = query(q[0].k);
    for(int i = 1; i<m; i++){
        while(r<q[i].r) {++r;add(r);};
        while(r>q[i].r) {del(r);--r;};
        while(l<q[i].l) {del(l);++l;};
        while(l>q[i].l) {--l;add(l);};
        ans[q[i].id] = query(q[i].k);
    }
    for(int i = 0; i<m; i++){
        printf("%d\n", ans[i]);
    }
    return 0;
}