Chia căn và thuật toán Mo
Một mảng n số, q câu hỏi trên đoạn [l, r] xen kẽ với các lần sửa mảng. Duyệt cả đoạn mỗi câu hỏi mất tới n bước, cả bài n × q bước. Cây phân đoạn làm mỗi câu hỏi trong log n bước nhưng chỉ dùng được khi thông tin của hai nửa ghép được với nhau. Chia căn chậm hơn một chút (khoảng bước mỗi câu hỏi) nhưng dễ viết và dùng được cho nhiều câu hỏi mà cây phân đoạn khó làm.
Chia mảng thành các khối
Phần tiêu đề “Chia mảng thành các khối”Chia mảng thành các khối liên tiếp, mỗi khối B phần tử (khối cuối có thể ngắn hơn). Phần tử ở vị trí i (đánh số từ 0) thuộc khối i ÷ B. Với mỗi khối, tính sẵn thông tin cần hỏi, ví dụ tổng các phần tử trong khối.
Mảng 3 1 4 1 5 9 2 6 5 (n = 9, B = 3):
| Khối | 0 | 1 | 2 |
|---|---|---|---|
| Phần tử | 3 1 4 | 1 5 9 | 2 6 5 |
| Tổng khối | 8 | 15 | 13 |
Hỏi tổng đoạn từ vị trí 1 đến 7 (đánh số từ 0): đoạn gồm phần lẻ đầu là vị trí 1, 2 của khối 0 (cộng từng số: 1 + 4), khối trọn vẹn 1 (lấy tổng khối: 15), và phần lẻ cuối là vị trí 6, 7 của khối 2 (2 + 6). Tổng là 5 + 15 + 8 = 28.
Số bước: hai phần lẻ có không quá 2B phần tử, số khối trọn vẹn không quá n ÷ B. Tổng là 2B + n ÷ B, nhỏ nhất khi B khoảng , lúc đó mỗi câu hỏi khoảng 3 bước. Với n = 105 là khoảng 1000 bước, so với 105 bước nếu duyệt cả đoạn.
Sửa ai thành v: cập nhật tổng của khối chứa i (cộng thêm v - ai), chỉ một bước.
import sysfrom math import isqrt
def tao_khoi(a): """Kích thước khối B và tổng từng khối.""" B = isqrt(len(a)) + 1 tong_khoi = [0] * (len(a) // B + 1) for i, x in enumerate(a): tong_khoi[i // B] += x return B, tong_khoi
def tong_doan(a, B, tong_khoi, l, r): """Tổng a[l..r] (đánh số từ 0).""" tong = 0 while l <= r and l % B != 0: # phần lẻ đầu tong += a[l] l += 1 while l + B - 1 <= r: # các khối trọn vẹn tong += tong_khoi[l // B] l += B while l <= r: # phần lẻ cuối tong += a[l] l += 1 return tong
def sua(a, B, tong_khoi, i, v): tong_khoi[i // B] += v - a[i] a[i] = v#include <vector>#include <cmath>using namespace std;
int B;vector<long long> a, tongKhoi;
void taoKhoi() { B = sqrt(a.size()) + 1; tongKhoi.assign(a.size() / B + 1, 0); for (size_t i = 0; i < a.size(); i++) tongKhoi[i / B] += a[i];}
long long tongDoan(int l, int r) { // tổng a[l..r], đánh số từ 0 long long tong = 0; while (l <= r && l % B != 0) tong += a[l++]; // phần lẻ đầu while (l + B - 1 <= r) { tong += tongKhoi[l / B]; l += B; } // khối trọn vẹn while (l <= r) tong += a[l++]; // phần lẻ cuối return tong;}
void sua(int i, long long v) { tongKhoi[i / B] += v - a[i]; a[i] = v;}Muốn cộng v vào cả đoạn, mỗi khối giữ thêm một số cho_ca_khoi: khối trọn vẹn chỉ cần cộng v vào số đó (một
bước), phần lẻ thì cộng trực tiếp vào từng phần tử. Đây là cùng ý với cập nhật lười của cây phân đoạn.
Sức mạnh của chia căn là mỗi khối giữ được bất cứ thông tin gì tính lại được trong khoảng B bước. Ví dụ giữ bản sắp xếp của từng khối thì đếm được số phần tử nhỏ hơn x trong đoạn: khối trọn vẹn dùng tìm kiếm nhị phân, phần lẻ đếm từng số (bài 4).
Thuật toán Mo
Phần tiêu đề “Thuật toán Mo”Nhiều câu hỏi rất khó ghép từ hai nửa, ví dụ trên đoạn [l, r] có bao nhiêu giá trị khác nhau. Nhưng nếu đã biết
câu trả lời cho [l, r] thì câu trả lời cho [l, r + 1] tính rất nhanh: giữ mảng dem[x] là số lần x xuất hiện trong
đoạn; thêm ar + 1 vào, nếu dem của nó từ 0 lên 1 thì có thêm một giá trị mới. Bỏ một phần tử ra cũng
tương tự.
Vậy có thể giữ một đoạn [l, r] “đang xét” và dịch hai đầu từng bước tới đoạn của câu hỏi. Vấn đề là thứ tự: nếu các câu hỏi nhảy lung tung, mỗi lần dịch có thể tới n bước. Mo (đặt theo tên người phổ biến cách này) đọc hết các câu hỏi trước rồi sắp xếp lại để tổng số bước dịch nhỏ:
- Chia vị trí thành các khối B phần tử, B khoảng .
- Sắp xếp câu hỏi theo khối chứa l, cùng khối thì theo r tăng dần.
- Trả lời lần lượt theo thứ tự đó, rồi in ra theo thứ tự ban đầu của đề.
Vì sao nhanh? Các câu hỏi cùng khối l có r tăng dần, nên đầu phải chỉ đi sang phải, tối đa n bước cho mỗi khối; có n ÷ B khối, tổng n2 ÷ B bước. Đầu trái mỗi câu hỏi chỉ đi trong một khối (hoặc sang khối kế), khoảng B bước, tổng q × B bước. Với B khoảng , cả bài khoảng (n + q) bước. Với n = q = 105 là khoảng 6 × 107 bước, so với 1010 bước nếu duyệt từng đoạn.
import sysfrom math import isqrt
def so_gia_tri_khac_nhau(a, cau_hoi): """Trả lời offline: mỗi câu hỏi (l, r), đánh số từ 0, hỏi số giá trị khác nhau trong a[l..r].""" B = isqrt(len(a)) + 1 thu_tu = sorted(range(len(cau_hoi)), key=lambda k: (cau_hoi[k][0] // B, cau_hoi[k][1])) dem = [0] * (max(a) + 1) khac_nhau = 0 l, r = 0, -1 # đoạn đang xét: a[l..r], ban đầu rỗng tra_loi = [0] * len(cau_hoi) for k in thu_tu: ql, qr = cau_hoi[k] while r < qr: # nới đầu phải r += 1 dem[a[r]] += 1 if dem[a[r]] == 1: khac_nhau += 1 while l > ql: # nới đầu trái l -= 1 dem[a[l]] += 1 if dem[a[l]] == 1: khac_nhau += 1 while r > qr: # thu đầu phải dem[a[r]] -= 1 if dem[a[r]] == 0: khac_nhau -= 1 r -= 1 while l < ql: # thu đầu trái dem[a[l]] -= 1 if dem[a[l]] == 0: khac_nhau -= 1 l += 1 tra_loi[k] = khac_nhau return tra_loi#include <vector>#include <cmath>#include <algorithm>using namespace std;
// Mỗi câu hỏi (l, r), đánh số từ 0: số giá trị khác nhau trong a[l..r].vector<int> soGiaTriKhacNhau(const vector<int> &a, const vector<pair<int, int>> &cauHoi) { int B = sqrt(a.size()) + 1, q = cauHoi.size(); vector<int> thuTu(q); for (int k = 0; k < q; k++) thuTu[k] = k; sort(thuTu.begin(), thuTu.end(), [&](int x, int y) { if (cauHoi[x].first / B != cauHoi[y].first / B) return cauHoi[x].first / B < cauHoi[y].first / B; return cauHoi[x].second < cauHoi[y].second; }); vector<int> dem(*max_element(a.begin(), a.end()) + 1, 0), traLoi(q); int khacNhau = 0, l = 0, r = -1; auto them = [&](int i) { if (++dem[a[i]] == 1) khacNhau++; }; auto bo = [&](int i) { if (--dem[a[i]] == 0) khacNhau--; }; for (int k : thuTu) { auto [ql, qr] = cauHoi[k]; while (r < qr) them(++r); // nới trước while (l > ql) them(--l); while (r > qr) bo(r--); // thu sau while (l < ql) bo(l++); traLoi[k] = khacNhau; } return traLoi;}Nên nới đoạn trước, thu đoạn sau như trong code, để đoạn đang xét không bao giờ bị “âm” (l lớn hơn r + 1).
Mo chỉ dùng được khi:
- đọc được hết câu hỏi trước khi trả lời (offline) và mảng không bị sửa giữa chừng;
- thêm hoặc bỏ một phần tử ở hai đầu đoạn cập nhật được câu trả lời nhanh (thường một vài bước).
Mẹo nhỏ: ở các khối thứ tự lẻ, sắp r giảm dần thay vì tăng dần. Đầu phải đi tới cuối khối này rồi quay về ở khối sau thay vì nhảy về đầu, bớt được khoảng một nửa số bước của đầu phải.
Luyện tập
Phần tiêu đề “Luyện tập”Gồm 11 bài, chia thành 3 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.
Nhóm 1. Chia mảng thành khối
Phần tiêu đề “Nhóm 1. Chia mảng thành khối”Bài 1. Tổng đoạn có sửa phần tử
Phần tiêu đề “Bài 1. Tổng đoạn có sửa phần tử”Dòng đầu có n, q (1 ≤ n, q ≤ 105), dòng thứ hai có n số nguyên (|ai| ≤ 109). q dòng sau mỗi dòng là 1 i v (gán ai = v, |v| ≤ 109) hoặc 2 l r (hỏi tổng al + … + ar). In ra đáp số các câu hỏi loại 2.
Ví dụ:
| Nhập | In ra |
|---|---|
5 41 2 3 4 52 2 41 3 102 1 52 3 3 | 92210 |
Kiểm tra: nhập
9 53 1 4 1 5 9 2 6 52 2 81 5 -52 4 61 9 02 1 9Bài 2. Cộng cả đoạn, hỏi tổng đoạn
Phần tiêu đề “Bài 2. Cộng cả đoạn, hỏi tổng đoạn”Dòng đầu có n, q (1 ≤ n, q ≤ 105), dòng thứ hai có n số nguyên (|ai| ≤ 109). q dòng sau mỗi dòng là 1 l r v (cộng v vào mọi al, …, ar, |v| ≤ 104) hoặc 2 l r (hỏi tổng al + … + ar). In ra đáp số các câu hỏi loại 2.
Ví dụ:
| Nhập | In ra |
|---|---|
6 41 1 1 1 1 11 2 5 32 1 61 4 6 -12 5 6 | 183 |
Kiểm tra: nhập
10 65 3 8 1 0 2 7 4 6 91 1 10 22 3 71 2 4 52 1 31 6 9 -32 4 10Bài 3. Nhỏ nhất trên đoạn có sửa phần tử
Phần tiêu đề “Bài 3. Nhỏ nhất trên đoạn có sửa phần tử”Dòng đầu có n, q (1 ≤ n, q ≤ 105), dòng thứ hai có n số nguyên (|ai| ≤ 109). q dòng sau mỗi dòng là 1 i v (gán ai = v) hoặc 2 l r (hỏi số nhỏ nhất trong al, …, ar). In ra đáp số các câu hỏi loại 2.
Ví dụ:
| Nhập | In ra |
|---|---|
6 44 2 7 1 8 32 1 31 4 92 3 62 4 5 | 238 |
Kiểm tra: nhập
10 69 4 6 2 8 5 7 1 3 102 2 71 4 112 2 71 8 02 5 102 9 9Bài 4. Đếm số không vượt quá x trong đoạn
Phần tiêu đề “Bài 4. Đếm số không vượt quá x trong đoạn”Dòng đầu có n, q (1 ≤ n, q ≤ 5 × 104), dòng thứ hai có n số nguyên (|ai| ≤ 109). q dòng sau mỗi dòng là 1 i v (gán ai = v) hoặc 2 l r x (hỏi có bao nhiêu chỉ số i trong [l, r] mà ai ≤ x). In ra đáp số các câu hỏi loại 2.
Ví dụ:
| Nhập | In ra |
|---|---|
6 35 1 4 2 6 32 1 6 31 2 72 2 5 4 | 32 |
Kiểm tra: nhập
10 58 3 5 9 1 4 7 2 6 02 1 10 42 3 8 61 5 102 3 8 62 4 4 9Nhóm 2. Thuật toán Mo
Phần tiêu đề “Nhóm 2. Thuật toán Mo”Bài 5. Số giá trị khác nhau trong đoạn
Phần tiêu đề “Bài 5. Số giá trị khác nhau trong đoạn”Dòng đầu có n, q (1 ≤ n, q ≤ 105), dòng thứ hai có n số nguyên (1 ≤ ai ≤ 106), q dòng sau mỗi dòng có l, r (1 ≤ l ≤ r ≤ n). Với mỗi câu hỏi, in ra số giá trị khác nhau trong al, …, ar.
Ví dụ:
| Nhập | In ra |
|---|---|
6 31 2 1 3 2 21 32 64 4 | 231 |
Kiểm tra: nhập
10 55 5 1 2 5 3 1 2 4 51 102 43 85 66 10Bài 6. Số cặp bằng nhau trong đoạn
Phần tiêu đề “Bài 6. Số cặp bằng nhau trong đoạn”Dòng đầu có n, q (1 ≤ n, q ≤ 105), dòng thứ hai có n số nguyên (1 ≤ ai ≤ 106), q dòng sau mỗi dòng có l, r. Với mỗi câu hỏi, đếm số cặp chỉ số (i, j) với l ≤ i nhỏ hơn j ≤ r mà ai = aj.
Ví dụ:
| Nhập | In ra |
|---|---|
6 31 2 1 1 2 31 42 51 6 | 324 |
Kiểm tra: nhập
10 54 4 4 2 4 2 2 1 4 21 101 34 72 98 8Bài 7. Sức mạnh của đoạn
Phần tiêu đề “Bài 7. Sức mạnh của đoạn”Dòng đầu có n, q (1 ≤ n, q ≤ 105), dòng thứ hai có n số nguyên (1 ≤ ai ≤ 106), q dòng sau mỗi dòng có l, r. Sức mạnh của đoạn al, …, ar là tổng của cx × cx × x theo mọi giá trị x, với cx là số lần x xuất hiện trong đoạn. In ra sức mạnh của từng đoạn được hỏi.
Ví dụ:
| Nhập | In ra |
|---|---|
4 21 2 1 11 42 3 | 113 |
Kiểm tra: nhập
8 43 1 3 3 2 1 2 31 82 54 71 1Bài 8. Giá trị xuất hiện đúng k lần
Phần tiêu đề “Bài 8. Giá trị xuất hiện đúng k lần”Dòng đầu có n, q, k (1 ≤ n, q ≤ 105, 1 ≤ k ≤ n), dòng thứ hai có n số nguyên (1 ≤ ai ≤ 106), q dòng sau mỗi dòng có l, r. Với mỗi câu hỏi, in ra số giá trị xuất hiện đúng k lần trong al, …, ar.
Ví dụ:
| Nhập | In ra |
|---|---|
7 3 21 2 1 3 2 2 31 41 72 6 | 120 |
Kiểm tra: nhập
10 5 34 1 4 4 2 1 1 2 4 21 101 42 75 103 9Bài 9. Đếm đoạn con có XOR bằng k
Phần tiêu đề “Bài 9. Đếm đoạn con có XOR bằng k”Dòng đầu có n, q, k (1 ≤ n, q ≤ 105, 0 ≤ k ≤ 106), dòng thứ hai có n số nguyên (0 ≤ ai ≤ 106), q dòng sau mỗi dòng có l, r. Với mỗi câu hỏi, đếm số cặp (i, j) với l ≤ i ≤ j ≤ r mà ai XOR ai + 1 XOR … XOR aj = k.
Ví dụ:
| Nhập | In ra |
|---|---|
6 2 31 2 1 1 0 31 63 5 | 70 |
Kiểm tra: nhập
8 4 11 0 1 1 0 0 1 11 82 53 34 8Nhóm 3. Chia theo kích thước
Phần tiêu đề “Nhóm 3. Chia theo kích thước”Bài 10. Những cái lỗ
Phần tiêu đề “Bài 10. Những cái lỗ”Có n lỗ xếp thành hàng, đánh số 1 đến n. Lỗ i có sức bật ai ≥ 1: quả bóng rơi vào lỗ i sẽ nảy sang lỗ i + ai, nếu i + ai lớn hơn n thì bóng ra khỏi hàng. Dòng đầu có n, q (1 ≤ n, q ≤ 105), dòng thứ hai có a1, …, an (1 ≤ ai ≤ n). q dòng sau mỗi dòng là 0 i v (đổi ai thành v, 1 ≤ v ≤ n) hoặc 1 i (thả bóng vào lỗ i). Với mỗi lần thả, in ra lỗ cuối cùng bóng chạm trước khi ra khỏi hàng và số lần bóng rơi vào lỗ (tính cả lỗ i).
Ví dụ:
| Nhập | In ra |
|---|---|
8 51 1 1 1 1 2 8 21 10 1 31 10 3 41 2 | 8 78 57 3 |
Kiểm tra: nhập
10 62 3 1 2 4 1 3 2 1 51 11 40 4 61 10 2 11 2Bài 11. Tổng theo bước nhảy
Phần tiêu đề “Bài 11. Tổng theo bước nhảy”Dòng đầu có n (1 ≤ n ≤ 3 × 104), dòng thứ hai có n số nguyên (|ai| ≤ 109), dòng thứ ba có q (1 ≤ q ≤ 3 × 104), q dòng sau mỗi dòng có x, y (1 ≤ x, y ≤ n). Với mỗi câu hỏi, in ra ax + ax + y + ax + 2y + … (cộng tới khi chỉ số vượt quá n).
Ví dụ:
| Nhập | In ra |
|---|---|
51 2 3 4 531 22 23 1 | 9612 |
Kiểm tra: nhập
103 -1 4 1 -5 9 2 6 5 351 32 34 71 110 2