Mô tả các cấu trúc nền tảng
Để hiểu rõ về thuật toán này, trước hết cần nắm vững định nghĩa của hai cấu trúc dữ liệu cơ bản:
Ngăn xếp (Stack)
Ngăn xếp là một cấu trúc tuân thủ nghiêm ngặt quy tắc First In Last Out (FILO) hoặc Last In First Out (LIFO). Trong hệ thống thư viện tiêu chuẩn C++, nó được hỗ trợ bởi container `stack`.
Các thao tác chính bao gồm:
st.push(val): Chèn phần tửvalvào đỉnh ngăn xếp.st.pop(): Xóa bỏ phần tử hiện tại ở vị trí đỉnh.st.top(): Truy xuất giá trị của phần tử đỉnh mà không xóa đi.st.size(): Trả về số lượng phần tử đang tồn tại trong ngăn xếp.st.empty(): Kiểm tra trạng thái rỗng (trả vềtruenếu chứa 0 phần tử).
Hàng đợi (Queue)
Hàng đợi hoạt động theo nguyên lý First In First Out (FIFO). Thư viện chuẩn cung cấp container `queue` để mô phỏng hành vi này.
Các phương thức tương ứng gồm:
q.push(val): Thêmvalvào cuối hàng đợi.q.pop(): Lấy ra và loại bỏ phần tử ở đầu hàng đợi.q.front(): Lấy giá trị của phần tử đầu tiên.q.size()vàq.empty(): Giống như ngăn xếp, dùng để kiểm tra kích thước và trạng thái.
Khái niệm Đơn điệu (Monotonicity)
Trong ngữ cảnh tìm kiếm nhị phân hay tối ưu hóa, tính đơn điệu ám chỉ một dãy số có thể chia thành hai phần rõ rệt dựa trên điều kiện thỏa mãn. Đối với Monotonic Stack/Queue, "đơn điệu" đồng nghĩa với việc chuỗi lưu trữ bên trong phải duy trì thứ tự tăng dần, giảm dần, tăng không giảm hoặc giảm không tăng liên tục.
Nội dung chi tiết
Môn học: Monotonic Stack
Đây là kỹ thuật phổ biến giúp giải quyết các bài toán tối ưu dãy số với độ phức tạp tuyến tính $O(n)$. Mục đích chính thường là tìm cực trị (nhỏ nhất/lớn nhất) cho một khoảng mở rộng xung quanh một phần tử cụ thể.
Bài toán mẫu: Tìm giá trị lớn nhất hậu tố động
Bài toán yêu cầu xử lý một dãy số được thêm vào từng bước một. Tại mỗi thời điểm, ta cần xác định tất cả các vị trí mà tại đó giá trị là lớn nhất đối với mọi phần tử nằm phía sau nó (tính đến vị trí hiện tại).
Yêu cầu đầu vào:
- Một số nguyên
n. - Dây chuyền các phép thêm số dương vào dãy.
Kết quả mong muốn:
Tính giá trị XOR tổng hợp các chỉ số thỏa mãn điều kiện sau mỗi lần chèn.
Lộ trình giải thuật
Vấn đề cốt lõi nằm ở việc duy trì danh sách các chỉ số tiềm năng cho vị trí lớn nhất. Ta sử dụng một ngăn xếp để lưu trữ các chỉ số. Khi một số mới xuất hiện:
- Nếu số mới lớn hơn hoặc bằng số tại đỉnh ngăn xếp, thì số cũ bị loại bỏ vì số mới sẽ che phủ nó (không còn là lớn nhất hậu tố nữa).
- Liên tục thực hiện lệnh pop cho đến khi điều kiện đơn điệu được giữ nguyên.
- Số mới được push vào ngăn xếp kèm theo chỉ số của nó.
Để tính tổng XOR mà không cần duyệt lại danh sách, ta tận dụng tính chất giao hoán và phản xạ của phép XOR ($A \oplus A = 0$). Khi một chỉ số bị pop ra khỏi ngăn xếp, ta cũng thực hiện XOR nó với bộ tích lũy kết quả.
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1000005;
int n_limit;
unsigned long long current_val;
unsigned long long xor_result_accumulator;
// Sử dụng mảng làm stack để tối ưu bộ nhớ và tốc độ
int monotonic_stack[MAX_N];
int top_idx = 0;
inline void fast_io() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
int main() {
fast_io();
if (!(cin >> n_limit)) return 0;
for (int i = 1; i <= n_limit; ++i) {
cin >> current_val;
// Duy trì tính đơn điệu giảm dần từ dưới lên
// Loại bỏ các giá trị nhỏ hơn giá trị hiện tại
while (top_idx > 0 && monotonic_stack[top_idx - 1] <= current_val) {
// Cập nhật kết quả XOR khi phần tử bị loại
xor_result_accumulator ^= monotonic_stack[top_idx - 1];
--top_idx;
}
// Lưu trữ chỉ số và giá trị (chỉ cần lưu chỉ số vì so sánh qua mảng global)
static unsigned long long val_history[MAX_N];
val_history[i] = current_val;
monotonic_stack[top_idx++] = i;
// Cập nhật kết quả với chỉ số hiện tại
xor_result_accumulator ^= i;
cout << xor_result_accumulator << "\n";
}
return 0;
}
Vận dụng nâng cao: Bài toán hình chữ nhật lớn nhất
Ứng dụng mở rộng của Monotonic Stack là giải quyết bài toán diện tích hình chữ nhật lớn nhất trong ma trận (dạng Histogram 2 chiều).
Xử lý tiền xử lý:
Trước tiên, tính toán mảng chiều cao height[i][j] biểu thị độ dài đoạn liên tiếp ký tự 'F' đi lên kể từ dòng i. Nếu ô đó là 'R' thì chiều cao bằng 0.
for (int row = 1; row <= n; ++row) {
for (int col = 1; col <= m; ++col) {
char type;
cin >> type;
if (type == 'F') {
height[row][col] = height[row-1][col] + 1;
} else {
height[row][col] = 0;
}
}
}
Xử lý từng hàng:
Với mỗi hàng coi như một đồ thị cột (histogram), bài toán chuyển về tìm hình chữ nhật lớn nhất. Ta cần tìm biên giới trái và phải xa nhất cho mỗi cột sao cho chiều cao vẫn lớn hơn hoặc bằng chiều cao của cột gốc.
long long calculate_largest_rectangle(int rows, int cols) {
vector<int> left_bound(cols + 1), right_bound(cols + 1);
// Duyệt ngược lại để tìm ranh giới trái
for (int j = 1; j <= cols; ++j) {
int idx = j;
while (idx > 0 && heights[idx - 1] >= heights[j]) {
idx = left_bound[idx - 1] + 1; // Tuyến tính hóa bước nhảy
}
left_bound[j] = idx;
}
// Duyệt thuận để tìm ranh giới phải
for (int j = cols; j >= 1; --j) {
int idx = j;
while (idx < cols && heights[idx + 1] >= heights[j]) {
idx = right_bound[idx + 1] - 1;
}
right_bound[j] = idx;
}
long long max_area = 0;
for (int j = 1; j <= cols; ++j) {
max_area = max(max_area, (long long)heights[j] * (right_bound[j] - left_bound[j] + 1));
}
return max_area;
}
Lưu ý: Để đạt hiệu suất tốt nhất, người ta thường thay thế việc tìm biên trái/phải bằng việc chạy một vòng lặp duy nhất với Stack đơn điệu thay vì dùng Vector như minh họa ở trên.
Ứng dụng trong Quy hoạch động (DP)
Monotonic Stack còn được sử dụng để tối ưu hóa các công thức chuyển tiếp trong Quy hoạch động, giảm độ phức tạp thời gian xuống mức phù hợp cho dữ liệu lớn. Tuy nhiên, cách áp dụng cụ thể phụ thuộc vào từng bài toán.
Giới thiệu về Monotonic Queue
Thay vì lưu trữ phần tử tại đỉnh, Monotonic Queue lưu trữ thông tin hữu ích tại hai đầu. Cấu trúc này thường xuyên được dùng để giải quyết bài toán Sliding Window (Cửa sổ trượt), nơi ta cần tìm max/min của một cửa sổ di chuyển trên mảng.