Hướng giải của Tìm Cực Tiểu Trên Lịch Sử
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: Tìm Cực Tiểu Trên Lịch Sử
Phân tích bài toán
Bài toán yêu cầu thực hiện hai loại truy vấn trên một cấu trúc dữ liệu lưu giữ lịch sử:
- Cập nhật giá trị tại một điểm (tạo phiên bản mới).
- Tìm giá trị nhỏ nhất trong một đoạn \([l, r]\) tại một phiên bản xác định \(v\).
- Quay lại làm việc trên một phiên bản \(v\) bất kỳ (rollback).
Vì mỗi thao tác cập nhật thay đổi giá trị của một phần tử, nên chỉ có tối đa \(O(\log N)\) nút trên cây Segment Tree bị thay đổi. Thay vì nhân bản toàn bộ cây hết \(O(N)\) bộ nhớ, ta áp dụng kỹ thuật Path Copying trong Persistent Segment Tree:
- Chỉ tạo các nút mới đại diện cho các nút bị thay đổi từ gốc đến lá.
- Các nút không thay đổi sẽ được liên kết trực tiếp bằng con trỏ đến các nút tương ứng ở phiên bản trước.
Cảnh báo lỗi C++ chí mạng: Reallocation Undefined Behavior
Khi sử dụng std::vector làm bộ lưu trữ các nút cây Persistent Segment Tree, thao tác push_back có thể làm tăng dung lượng mảng động và gây tái cấp phát vùng nhớ (Reallocation). Nếu viết:
tree[id].left = update(tree[old].left, ...);
Trình biên dịch C++ có thể đánh giá địa chỉ của tree[id] trước khi chạy hàm update(). Trong khi đó, update() đệ quy thực hiện thêm phần tử vào tree thông qua push_back. Nếu xảy ra tái cấp phát bộ nhớ, địa chỉ cũ của tree[id] bị vô hiệu hóa, dẫn tới hành vi không xác định (Undefined Behavior/Crash).
Để phòng tránh triệt để, ta cần thực hiện tính toán giá trị con trỏ nút con trước thông qua biến cục bộ, sau đó mới gán lại cho nút cha:
int new_left = tree[id].left;
if (pos <= mid) {
new_left = update(new_left, lo, mid, pos, val);
}
// Sau khi đệ quy hoàn thành, mới thực hiện gán bằng chỉ số an toàn
tree[id].left = new_left;
Độ phức tạp
- Thời gian: Xây dựng cây ban đầu mất \(O(N)\). Mỗi truy vấn cập nhật và truy vấn min đoạn mất \(O(\log N)\).
- Không gian: Khởi tạo mất \(O(N)\) nút. Mỗi lần cập nhật tạo thêm \(\lceil \log_2 N \rceil + 1\) nút mới. Tổng không gian bộ nhớ là \(O(N + Q \log N)\).
Mã nguồn C++ tối ưu
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;
struct Node {
int left = -1, right = -1;
int min_val = INF;
};
vector<Node> tree;
vector<int> roots;
int build(const vector<int>& a, int lo, int hi) {
int id = tree.size();
tree.push_back(Node());
if (lo == hi) {
tree[id].min_val = a[lo];
return id;
}
int mid = lo + (hi - lo) / 2;
int left_child = build(a, lo, mid);
tree[id].left = left_child;
int right_child = build(a, mid + 1, hi);
tree[id].right = right_child;
tree[id].min_val = min(tree[tree[id].left].min_val, tree[tree[id].right].min_val);
return id;
}
int update(int old, int lo, int hi, int pos, int val) {
int id = tree.size();
tree.push_back(tree[old]);
if (lo == hi) {
tree[id].min_val = val;
return id;
}
int mid = lo + (hi - lo) / 2;
int new_left = tree[id].left;
int new_right = tree[id].right;
if (pos <= mid) {
new_left = update(new_left, lo, mid, pos, val);
} else {
new_right = update(new_right, mid + 1, hi, pos, val);
}
tree[id].left = new_left;
tree[id].right = new_right;
tree[id].min_val = min(tree[new_left].min_val, tree[new_right].min_val);
return id;
}
int query(int id, int lo, int hi, int l, int r) {
if (r < lo || hi < l) return INF;
if (l <= lo && hi <= r) return tree[id].min_val;
int mid = lo + (hi - lo) / 2;
return min(query(tree[id].left, lo, mid, l, r),
query(tree[id].right, mid + 1, hi, l, r));
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
if (!(cin >> n >> q)) return 0;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
tree.reserve(n * 4 + q * 40);
roots.push_back(build(a, 1, n));
int cur_root = roots.back();
for (int i = 0; i < q; i++) {
int type;
cin >> type;
if (type == 1) {
int pos, val;
cin >> pos >> val;
cur_root = update(cur_root, 1, n, pos, val);
roots.push_back(cur_root);
} else if (type == 2) {
int ver, l, r;
cin >> ver >> l >> r;
cout << query(roots[ver], 1, n, l, r) << "\n";
} else if (type == 3) {
int ver;
cin >> ver;
cur_root = roots[ver];
}
}
return 0;
}
Nhận xét