---
layout: 数列互质
title: 「美团 CodeM 初赛 Round A」数列互质
date: 2019-08-13 12:11:30
tags:
- 数据结构
- 莫队
categories:
- ACM
---
给出一个长度为 $n$ 的数列 ${ a_1 , a_2 , a_3 , ... , a_n }$，以及 $m$ 组询问 $( l_i , r_i , k_i)$，求区间 $[ l_i , r_i ]$ 中有多少数在该区间中的出现次数与 $k_i$ 互质。
<!--more-->
## 题目链接
[「美团 CodeM 初赛 Round A」数列互质](https://loj.ac/problem/6164)
## 输入输出格式
### 输入格式：
第一行，两个正整数 $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
```
### 样例输出
```
0
2
1
1
0
```
## 说明
- $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$ 这个数出现了两次。这样在用莫队，统计的时候就方便了。剩下的看注释吧。
## 代码
```cpp
#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;
}
```
「美团 CodeM 初赛 Round A」数列互质