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';
}
}
```
Để giải quyết bài toán này, ta sẽ sử dụng thuật toán Mo. Nhưng nếu sử dụng Fenwick Tree để cập nhật
và truy vấn đáp án thì độ phức tạp thuật toán sẽ là $O(q \sqrt{n} \log{n})$ và không qua được time limit.
Việc sử dụng Fenwick Tree chính là lí do tại sao thuật toán trên chạy chậm. Ta cần một cấu trúc
dữ liệu có thể giải quyết các truy vấn sau:
1. Thêm một phần tử: $O(\log n)$, được gọi tổng cộng $O(q \sqrt{n})$ lần.
2. Xóa một phần tử: $O(\log n)$, được gọi tổng cộng $O(q \sqrt{n})$ lần.
3. Truy vấn đoạn: $O(\log n)$, được gọi tổng cộng $O(q)$ lần.
Nhận thấy rằng các truy vấn loại 1 và 2 được gọi nhiều hơn loại thứ 3. Để tối ưu, ta có thể "cân
bằng" độ phức tạp của các truy vấn. Ta sẽ làm truy vấn 1 và 2 chạy nhanh hơn, đánh đổi bằng việc
truy vấn thứ 3 sẽ chạy chậm hơn một chút. Ví dụ, ta có thể dựng một cấu trúc dữ liệu hỗ trợ các
thao tác như sau:
1. Thêm một phần tử: $O(1)$.
2. Xóa một phần tử: $O(1)$.
3. Truy vấn đoạn: $O(\sqrt{n})$.
Các bạn có thể tự cài một cấu trúc dữ liệu như vậy trước khi đọc tiếp hướng dẫn dưới đây.
Ta sẽ chia đoạn $[1, 10^5]$ thành các block có độ dài $S = \sqrt{n}$. Mỗi block sẽ lưu các giá trị
$sz_{cnt}, sz_{ext}$ lần lượt là số lượng các số các giá trị phân biệt trong block đó.
Khi thêm một phần tử $x$, ta sẽ tìm block chứa số $x$, gọi là $d$.
Để cập nhật, ta chỉ cần cộng $cnt[x]$ lên $1$ và $sz_{cnt}[d]$ lên $1$. Truy vấn xóa ta làm tương tự.
Việc cập nhật $sz_{ext}[d]$ khá dễ dàng khi chỉ có hai trường hợp là khi thêm số $x$ và $cnt[x] = 0$,
hoặc khi xóa số $x$ thì $cnt[x] = 1$. Độ phức tạp của cả truy vấn thêm và xóa là $O(1)$.
Để truy vấn số lượng các số và các giá trị phân biệt nằm trong đoạn $[a, b]$, ta có thể tìm trước
các block hoàn toàn nằm trong đoạn $[a, b]$ và cập nhật đáp án theo $sz_{cnt}$ và $sz_{ext}$.
Vì có $\frac{n}{S}$ block nên độ phức tạp của phần này là $O(\frac{n}{S}) = O(\sqrt{n})$.
Ở các block mà chứa biên của truy vấn, ta hoàn toàn có thể duyệt qua các phần tử ở biên đó. Độ
phức tạp khi duyệt qua các phần tử này là $O(S) = O(\sqrt{n})$
Đọc thêm: [Trick 2, Codeforces Blog - [Tutorial] Collection of little techniques](https://codeforces.com/blog/entry/100910)
```cpp
#include "bits/stdc++.h"
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using ll = long long;
using pii = pair<int, int>;
#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
assert(l <= r);
return uniform_int_distribution<ll> (l, r)(rng);
}
const int N = 1e5 + 3;
const int B = 320;
struct Query{
int l, r, x, y, id;
bool operator < (const Query &o) { return l / B != o.l / B ? l / B < o.l / B : r < o.r; }
};
struct sqrtDS{
int n;
vector<int> cnt, ext, id, sz_cnt, sz_ext;
void init(int _n){
n = _n + 2;
cnt.resize(n + 2, 0);
ext.resize(n + 2, 0);
id.resize(n + 2, 0);
sz_cnt.resize(n + 2, 0);
sz_ext.resize(n + 2, 0);
for(int i = 1; i <= n; ++i)
id[i] = (i + B - 1) / B;
}
void add(int x){
debug(+1, x);
sz_ext[id[x]] += (cnt[x] == 0);
ext[x] = 1;
++cnt[x];
++sz_cnt[id[x]];
}
void del(int x){
--cnt[x];
--sz_cnt[id[x]];
sz_ext[id[x]] -= (cnt[x] == 0);
ext[x] = (cnt[x] > 0);
}
pii query(int l, int r){
int res_cnt = 0, res_ext = 0;
for(int i = l; i <= r and id[i] == id[l]; ++i)
res_cnt += cnt[i], res_ext += ext[i];
if(id[l] != id[r])
for(int i = r; i >= l and id[i] == id[r]; --i)
res_cnt += cnt[i], res_ext += ext[i];
for(int bl = id[l] + 1; bl < id[r]; ++bl)
res_cnt += sz_cnt[bl], res_ext += sz_ext[bl];
debug(l, r, res_cnt, res_ext);
return {res_cnt, res_ext};
}
};
sqrtDS dak;
int n, q, a[N];
vector<Query> d;
pii res[N];
void solve(){
dak.init(N);
cin >> n >> q;
for(int i = 1; i <= n; ++i)
cin >> a[i];
for(int i = 1; i <= q; ++i){
int l, r, x, y;
cin >> l >> r >> x >> y;
d.push_back({l, r, x, y, i});
}
sort(all(d));
int cur_l = 1, cur_r = 0;
for(auto [l, r, x, y, id] : d){
while(cur_l > l){
--cur_l;
dak.add(a[cur_l]);
}
while(cur_r < r){
++cur_r;
dak.add(a[cur_r]);
}
while(cur_l < l){
dak.del(a[cur_l]);
++cur_l;
}
while(cur_r > r){
dak.del(a[cur_r]);
--cur_r;
}
res[id] = dak.query(x, y);
}
for(int i = 1; i <= q; ++i)
cout << res[i].F << ' ' << res[i].S << '\n';
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(0);
#define task "troll"
if(fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int test = 1;
// cin >> test;
for(int i = 1; i <= test; ++i){
// cout << "Case #" << i << ": ";
solve();
}
#ifdef LOCAL
cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
#endif
return 0;
}
```
bean
Created at
9 likes
kh0i
Created at
1 likes