Chia căn – Thuật toán MO

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int int64_t
#define pii pair<int,int>
const int mx = 1e5 + 5;
const int mod = 1e9 + 7;
const int inf = 1e18;
const int blockn = sqrt(mx);
int n;
int cnt[mx / blockn + 5][mx];
int a[mx];
int truyvan(int l, int r, int x){
    int blockL = l / blockn;
    int blockR = r / blockn;
    if (blockL >= blockR)
        return count(a + l, a + r + 1, x);
    int sum = 0;
    for (int i = blockL; i < blockR; ++i)
        sum += cnt[i][x];      
    for (int i = l; i < blockL * blockn; ++i)
        if (a[i] == x) ++sum;       
    for (int i = blockR * blockn; i <= r; ++i)
        if (a[i] == x) ++sum;     
    return sum;
}
void sub() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		++cnt[i / blockn][a[i]];
	}
	int qr; cin >> qr;
	while(qr--) {
		int l,r,x; cin >> l >> r >> x;
		cout << truyvan(l,r,x);
	}
}
signed main() {
	#define name 
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if (fopen(name".inp", "r")) {
		freopen(name".inp", "r", stdin);
		freopen(name".out", "w", stdout);
	}
	sub();
	return 0;
}
//honguwu	

2. Thuật toán MO

Thuật toán MO giúp chúng ta cải thiện độ phức tạp của các truy vấn bằng cách sắp xếp chúng theo 1 thứ tự nhất định.

Bài toán 2

Cho một mảng \(A\) gồm \(N\) phần tử. Cần thực hiện \(Q\) truy vấn, mỗi truy vấn \((i, j)\) yêu cầu tìm giá trị xuất hiện nhiều lần nhất trong khoảng \([i,j]\). Giới hạn: \(N, Q, A_{i} <=10^{5}\).

Thường ta sẽ nghĩ theo hướng sử dụng Segment Tree để giải bài toán này, nhưng ta rất khó để hợp nhất 2 nút của Segment Tree với điều kiện tìm phần tử xuất hiện nhiều nhất này.

Thuật toán ngây thơ

• Với mỗi truy vấn, ta for từ trái sang phải, đếm số lần xuất hiện.
• Trong khi đếm thì ta cập nhật kết quả.

Thuật toán này có độ phức tạp \(O(N*Q)\) do mỗi truy vấn ta lại phải khởi tạo lại mảng \(cnt\).

Ta có thể cải tiến được như sau:

Sau khi trả lời truy vấn \([l_{1}, r_{1}]\), để trả lời truy vấn \([l_{2}, r_{2}]\), bạn chỉ cần thay đổi mảng đếm một cách phù hợp:

• Nếu \(l_{2} > l_{1}\), giảm số lần xuất hiện của \(A_{l_{1}}, …, A_{l_{2}-1}\).
• Nếu \(l_{2} < l_{1}\), tăng số lần xuất hiện của \(A_{l_{2}}, …, A_{l_{1}-1}\).
• Tương tự với \(r_{1}, r_{2}\).

Như vậy, độ phức tạp của ta là tổng \(|l_{i} – l_{i-1}| + |r_{i} – r_{i-1}|\), nhân thêm \(O(logN)\) để đếm và tìm phần tử lớn nhất của mảng đếm.

Thuật toán cải tiến

Thuật toán MO là một cách sắp xếp lại các truy vấn, sao cho tổng \(|l_{i} – l_{i-1}| + |r_{i} – r_{i-1}|\) không quá \(O(N * \sqrt{N} + Q * \sqrt{N})\)

Thứ tự các truy vấn được định nghĩa:

bool operator < (query A, query B){
	int blocka = A.l/ blockn;
	int blockb = B.l/blockn;
	if (blocka!=blockb) return A.l < B.l;
	return A.r < B.r;
}

Giải thích

Ta chia dãy thành các block độ dài \(\sqrt{N}\). Nếu đầu trái của truy vấn nằm ở 2 block khác nhau, ta sắp xếp theo đầu trái. Ngược lại, ta sắp xếp theo đầu phải.

Chứng minh

+) Di chuyển \(l_{1}\) đến \(l_{2}\):

• Nếu \(l_{1}\) và \(l_{2}\) cùng block: Với mỗi thao tác, độ phức tạp không quá \(sqrt(N)\). Do đó, độ phức tạp trong trường hợp này của cả \(Q\) thao tác là \(O(Q*\sqrt{N})\).
• Nếu \(l_{1}\) và \(l_{2}\) khác block: Vì ta ưu tiên sort theo \(l\) nên trường hợp này xảy ra không quá \(sqrt(N)\) lần. Ta mất \(O(N)\) cho mỗi trường hợp, nên độ phức tạp là \(O(N*\sqrt{N})\).

+) Di chuyển \(r_{1}\) đến \(r_{2}\):

• Nếu \(l_{1}\) và \(l_{2}\) cùng block: Vì trong cùng 1 block \(r\) được sắp xếp tăng dần nên với mỗi block của \(l\) ta mất \(O(N)\). Có \(sqrt(N)\) block nên độ phức tạp tổng là \(O(N*\sqrt{N})\).
• Nếu \(l_{1}\) và \(l_{2}\) khác block: tương tự như di chuyển \(l_{1}\) đến \(l_{2}\), độ phức tạp là \(O(N*\sqrt{N})\).

Suy ra độ phức tạp là \(O(N*\sqrt{N} + Q*\sqrt{N})\).

Cài đặt

• Ta lưu các truy vấn vào một mảng sau đó sort lại theo thứ tự ở trên.
• Ta sẽ xử lí offline các truy vấn: thực hiện truy vấn đầu tiên sau khi được sắp xếp lại trước; sau đó duyệt các truy vấn từ 2 đến \(n\), mỗi truy vấn được di chuyển từ truy vấn trước đó theo cách đã nói ở trên.
• Khi giảm số lần xuất hiện của \(x\), nếu số lần xuất hiện của \(x\) là lớn nhất thì ta trừ kết quả đi 1.
• Khi tăng số lần xuất hiện của \(x\), nếu số lần xuất hiện của \(x\) là lớn nhất thì ta tăng kết quả lên 1.

Độ phức tạp: \(O(N*\sqrt{N} + Q*\sqrt{N})\).

Code mẫu

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int int64_t
#define pii pair<int,int>
const int mx = 1e4 + 5;
const int mod = 1e9 + 7;
const int inf = 1e18;
int n,q,a[mx],ans[mx],res,blockn, cnt[mx], kq;
struct query{
	int l,r,id;
};
query qr[mxq];
void add(int pos){
	cnt[a[pos]]++;
	if (cnt[a[pos]]-1==res) {
		res++;
		kq = a[pos];
	}
}
void del(int pos){
	cnt[a[pos]]--;
	if (cnt[a[pos]]+1==res) {
		res--;
		kq = a[pos];
	}
}
bool operator < (query A, query B){
	int blocka = A.l/ blockn;
	int blockb = B.l/blockn;
	if (blocka!=blockb) return A.l < B.l;
	return A.r < B.r;
}
void sub() {
	cin >> n;
	blockn = sqrt(n);
	for (int i=1;i<=n;i++) {
		cin >> a[i];
	}
	cin >> q;
	for (int i =1;i<=q;i++) {
		cin >> qr[i].l >> qr[i].r;
		qr[i].id = i;
	}
	sort(qr+1,qr+q+1);
	int l = qr[1].l, r = qr[1].r;
	for (int i =l;i<=r;i++) add(i);
	ans[qr[1].id] = kq;
	for (int i =2;i<=q;i++){
		while(l<qr[i].l) del(l++);
		while(l>qr[i].l) add(--l);
		while(r<qr[i].r) add(++r);
		while(r>qr[i].r) del(r--);
		ans[qr[i].id] = kq;
	}
	for (int i =1;i<=q;i++) cout << ans[i] << '\n';

}
signed main() {
	#define name 
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if (fopen(name".inp", "r")) {
		freopen(name".inp", "r", stdin);
		freopen(name".out", "w", stdout);
	}
	sub();
	return 0;
}
//honguwu

Khi nào sử dụng thuật toán MO?

Khi gặp bài toán có các truy vấn đoạn ta có thể sử dụng thuật toán MO để giải quyết.

3. Luyện tập

Đây là một số bài tập luyện tập trong sách Competitive Programming Basic của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn