Solutions of Range query

Select solution language

Write solution here.

bean Created at 9 likes

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'; } }$