Khái Niệm Cơ Bản
Thuật toán Mo là một phương pháp tiếp cận được thiết kế để giải quyết hiệu quả các bài toán liên quan đến truy vấn đoạn trên dãy số. Kỹ thuật này dựa trên nguyên lý phân khối và thường yêu cầu dữ liệu đầu vào phải ở dạng offline (xử lý tất cả truy vấn sau khi đã biết toàn bộ thông tin). Nếu bài toán buộc phải trả lời ngay lập tức (online), phương pháp này sẽ không thể áp dụng.
Mục tiêu cốt lõi của thuật toán Mo là tận dụng khả năng chuyển đổi trạng thái nhanh chóng giữa hai đoạn lân cận. Cụ thể, nếu chúng ta đã có kết quả cho đoạn $[l, r]$, việc mở rộng hoặc thu hẹp sang $[l, r+1]$, $[l+1, r]$, $[l, r-1]$ hay $[l-1, r]$ phải thực hiện trong thời gian $O(k)$, thường là $k=1$. Khi đó, tổng độ phức tạp thời gian để xử lý $q$ truy vấn trên dãy độ dài $n$ sẽ đạt mức $O(n\sqrt{q})$.
Nguyên Lý Sắp Xếp Và Độ Phức Tạp
Nếu duy trì trạng thái hiện tại và di chuyển con trỏ theo thứ tự truy vấn ban đầu, lượng phép tính có thể tăng vọt vượt quá giới hạn cho phép. Để giảm thiểu khoảng cách di chuyển của các con trỏ trái và phải, chúng ta cần sắp xếp lại thứ tự xử lý các truy vấn. Cách sắp xếp đơn giản theo $l$ rồi đến $r$ thường chưa đủ hiệu quả.
Giải pháp tối ưu sử dụng kỹ thuật phân khối. Giả sử độ dài dãy là $n$ và kích thước khối là $B$. Mỗi vị trí $i$ sẽ thuộc về khối $block\_i = \lfloor i / B \rfloor$. Chúng ta sẽ sắp xếp các truy vấn dựa trên tiêu chí:
- Theo $block\_l$ tăng dần.
- Sau đó theo $block\_r$ tăng dần (hoặc tùy biến).
Khi chọn $B = \frac{n}{\sqrt{q}}$, tổng số lần dịch chuyển con trỏ trái và phải được cân bằng để tối thiểu hóa độ phức tạp. Tuy nhiên, trong thực tế với $q \approx n$, người ta thường chọn $B \approx \sqrt{n}$ để đạt độ phức tạp trung bình $O((n + q)\sqrt{n})$, đủ sức xử lý các dữ liệu có quy mô $10^5$ trở lên.
Kỹ Thuật Tối Ưu Chẵn Lẻ (Odd-Even Optimization)
Một nhược điểm của việc sắp xếp khối đơn thuần là khi $block\_l$ thay đổi, con trỏ $r$ có thể phải quay lại từ cuối mảng về đầu mảng, gây lãng phí thao tác. Để khắc phục, ta áp dụng sắp xếp chẵn lẻ:
- Nếu $block\_l$ là số chẵn, sắp xếp $r$ tăng dần.
- Nếu $block\_l$ là số lẻ, sắp xếp $r$ giảm dần.
Kỹ thuật này giúp con trỏ $r$ luôn di chuyển theo một hướng thuận tiện hơn trong cùng một khối, giảm đáng kể lượng công việc thực thi và cải thiện hằng số tốc độ chạy chương trình.
Cấu Trúc Cài Đặt Tổng Quát
Phần khung chính của thuật toán bao gồm việc đọc dữ liệu, sắp xếp truy vấn và duy trì trạng thái thông qua hai hàm hỗ trợ chính: thêm phần tử mới vào vùng xét và loại bỏ phần tử khỏi vùng xét.
Dưới đây là mẫu khung sườn chung có thể tái sử dụng:
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
int freq[MAXN]; // Mảng đếm tần suất
long long currentAnswer = 0; // Biến lưu kết quả tạm thời
int blockSize;
struct Query {
int left, right, id, blockIndex;
};
// Hàm so sánh theo thứ tự Mo
bool compareQueries(const Query& a, const Query& b) {
if (a.blockIndex != b.blockIndex)
return a.blockIndex < b.blockIndex;
// Tối ưu chẵn lẻ
return (a.blockIndex % 2 == 0) ? (a.right < b.right) : (a.right > b.right);
}
// Hàm cập nhật khi thêm chỉ số p vào khoảng hiện tại
void addElement(int p, const vector<int>& arr) {
// Logic cụ thể phụ thuộc vào yêu cầu bài toán
}
// Hàm cập nhật khi loại bỏ chỉ số p khỏi khoảng hiện tại
void removeElement(int p, const vector<int>& arr) {
// Logic cụ thể phụ thuộc vào yêu cầu bài toán
}
void solve() {
int n, qCount;
cin >> n >> qCount;
vector<int> data(n + 1);
for (int i = 1; i <= n; ++i) cin >> data[i];
blockSize = static_cast<int>(n / sqrt(qCount));
if (blockSize == 0) blockSize = 1;
vector<Query> queries(qCount);
for (int i = 0; i < qCount; ++i) {
cin >> queries[i].left >> queries[i].right;
queries[i].id = i;
queries[i].blockIndex = queries[i].left / blockSize;
}
sort(queries.begin(), queries.end(), compareQueries);
vector<long long> results(qCount);
int curL = 1, curR = 0;
for (const auto& qry : queries) {
while (curL > qry.left) {
curL--;
addElement(curL, data);
}
while (curR < qry.right) {
curR++;
addElement(curR, data);
}
while (curL < qry.left) {
removeElement(curL, data);
curL++;
}
while (curR > qry.right) {
removeElement(curR, data);
curR--;
}
results[qry.id] = currentAnswer;
}
for (long long res : results) cout << res << "\n";
}Ứng Dụng Vào Các Bài Toán Cụ Thể
Để minh họa cách linh hoạt trong việc xây dựng hàm `addElement` và `removeElement`, dưới đây là phân tích một số trường hợp phổ biến.
1. Đếm Số Phần Tử Khác Nhau Trong Khoảng
Vấn đề yêu cầu xác định số lượng giá trị độc nhất trong đoạn $[l, r]$. Ta duy trì một mảng đếm tần suất. Khi thêm số $x$ mà tần suất đang bằng 0 thì tăng kết quả.
void handleInsertion(int idx, const vector<int>& array) {
int val = array[idx];
if (freq[val] == 0) {
currentAnswer++;
}
freq[val]++;
}
void handleDeletion(int idx, const vector<int>& array) {
int val = array[idx];
freq[val]--;
if (freq[val] == 0) {
currentAnswer--;
}
}2. Tính Tích Của Tần Suất Bình Phương Với Giá Trị
Bài toán yêu cầu tính tổng $\sum c_x^2 \times x$, trong đó $c_x$ là số lần xuất hiện của giá trị $x$. Khi thêm/xóa phần tử, ta trừ đi đóng góp cũ của giá trị đó trước khi cập nhật biến đếm, rồi cộng dồn giá trị mới.
void updateAdd(int pos, const vector<int>& arr) {
int val = arr[pos];
currentAnswer -= 1LL * freq[val] * freq[val] * val;
freq[val]++;
currentAnswer += 1LL * freq[val] * freq[val] * val;
}
void updateRemove(int pos, const vector<int>& arr) {
int val = arr[pos];
currentAnswer -= 1LL * freq[val] * freq[val] * val;
freq[val]--;
currentAnswer += 1LL * freq[val] * freq[val] * val;
}3. Truy Vấn Tổng XOR Của Đoạn Con
Sử dụng tiền tố XOR, giá trị XOR của đoạn $[l, r]$ tương đương với prefix[r] ^ prefix[l-1]. Khi di chuyển cửa sổ, ta kiểm tra xem trong khoảng hiện tại có tồn tại bao nhiêu giá trị prefix XOR thỏa mãn điều kiện đối với tham số $k$ đã cho.
void moveAdd(int index, const vector<int>& prefixArr, int targetK) {
int currentPrefix = prefixArr[index];
int needed = currentPrefix ^ targetK;
currentAnswer += countMap[needed];
countMap[currentPrefix]++;
}
void moveRemove(int index, const vector<int>& prefixArr, int targetK) {
int currentPrefix = prefixArr[index];
countMap[currentPrefix]--;
int needed = currentPrefix ^ targetK;
currentAnswer -= countMap[needed];
}4. Tìm Mex (Minimum Excluded Value)
Với yêu cầu tìm số tự nhiên nhỏ nhất không xuất hiện trong đoạn, thay vì cập nhật trực tiếp kết quả mỗi lần chuyển, ta chỉ duy trì mảng đếm tần suất. Khi cần lấy đáp án, quét từ 0 đến khi gặp số có tần suất bằng 0. Để tối ưu, có thể dùng `bitset` đánh dấu sự xuất hiện của các số để tìm vị trí trống nhanh hơn.
bitSet presenceBits; // Đánh dấu số đã xuất hiện (1 là đã xuất hiện)
void insertBit(int value) {
freq[value]++;
if (freq[value] == 1) presenceBits.set(value, true);
}
void eraseBit(int value) {
freq[value]--;
if (freq[value] == 0) presenceBits.set(value, false);
}
// Sau khi chạy vòng lặp Mo, tìm mex bằng cách duyệt bitset hoặc tìm bit đầu tiên là 0
int findMex() {
int candidate = 0;
while (presenceBits.test(candidate)) candidate++;
return candidate;
}5. Thống Kê Tần Xuất Cực Đại
Bài toán yêu cầu đếm số lượng phần tử xuất hiện đúng 2 lần. Logic sẽ kiểm tra điều kiện biên của biến đếm tần suất trước khi thực hiện tăng/giảm.
void trackFrequency(int val) {
if (freq[val] == 2) totalTwoCounts--;
freq[val]++;
if (freq[val] == 2) totalTwoCounts++;
}
// Tương tự với hàm xóa nhưng đảo ngược logic điều kiện