Hướng giải của [Mo's] Cập Nhật
Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Tác giả:
Hướng dẫn giải
Bài toán yêu cầu xử lý cả truy vấn đoạn và cập nhật điểm. Sử dụng Mo's Algorithm 3 chiều (Mo's with Updates).
Ý tưởng:
- Thêm chiều thời gian \(t\): số thao tác cập nhật đã xảy ra trước truy vấn.
- Mỗi truy vấn có dạng \((L, R, t)\).
- Sắp xếp theo: \((L / blockSize, R / blockSize, t)\) với block size = \(N^{2/3}\).
- Duy trì mảng tần suất và biến đếm distinct.
- Khi di chuyển con trỏ thời gian:
applyUpdate(t): áp dụng cập nhật thứ \(t\), nếu vị trí nằm trong \([curL, curR]\) thì cập nhật tần suất tương ứng.undoUpdate(t): hoàn tác cập nhật thứ \(t\).
Độ phức tạp: \(O((N+Q) \cdot N^{2/3})\).
Mã nguồn C++
#include <bits/stdc++.h>
using namespace std;
int blockSize;
struct Query {
int l, r, t, idx;
bool operator<(const Query& o) const {
int bl = l / blockSize, br = o.l / blockSize;
if (bl != br) return bl < br;
int bbl = r / blockSize, bbr = o.r / blockSize;
if (bbl != bbr) return bbl < bbr;
return t < o.t;
}
};
struct Update {
int pos, oldVal, newVal;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
// Nén toàn bộ giá trị
vector<int> vals = a;
vector<Query> queries;
vector<Update> updates;
int updCnt = 0;
for (int i = 0; i < q; i++) {
int type; cin >> type;
if (type == 2) {
int l, r; cin >> l >> r;
queries.push_back({l - 1, r - 1, updCnt, (int)queries.size()});
} else {
int pos, val; cin >> pos >> val;
updates.push_back({pos - 1, a[pos - 1], val});
a[pos - 1] = val;
vals.push_back(val);
updCnt++;
}
}
// Khôi phục mảng a ban đầu
for (int i = 0; i < n; i++) a[i] = vals[i];
// Nén giá trị
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
auto get = [&](int v) { return lower_bound(vals.begin(), vals.end(), v) - vals.begin(); };
for (int i = 0; i < n; i++) a[i] = get(a[i]);
for (auto& u : updates) {
u.oldVal = get(u.oldVal);
u.newVal = get(u.newVal);
}
blockSize = max(1, (int)pow(n, 2.0 / 3.0));
sort(queries.begin(), queries.end());
vector<int> ans(queries.size());
vector<int> freq(vals.size(), 0);
int distinct = 0, curL = 0, curR = -1, curT = 0;
auto add = [&](int pos) {
if (freq[a[pos]] == 0) distinct++;
freq[a[pos]]++;
};
auto remove = [&](int pos) {
freq[a[pos]]--;
if (freq[a[pos]] == 0) distinct--;
};
auto apply = [&](int t, int l, int r) {
auto& u = updates[t];
if (u.pos >= l && u.pos <= r) {
freq[a[u.pos]]--;
if (freq[a[u.pos]] == 0) distinct--;
a[u.pos] = u.newVal;
if (freq[a[u.pos]] == 0) distinct++;
freq[a[u.pos]]++;
} else {
a[u.pos] = u.newVal;
}
};
auto undo = [&](int t, int l, int r) {
auto& u = updates[t];
if (u.pos >= l && u.pos <= r) {
freq[a[u.pos]]--;
if (freq[a[u.pos]] == 0) distinct--;
a[u.pos] = u.oldVal;
if (freq[a[u.pos]] == 0) distinct++;
freq[a[u.pos]]++;
} else {
a[u.pos] = u.oldVal;
}
};
for (auto& qr : queries) {
while (curT < qr.t) apply(curT++, curL, curR);
while (curT > qr.t) undo(--curT, curL, curR);
while (curL > qr.l) add(--curL);
while (curR < qr.r) add(++curR);
while (curL < qr.l) remove(curL++);
while (curR > qr.r) remove(curR--);
ans[qr.idx] = distinct;
}
for (int i = 0; i < (int)ans.size(); i++)
cout << ans[i] << "\n";
return 0;
}
Nhận xét