Thông thường khi giải quyết các bài tập yêu cầu: Đưa trạng thái hiện tại về trạng thái trước khi thực hiện truy vấn thứ \(k\), mọi người thường hay dùng các cấu trúc dữ liệu Persistent để giải. Tuy nhiên, một số bài cho phép chúng ta xử lí offline, vậy ta có thể sử dụng phương pháp này để code cho đơn giản.
Thuật toán
Đọc hết các truy vấn trước khi giải. Với mỗi truy vấn thứ \(i\), nếu nó không là truy vấn đưa về trạng thái thứ \(k\), nối nó đến đỉnh thứ \(i-1\); ngược lại, nối nó đến đỉnh \(k\). Khi này đồ thị chúng ta nhận được sẽ là một cây (do mỗi đỉnh chỉ nối đến một đỉnh duy nhất nằm ở đằng trước nó).
Sau khi đã đọc hết các truy vấn, ta sẽ DFS từ đỉnh số \(0\) để giải bài toán.
void dfs (int u) {
trả lời truy vấn u nếu cần
for (truy vấn v kề u) {
if (truy vấn v không phải là truy vấn đưa về trước) {
thực hiện thay đổi theo truy vấn v
}
dfs(v);
if (truy vấn v không phải là truy vấn đưa về trước) {
xoá các hành động vừa thực hiện
}
}
}
Độ phức tạp: \(O(q \times n)\), trong đó \(n\) là thời gian thực hiện một truy vấn.
Bài tập áp dụng:
- Codeforces 707D
-
Hai bài trên là một áp dụng cơ bản của dạng bài này, các bạn chỉ cần chép nguyên hàm DFS vào, mỗi truy vấn làm y như đề bảo là AC.
-
Dựng cây Segment Tree; mỗi nút ở Segment Tree lưu thông tin: số ngoặc mở chưa được ghép với đứa nào trong đoạn \((i,j)\), tương tự với số ngoặc đóng.
struct Node { int open, close; };Như vậy khi ghép 2 nút con \(L\), \(R\) vào với nút cha ta sẽ làm như sau:
Node operator + (Node L, Node R) { Node ans = {L.open + R.open, L.close + R.close}; int will_be_match = min(L.open, R.close); ans.open -= will_be_match; ans.close -= will_be_match; return ans; }Với các thông tin như vậy ta có thể dễ dàng suy ra trọng số của đoạn \([L,R]\).
Đến đây ta đã giải quyết được các truy vấn \(1\) và \(2\) trong \(O(logN)\). Còn truy vấn \(3\), bạn chỉ cần chép hàm DFS như trên là AC.
- Query-Max 4 - LQDOJ