Ta sẽ giải bài này bằng cách truy vấn offline.
Đầu tiên, ta sẽ lưu tất cả những vị trí xuất hiện giá trị $x$ trong một mảng, gọi các mảng này là $pos[x]$. Điều này sẽ cho phép chúng ta truy vấn số lượng $x$ nằm trong đoạn $[l, r]$ trong $\mathcal{O}(log(n))$.
Lưu tất cả các truy vấn theo $x$, sau đó ta có thể duyệt qua từng giá trị $i \in [1, max(a)]$.
Với mỗi giá trị này, ta sẽ duyệt qua tất cả các bội $j$ của nó, sau đó thêm 1 lượng thích hợp. $j$ là bội của $i$, vậy thì $i$ chính là bội của $j$, và ngược lại. Điều này sẽ cho phép chúng ta trả lời truy vấn liên quan đến $i$ và $j$.
Độ phức tạp để duyệt là $n + \frac{n}{2} + \frac{n}{3} + ... + \frac{n}{n} \approx n \times log(n)$. Mỗi lần đếm số giá trị nằm trong khoảng mất $log(n)$, và có tổng cộng $q$ truy vấn như vậy. Vì vậy tổng độ phức tạp sẽ là $\mathcal{O}((n + q) \times log^2(n))$
**Code tham khảo:**
```cpp
#include "bits/stdc++.h"
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, q;
cin >> n >> q;
const int N = 2e5;
vector<vector<int>> pos(N + 1);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
pos[x].push_back(i);
}
vector<vector<array<int, 3>>> queries(N + 1);
for (int i = 0; i < q; i++) {
int l, r, x;
cin >> l >> r >> x;
--l; --r;
queries[x].push_back({l, r, i});
}
auto Count = [&](int l, int r, int x) {
return upper_bound(pos[x].begin(), pos[x].end(), r) - lower_bound(pos[x].begin(), pos[x].end(), l);
};
vector<int> ans(q);
for (int i = 1; i <= N; i++) {
for (int j = 2 * i; j <= N; j += i) {
for (auto &[l, r, idx] : queries[j]) {
ans[idx] += Count(l, r, i);
}
for (auto &[l, r, idx] : queries[i]) {
ans[idx] += Count(l, r, j);
}
}
for (auto &[l, r, idx] : queries[i]) {
ans[idx] += Count(l, r, i);
}
}
for (int i = 0; i < q; i++) {
cout << ans[i] << ' ';
}
}
```
bean
Created at
3 likes