Dễ dàng nhận thấy rằng ta có thể dùng thuật toán Mo's và Fenwick tree hoặc Segment tree để giải bài toán này trong $\mathcal{O}((n + q)\sqrt{n}\log n)$
Vậy thì làm thế nào để ta có thể tối ưu nó hơn? Gọi $freq(i)$ là tần số xuất hiện của phần tử $i$ trong đoạn ta đang xét, ta cũng có thể dễ dàng tính mảng $distinct(i)$ là số phần tử có $freq(i) > 0$. Ta có thể tính nhanh bằng cách dịch đoạn bằng Mo's với mỗi truy vấn trong $\mathcal{O}(B)$
Vậy vấn đề cuối cùng ở đây là làm sao để tính nhanh số phần tử có trong đoạn / số phần tử phân biệt?
Ta có thể chia mảng $freq$ và $distinct$ ra thành $B$ đoạn. Gọi $f(i)$ là tổng của $freq(j)$, và $d(i)$ là tổng của $distinct(j)$ với $j \in [i * B, (i + 1) * B)$
Sau khi xử lý xong, với mỗi truy vấn, ta chỉ đơn giản là xét các đoạn $i$ sao cho $[i * B, (i + 1) * B) \in [a, b]$ và xử lý đoạn không nằm trong hoàn toàn riêng. Khi ta chọn độ dài của đoạn $B = \sqrt{n}$ thì tổng độ phức tạp sẽ là $\mathcal{O}((n + q)*2\sqrt{n})$
Code tham khảo:
```cpp
#include "bits/stdc++.h"
using namespace std;
const int N = 1e5;
const int sqr = 320;
struct Query {
int l, r, a, b, idx;
pair<int, int> toPair() const {
int blk = l / sqr;
return {blk, blk & 1 ? -r : r};
}
bool operator<(const Query &other) {
return toPair() < other.toPair();
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, q;
cin >> n >> q;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
array<int, N + 1> freq{};
array<vector<int>, 2> cnt;
cnt[0] = cnt[1] = vector<int>(N / sqr + 1);
auto add = [&](int x) {
int blk = x / sqr;
cnt[0][blk]++;
cnt[1][blk] += (freq[x] == 0);
freq[x]++;
};
auto del = [&](int x) {
int blk = x / sqr;
cnt[0][blk]--;
cnt[1][blk] -= (freq[x] == 1);
freq[x]--;
};
vector<Query> queries(q);
for (int i = 0; i < q; i++) {
int l, r, a, b;
cin >> l >> r >> a >> b;
--l; --r;
queries[i] = {l, r, a, b, i};
}
sort(queries.begin(), queries.end());
vector<pair<int, int>> ans(q);
int cur_l = 0, cur_r = -1;
for (Query &qr : queries) {
while (cur_l > qr.l) add(v[--cur_l]);
while (cur_r < qr.r) add(v[++cur_r]);
while (cur_l < qr.l) del(v[cur_l++]);
while (cur_r > qr.r) del(v[cur_r--]);
auto &[u, v] = ans[qr.idx];
int x = qr.a / sqr;
int y = qr.b / sqr;
if (x == y) {
for (int i = qr.a; i <= qr.b; i++) {
u += freq[i];
v += freq[i] > 0;
}
} else {
for (int i = x + 1; i < y; i++) {
u += cnt[0][i];
v += cnt[1][i];
}
for (int i = qr.a; i < (x + 1) * sqr; i++) {
u += freq[i];
v += freq[i] > 0;
}
for (int i = y * sqr; i <= qr.b; i++) {
u += freq[i];
v += freq[i] > 0;
}
}
}
for (auto &it : ans) {
cout << it.first << ' ' << it.second << '\n';
}
}
```
bean
Created at
3 likes