「美团 CodeM 初赛 Round A」数列互质

给出一个长度为 $n$ 的数列 ${ a_1 , a_2 , a_3 , ... , a_n }$，以及 $m$ 组询问 $( l_i , r_i , k_i)$，求区间 $[ l_i , r_i ]$ 中有多少数在该区间中的出现次数与 $k_i$ 互质。

题目链接

「美团 CodeM 初赛 Round A」数列互质

输入输出格式

输入格式：

第一行，两个正整数 $n , m$。

第二行，$n$ 个正整数 $a_i$ 描述这个数列。

接下来 $m$ 行，每行三个正整数 $l_i , r_i , k_i$，描述一次询问。

输出格式

输出 $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

样例输出

说明

$1\le n,m\le 5\times 10^4$
$1\le a_i\le n$
$1\le l_i\le r_i\le n$
$1\le k_i\le n$

题解

先看这是一个区间问题，大概率数据结构。再看一眼数据范围，恩莫队可解，成了。
题目中要求统计某个数在 $[L,R]$ 有多少个数出现的次数与 $K$ 互质。我们开两个数组，一个记录区间内每个数出现的次数，另一个数组记录这个数出现的次数的次数。~~绕口令？~~ 比如样例的 $[4,7]$ 第一个数组 $cnt$就记录了区间内 $cnt[1] = 2，cnt[2] = 2$ $1,2$ 分别各出现两次。另一个数组 $num$ 用来记录 $num[cnt[1]] = 2$ ,代表这个区间内 $2$ 这个数出现了两次。这样在用莫队，统计的时候就方便了。剩下的看注释吧。

代码


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 7;
const int INF = 0x3f3f3f3f;

int block, num[MAXN], cnt[MAXN], belong[MAXN];
int n, m, a[MAXN], x, y, ret, ans[MAXN];
bool vis[MAXN];
vector<int> V;

struct Node {
    int l, r, k, id;
} data[MAXN];

bool cmp(Node a, Node b) {
    return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l]
                                       : ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
}

int read() {
    int x = 0, flag = 1;
    char ch = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            flag = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + ch - 48;
        ch = getchar();
    }
    return x * flag;
}
void write(int x) {
    if (x < 0)
        x = -x, putchar('-');
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + 48);
}

int gcd(int x, int y) { return (y) ? gcd(y, x % y) : x; }

void Build() {
    block = sqrt(n);
    for (int i = 1; i <= n; i++) belong[i] = (i - 1) / block + 1;
}

void solve(int x, int op) {
    --num[cnt[x]]; //先把这个数的贡献减去，再把后来改变的加上
    cnt[x] += op;
    ++num[cnt[x]];
    int t = cnt[x];
    if (t && !vis[t]) //如果这个数的出现次数不是0，并且这个出现的次数以前没在这个区间出现过，把他放到数组里，留到后面遍历
        vis[t] = 1, V.push_back(t);
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
    }
    Build();
    for (int i = 1; i <= m; i++) {
        data[i].l = read();
        data[i].r = read();
        data[i].k = read();
        data[i].id = i;
    }
    sort(data + 1, data + 1 + m, cmp);
    int L = 1, R = 0;
    for (int i = 1; i <= m; i++) {
        int ql = data[i].l, qr = data[i].r, qk = data[i].k;
        while (ql < L) solve(a[--L], 1); // 这里的顺序要特别注意不然会RE，具体自己手动领悟
        while (qr > R) solve(a[++R], 1);
        while (ql > L) solve(a[L++], -1);
        while (qr < R) solve(a[R--], -1);
        int t = 0, sz = V.size(); //V里面存的是出现的次数
        for (int j = 0; j < sz; j++) {
            if (num[V[j]]) {
                if (gcd(V[j], qk) == 1)
                    ans[data[i].id] += num[V[j]];
                V[t++] = V[j];
            } else {
                vis[V[j]] = 0; //当前区间内这个数出现的次数的次数为0，把他的标记去掉
            }
        }
        for (int j = sz - t; j >= 1; j--) V.pop_back(); //把那些出现次数的次数为0的数删去
    }
    for (int i = 1; i <= m; i++) {
        write(ans[i]), puts("");
    }
    return 0;
}