Hướng dẫn giải của Truy vấn dãy ngoặc
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
, , ,
Editorial for qbrack: Truy vấn dãy ngoặc
Hiểu bài toán
Bài toán yêu cầu xử lý một xâu chỉ gồm các ký tự '(' và ')' với hai loại truy vấn: cập nhật (đảo ngược ký tự tại một vị trí) và truy vấn (kiểm tra xem xâu con từ i đến j có phải là một dãy ngoặc đúng hay không). Dãy ngoặc đúng được định nghĩa theo quy tắc chuẩn: có thể rỗng, (A) nếu A đúng, hoặc AB nếu A và B đúng. Với N, M lên tới 10^5, lời giải toán tử (O(N)) cho mỗi truy vấn sẽ không khả thi, cần một cấu trúc dữ liệu hiệu quả hơn.
Các cách tiếp cận
Cách Brute Force (Toán tử)
#include <iostream>
#include <string>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
string s;
cin >> s;
while (m--) {
int type;
cin >> type;
if (type == 0) {
int i;
cin >> i;
s[i-1] = (s[i-1] == '(' ? ')' : '(');
} else {
int l, r;
cin >> l >> r;
int balance = 0;
bool valid = true;
for (int k = l - 1; k < r; k++) {
if (s[k] == '(') balance++;
else balance--;
if (balance < 0) {
valid = false;
break;
}
}
if (balance != 0) valid = false;
cout << (valid ? '1' : '0');
}
}
return 0;
}
- Time Complexity: O(M * N)
- Space Complexity: O(N)
Giải pháp này sử dụng trực tiếp định nghĩa của dãy ngoặc đúng. Với mỗi truy vấn type 1, ta duyệt qua xâu con từ i đến j, dùng biến 'balance' để đếm số ngoặc mở trừ đi số ngoặc đóng. Nếu 'balance' bao giờ cũng không âm và cuối cùng bằng 0 thì xâu con đó đúng. Cập nhật chỉ cần thay đổi ký tự tại vị trí. Tuy nhiên, độ phức tạp O(M*N) sẽ bị Time Limit Exceeded với N, M = 10^5.
Cách Segment Tree (Quản lý cặp ngoặc)
#include <bits/stdc++.h>
using namespace std;
struct Node {
int open; // Số ngoặc mở dư
int close; // Số ngoặc đóng dư
};
string s;
vector<Node> st;
// Hàm gộp hai node
Node mergeNode(const Node &L, const Node &R) {
Node res;
int match = min(L.open, R.close); // Số cặp ngoặc có thể ghép
res.open = L.open + R.open - match;
res.close = L.close + R.close - match;
return res;
}
void build(int id, int l, int r) {
if (l == r) {
if (s[l] == '(') st[id] = {1, 0};
else st[id] = {0, 1};
return;
}
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
st[id] = mergeNode(st[id * 2], st[id * 2 + 1]);
}
void update(int id, int l, int r, int pos) {
if (l == r) {
// Đảo ngược giá trị
if (s[l] == '(') {
s[l] = ')';
st[id] = {0, 1};
} else {
s[l] = '(';
st[id] = {1, 0};
}
return;
}
int mid = (l + r) / 2;
if (pos <= mid) update(id * 2, l, mid, pos);
else update(id * 2 + 1, mid + 1, r, pos);
st[id] = mergeNode(st[id * 2], st[id * 2 + 1]);
}
Node query(int id, int l, int r, int u, int v) {
if (v < l || r < u) return {0, 0};
if (u <= l && r <= v) return st[id];
int mid = (l + r) / 2;
Node left = query(id * 2, l, mid, u, v);
Node right = query(id * 2 + 1, mid + 1, r, u, v);
return mergeNode(left, right);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
cin >> s;
st.resize(4 * n);
build(1, 0, n - 1);
while (m--) {
int type;
cin >> type;
if (type == 0) {
int i;
cin >> i;
update(1, 0, n - 1, i - 1);
} else {
int l, r;
cin >> l >> r;
Node res = query(1, 0, n - 1, l - 1, r - 1);
// Một dãy ngoặc đúng phải có số ngoặc mở dư = 0 và số ngoặc đóng dư = 0
if (res.open == 0 && res.close == 0) cout << '1';
else cout << '0';
}
}
return 0;
}
- Time Complexity: O(N) để build cây, O(log N) cho mỗi truy vấn cập nhật và truy vấn.
- Space Complexity: O(N)
Sử dụng Segment Tree để lưu trữ thông tin về các đoạn con. Mỗi node trong cây lưu số lượng ngoặc mở dư ('open') và ngoặc đóng dư ('close'). Hàm gộp (merge) của Segment Tree hoạt động như sau: khi ghép đoạn A và B, số cặp ngoặc mới được tạo ra bằng min(open của A, close của B). Sau đó ta trừ đi số lượng đã ghép được để tính số dư cho đoạn gộp. Nếu kết quả truy vấn cho đoạn [i, j] có cả 'open' và 'close' bằng 0, thì đoạn này là dãy ngoặc đúng. Cập nhật chỉ cần thay đổi lá và Propagate lên cha.
Cách Segment Tree (Tổng tiền tố)
// Lưu ý: Đây là một biến thể khác của Segment Tree, dùng tổng tiền tố
// Code minh họa logic
#include <bits/stdc++.h>
using namespace std;
vector<int> st;
int n;
void build(const string& s, int id, int l, int r) {
if (l == r) {
st[id] = (s[l] == '(' ? 1 : -1);
return;
}
int mid = (l + r) / 2;
build(s, id * 2, l, mid);
build(s, id * 2 + 1, mid + 1, r);
st[id] = st[id * 2] + st[id * 2 + 1];
}
void update(int id, int l, int r, int pos, int val) {
if (l == r) {
st[id] = val;
return;
}
int mid = (l + r) / 2;
if (pos <= mid) update(id * 2, l, mid, pos, val);
else update(id * 2 + 1, mid + 1, r, pos, val);
st[id] = st[id * 2] + st[id * 2 + 1];
}
int querySum(int id, int l, int r, int u, int v) {
if (v < l || r < u) return 0;
if (u <= l && r <= v) return st[id];
int mid = (l + r) / 2;
return querySum(id * 2, l, mid, u, v) + querySum(id * 2 + 1, mid + 1, r, u, v);
}
// Hàm tìm chỉ số đầu tiên trong đoạn [L, R] có tổng tiền tố < min_val
// Cần Segment Tree hoặc Mảng cộng tiền tố + Binary Lifting để tìm min prefix
class SegmentTreeMin {
// ... (Code đầy đủ cho Segment Tree Min và Max)
};
int main() {
// ... (Logic main)
return 0;
}
- Time Complexity: O(log N)
- Space Complexity: O(N)
Phương pháp này sử dụng tổng tiền tố. Xâu con từ i đến j là ngoặc đúng nếu:
- Tổng của xâu con đó bằng 0 (số lượng '(' bằng ')').
- Tổng tiền tố tích lũy tại mọi điểm bên trong đoạn [i, j] không bao giờ giảm quá tổng tiền tố tại i-1. Để kiểm tra điều kiện 2 hiệu quả, ta cần tìm giá trị nhỏ nhất của tổng tiền tố trong đoạn [i, j]. Nếu MinPrefix(i, j) >= Prefix[i-1] và Sum(i, j) == 0 thì đáp án là 1. Điều này có thể thực hiện bằng cách dùng Segment Tree lưu tổng và Segment Tree lưu Min/Max của tổng tiền tố.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(M * N) | O(N) | Brute Force (Toán tử) |
| 2 | O(N) để build cây, O(log N) cho mỗi truy vấn cập nhật và truy vấn. | O(N) | Segment Tree (Quản lý cặp ngoặc) |
| 3 | O(log N) | O(N) | Segment Tree (Tổng tiền tố) |
Bài học kinh nghiệm
- Dãy ngoặc đúng có tính chất kết hợp: khi ghép hai dãy ngoặc đúng (hoặc có thể trở thành đúng), ta chỉ cần quan tâm đến số ngoặc mở thừa và số ngoặc đóng thừa của từng đoạn.
- Bài toán có thể chuyển đổi thành bài toán tìm Min/Max của tổng tiền tố, nhưng phương pháp quản lý số ngoặc dư (open/close) là trực quan và phổ biến hơn trong cộng đồng lập trình thi đấu cho bài toán này.
Lỗi thường gặp
- Lỗi chỉ số (Off-by-one error): Xâu được đánh số từ 1 đến N nhưng code C++ thường xử lý từ 0 đến N-1. Cần chuyển đổi chỉ số đầu vào/đầu ra một cách cẩn thận.
- Quên kiểm tra điều kiện tổng bằng 0: Một đoạn có thể có tổng tiền tố dương tại mọi điểm nhưng nếu tổng cuối cùng không bằng 0 thì nó vẫn chưa phải là dãy ngoặc đúng (ví dụ: '(()').
- Hiệu năng của Segment Tree: Cần tối ưu I/O (dùng iosbase::syncwith_stdio(false); cin.tie(NULL);) và đệ quy cây (nên dùng đệ quy cây hoặc mảng 1 chiều) để tránh tràn stack hoặc TLE.
Bình luận