Hướng dẫn giải của Dãy ngoặc đúng
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu xử lý một xâu ngoặc S và các truy vấn trên xâu đó. Có ba loại truy vấn: C i (đảo ngược ký tự tại vị trí i), Q i j (tính trọng số của xâu con S[i..j]), U k (quay lại trạng thái xâu S sau khi thực hiện lệnh thứ k). Trọng số của một xâu được định nghĩa là số lượng ký tự cần thêm vào để biến nó thành xâu ngoặc đúng.
Về mặt bản chất, nếu quy đổi '(' thành +1 và ')' thành -1, trọng số của một xâu con liên tiếp bằng tổng số lượng dấu ngoặc đơn cần thêm vào. Cụ thể, nếu ta có tổng tiền tố (prefix sum) nhỏ nhất là minprefix, thì cần thêm |minprefix| dấu '(' vào đầu (nếu minprefix < 0). Sau khi thêm, tổng của xâu sẽ tăng lên |minprefix|, chênh lệch so với tổng ban đầu là |minprefix|, và để tổng cuối cùng về 0, ta cần thêm |minprefix| dấu ')' vào cuối. Vậy trọng số là 2 * |min_prefix|.
Tuy nhiên, có một trường hợp đặc biệt: nếu tổng của xâu con (tổng cuối cùng) lớn hơn |minprefix| (tức tổng dương), thì sau khi thêm |minprefix| dấu '(' vào đầu, tổng sẽ là tổngbanđầu + |minprefix|. Nếu giá trị này dương, ta cần thêm bấy nhiêu dấu ')' vào cuối. Đáp án chính xác là: |minprefix| + max(0, (tổngcuối - minprefix)).
Bài toán này cần xử lý các thay đổi điểm (point update) và truy vấn khoảng (range query) trên cấu trúc dữ liệu động, cùng với đó là khả năng rollback (quay lui) về các phiên bản trước đó.
Các cách tiếp cận
Cách Persistent Segment Tree (Cây phân đoạn bất biến)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
struct Node{
int l=0,r=0;
int open=0,close=0;
};
vector<Node> seg;
string s;
pii merge_val(pii A,pii B){
int t=min(A.first,B.second);
return {A.first+B.first-t,A.second+B.second-t};
}
int clone_node(int idx){
seg.push_back(seg[idx]);
return seg.size()-1;
}
int build(int l,int r){
seg.emplace_back();
int node=seg.size()-1;
if(l==r){
if(s[l-1]=='(') seg[node].open=1;
else seg[node].close=1;
return node;
}
int mid=(l+r)/2;
seg[node].l=build(l,mid);
seg[node].r=build(mid+1,r);
pii L={seg[seg[node].l].open,seg[seg[node].l].close};
pii R={seg[seg[node].r].open,seg[seg[node].r].close};
pii M=merge_val(L,R);
seg[node].open=M.first;
seg[node].close=M.second;
return node;
}
int update(int pre,int l,int r,int pos){
int cur=clone_node(pre);
if(l==r){
if(seg[cur].open) {seg[cur].open=0; seg[cur].close=1;}
else {seg[cur].open=1; seg[cur].close=0;}
return cur;
}
int mid=(l+r)/2;
if(pos<=mid) seg[cur].l=update(seg[pre].l,l,mid,pos);
else seg[cur].r=update(seg[pre].r,mid+1,r,pos);
pii L={seg[seg[cur].l].open,seg[seg[cur].l].close};
pii R={seg[seg[cur].r].open,seg[seg[cur].r].close};
pii M=merge_val(L,R);
seg[cur].open=M.first;
seg[cur].close=M.second;
return cur;
}
pii query(int node,int l,int r,int ql,int qr){
if(ql<=l && r<=qr) return {seg[node].open,seg[node].close};
int mid=(l+r)/2;
if(qr<=mid) return query(seg[node].l,l,mid,ql,qr);
if(ql>mid) return query(seg[node].r,mid+1,r,ql,qr);
return merge_val(query(seg[node].l,l,mid,ql,qr), query(seg[node].r,mid+1,r,ql,qr));
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>s;
int n=s.length();
int m; cin>>m;
seg.reserve(40000000);
vector<int> roots;
roots.push_back(build(1,n));
for(int k=1; k<=m; ++k){
char type; cin>>type;
if(type=='C'){
int i; cin>>i;
int next_root = update(roots.back(), 1, n, i);
roots.push_back(next_root);
} else if(type=='Q'){
int i, j; cin>>i>>j;
pii res = query(roots.back(), 1, n, i, j);
cout << res.first << '\n';
} else {
int k_idx; cin>>k_idx;
roots.push_back(roots[k_idx]);
}
}
return 0;
}
- Time Complexity: O(m log n)
- Space Complexity: O(m log n)
Cách tiếp cận này sử dụng cây phân đoạn bất biến (Persistent Segment Tree). Mỗi node lưu số lượng dấu ngoặc mở và đóng 'cần thiết' sau khi đã khớp với nhau (theo logic merge_val). Đây là một cách tính tổng quát cho độ dài xâu ngoặc đúng bằng cách tối ưu hóa số lượng cặp ngoặc đúng có thể tạo thành.
- Cấu trúc dữ liệu: Mỗi node cây phân đoạn lưu
open(số ngoặc mở còn dư) vàclose(số ngoặc đóng còn dư). Hàm gộp (merge) kết quả hai xâu A và B:open = A.open + B.open - min(A.open, B.close)vàclose = A.close + B.close - min(A.open, B.close). Trả về trọng số bằngopen. - Xây dựng: Cây được build ban đầu từ xâu S. Cập nhật (C i) tạo một phiên bản mới của cây bằng cách clone đường đi từ root cũ và thay đổi giá trị tại leaf. Truy vấn (Q i j) lấy kết quả từ phiên bản hiện tại. Lệnh U k đơn giản chỉ là trỏ root hiện tại về root của phiên bản thứ k.
- Tại sao hiệu quả: Persistent tree cho phép lưu trữ tất cả các phiên bản của cấu trúc dữ liệu với chi phí không gian chấp nhận được, xử lý được cả truy vấn U một cách dễ dàng.
Cách Segment Tree with Rollback (Offline)
#include <bits/stdc++.h>
using namespace std;
// ----- Segment tree with rollback (store sum and minPrefix) -----
struct STNode { int sum, mn; };
struct Change { int idx; STNode prev; };
int N, M;
string S;
vector<STNode> seg; // size ~ 4*N
vector<int> val; // current +1/-1 at each position
vector<Change> changes; // rollback stack
vector<int> valFlip; // positions flipped in current DFS path
inline STNode mergeNode(const STNode& L, const STNode& R){
return { L.sum + R.sum, min(L.mn, L.sum + R.mn) };
}
void build(int p, int l, int r){
if(l == r){
int v = (S[l-1] == '(') ? +1 : -1;
seg[p] = { v, min(0, v) };
return;
}
int m = (l + r) >> 1;
build(p<<1, l, m);
build(p<<1|1, m+1, r);
seg[p] = mergeNode(seg[p<<1], seg[p<<1|1]);
}
inline void setNode(int p, const STNode& nv){
changes.push_back({p, seg[p]});
seg[p] = nv;
}
void point_set(int p, int l, int r, int pos, int v){
if(l == r){
setNode(p, {v, min(0, v)});
return;
}
int m = (l + r) >> 1;
if(pos <= m) point_set(p<<1, l, m, pos, v);
else point_set(p<<1|1, m+1, r, pos, v);
setNode(p, mergeNode(seg[p<<1], seg[p<<1|1]));
}
STNode query(int p, int l, int r, int ql, int qr){
if(ql <= l && r <= qr) return seg[p];
int m = (l + r) >> 1;
if(qr <= m) return query(p<<1, l, m, ql, qr);
if(ql > m) return query(p<<1|1, m+1, r, ql, qr);
return mergeNode(query(p<<1, l, m, ql, qr), query(p<<1|1, m+1, r, ql, qr));
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> S; N = S.length();
cin >> M;
seg.resize(4 * N + 10);
val.resize(N + 1);
build(1, 1, N);
for(int k = 1; k <= M; ++k){
char type; cin >> type;
if(type == 'C'){
int i; cin >> i;
int old_v = val[i];
int new_v = -old_v;
point_set(1, 1, N, i, new_v);
val[i] = new_v;
} else if(type == 'Q'){
int i, j; cin >> i >> j;
STNode res = query(1, 1, N, i, j);
int ans = -res.mn + max(0, res.sum + res.mn);
cout << ans << '\n';
} else {
int k_idx; cin >> k_idx;
// Rollback to state after command k_idx
// This requires saving state history
// Since U k refers to command index, not number of changes,
// we need to track how many changes to rollback.
// (Simplified logic: In this approach, we need a history of change counts)
// For this snippet, assume we have a way to know `changes_to_rollback`.
// In actual implementation, we'd store `change_count[k]`.
}
}
return 0;
}
- Time Complexity: O(m log n)
- Space Complexity: O(n + m)
Sử dụng Segment Tree thường kết hợp với cơ chế Rollback (hoặc Undo). Cấu trúc cây lưu trữ tổng và tổng tiền tố tối thiểu (min prefix).
- Rollback: Thay vì Persistent Tree lưu nhiều phiên bản, chúng ta lưu các thay đổi (changes) vào một stack. Khi cần rollback, ta lùi stack về trạng thái trước đó. Tuy nhiên, bài toán yêu cầu rollback về lệnh thứ k, không phải rollback từng bước một cách đơn giản. Do đó, ta cần lưu số lượng thay đổi (stack size) tại mỗi thời điểm.
- Logic tính đáp án: Với một khoảng [i, j], ta tính tổng (sum) và min tiền tố (mn). Trọng số = |mn| + (sum - min(0, mn)).
- Hạn chế: Cách này phức tạp trong việc quản lý state history để rollback đúng theo chỉ số lệnh. Persistent Tree (Approach 1) giải quyết vấn đề này tự nhiên và an toàn hơn.
Cách Simulation với Order Statistic Tree (TLE)
// Pseudocode for illustration
#include <iostream>
#include <set>
using namespace std;
struct Event { int type; int pos; int prev_val; };
vector<Event> history;
string s;
int main() {
// Read s, m
// Loop queries:
// if C i: save {i, s[i]}, s[i] = flip(s[i])
// if Q i j: naive scan O(n)
// if U k: restore states from history[k]...current
// Complexity: O(m * n) -> TLE
}
- Time Complexity: O(m * n)
- Space Complexity: O(n + m)
Một cách tiếp cận đơn giản nhất là mô phỏng y chang yêu cầu:
- Lưu trữ xâu S.
- Với mỗi lệnh C: Thay đổi ký tự tại vị trí i, lưu lại thay đổi vào lịch sử.
- Với mỗi lệnh Q: Duyệt trực tiếp từ i đến j, tính toán trọng số (có thể dùng stack ảo hoặc đếm tổng tiền tố).
- Với mỗi lệnh U: Khôi phục lại xâu S về trạng thái trước lệnh thứ k (cần lưu trữ history chi tiết).
Cách này chỉ khả thi với dữ liệu nhỏ. Với n, m lên tới 10^6, thời gian chạy sẽ quá giới hạn cho phép.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(m log n) | O(m log n) | Persistent Segment Tree (Cây phân đoạn bất biến) |
| 2 | O(m log n) | O(n + m) | Segment Tree with Rollback (Offline) |
| 3 | O(m * n) | O(n + m) | Simulation với Order Statistic Tree (TLE) |
Bài học kinh nghiệm
- Bài toán có thể được chuyển đổi thành bài toán tính toán tổng tiền tố (prefix sum) và tổng tiền tố nhỏ nhất (min prefix sum) trên đoạn [i, j].
- Công thức tính trọng số: |minprefix| + max(0, (totalsum - min(0, min_prefix))).
- Persistent Segment Tree là cấu trúc dữ liệu phù hợp nhất cho các bài toán yêu cầu xử lý nhiều phiên bản của một mảng với các thao tác update và query trên các phiên bản đó.
Lỗi thường gặp
- Sai công thức tính trọng số: Cần xử lý đúng các trường hợp tổng dương và âm.
- Quản lý bộ nhớ cho Persistent Tree: Nếu không phân bổ đủ bộ nhớ cho nodes, chương trình sẽ bị lỗi memory limit exceeded hoặc segmentation fault.
- Lỗi logic rollback: Khi dùng Segment Tree thường, việc track history để rollback về đúng phiên bản theo chỉ số lệnh U k là khó khăn, dễ导致 sai state.
Bình luận