题解 | #数列互质#

做法：莫队 + 根号分治

显然这题我们需要莫队来处理询问，我们用两个unordered_map<int, int> mp, cnt 来分别记录数字 的出现次数 和出现次数为 的数的个数 . 我们可以发现，出现次数如果很多，那么不同的数字就会很少；不同的数字很多，那么出现的次数就会很少，容易证明二者平均时大家的个数都是 。

复杂度：

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
struct node {
	int l, r, w, id;
};
int n, m, a[N], belong[N], L[N], R[N], ans[N];
unordered_map<int, int> mp, cnt;
void add(int x) {
	x = a[x];
	if (mp.count(x)) cnt[mp[x]]--;
	if (cnt[mp[x]] == 0) cnt.erase(mp[x]);
	mp[x]++, cnt[mp[x]]++;
}
void sub(int x) {
	x = a[x];
	cnt[mp[x]]--;
	if (cnt[mp[x]] == 0) cnt.erase(mp[x]);
	mp[x]--;
	if (mp[x] == 0) mp.erase(x);
	else cnt[mp[x]]++;
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	vector<node> q(m);
	for (int i = 0; i < m; ++i) {
		cin >> q[i].l >> q[i].r >> q[i].w;
		q[i].id = i + 1;
	}
	int siz = sqrt(n);
	for (int i = 1; i <= n; ++i) belong[i] = (i - 1) / siz + 1;
	sort(q.begin(), q.end(), [](auto a, auto b) {
		return belong[a.l] == belong[b.l] ? a.r < b.r : belong[a.l] < belong[b.l];
	});
	int i = 1, j = 0;
	for (auto [l, r, w, id] : q) {
		while (j < r) add(++j);
		while (j > r) sub(j--);
		while (i > l) add(--i);
		while (i < l) sub(i++);
		if (mp.size() > cnt.size()) {//根号分治
			for (auto [u, v] : cnt) {
				if (gcd(u, w) == 1) ans[id] += v;
			}
		} else {
			for (auto [u, v] : mp) {
				if (gcd(v, w) == 1) ans[id]++;
			}
		}
	}
	for (int i = 1; i <= m; ++i) {
		cout << ans[i] << "\n";
	}
	return 0;
}