Một ý tưởng căn bậc hai, hai cách dùng
Chia căn gom khoảng sqrt(n) phần tử liên tiếp thành một khối. Với truy vấn tổng và cập nhật điểm, mỗi khối lưu sẵn tổng; một đoạn được tách thành hai mép lẻ và nhiều khối đầy. Thuật toán Mo dùng kích thước khối để sắp lại truy vấn ngoại tuyến, nhờ đó hai đầu cửa sổ ít phải chạy xa.
Mo không thay đổi đáp án vì các truy vấn độc lập và được trả về theo id ban đầu. Nó chỉ thay thứ tự tính để tái sử dụng trạng thái cửa sổ [L,R).
Chia căn cơ bản trước khi học Mo
Với mảng tĩnh hoặc có cập nhật điểm, chọn độ dài khối B gần sqrt(n). Phần tử i thuộc khối i//B. Truy vấn tổng [l,r) cộng từng phần tử cho tới đầu khối, cộng nhanh tổng các khối nằm trọn, rồi xử lý đuôi. Một truy vấn đi qua O(n/B+B) mục; chọn B gần căn n cân bằng hai phần.
Cập nhật điểm a[i]=x chỉ cần đổi tổng khối bằng hiệu mới-cũ, tốn O(1). Nếu phép cập nhật là cộng cả đoạn, cần thêm nhãn khối hoặc cấu trúc khác. “Sqrt decomposition” là một họ thiết kế; không có một bản duy nhất tự giải mọi loại truy vấn.
Mo biến truy vấn thành đường đi của hai con trỏ
Giả sử cần số giá trị phân biệt trong nhiều đoạn, mảng không đổi và biết toàn bộ truy vấn trước. Mỗi truy vấn mang (l,r,id). Sắp theo l//B; trong cùng khối l, sắp r tăng ở khối chẵn và giảm ở khối lẻ. Kiểu zíc zắc tránh đưa R về đầu sau mỗi khối.
Duy trì cửa sổ nửa mở [L,R), mảng freq và số distinct. Khi thêm vị trí i, tăng freq[value]; nếu từ 0 lên 1 thì tăng distinct. Khi bỏ, giảm tần suất; nếu về 0 thì giảm distinct. Trước khi ghi đáp án, bốn vòng while phải đưa chính xác L tới l và R tới r.
Trên 1,2,1,3,2, đoạn [0,3) có hai giá trị, [1,5) có ba, còn [2,2) rỗng nên bằng 0. Ca rỗng kiểm việc hai con trỏ có thể trùng nhau mà không thêm phần tử ngoài đoạn.
Nén giá trị là phần của hợp đồng
Tần suất không thể đánh chỉ số trực tiếp nếu a[i] âm hoặc tới 10^9. Code sắp các giá trị phân biệt, ánh xạ chúng về 0..k-1 rồi mới tạo freq. Nén giữ quan hệ bằng nhau, đúng điều bài đếm distinct cần. Nếu trạng thái phụ thuộc khoảng cách số học, phải giữ cả giá trị gốc.
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
struct Query{int l,r,id;};
vector<int> mo_distinct(const vector<int>& a,vector<Query> q){
int n=a.size(),bs=max(1,(int)sqrt(max(1,n)));vector<int> vals=a;sort(vals.begin(),vals.end());vals.erase(unique(vals.begin(),vals.end()),vals.end());vector<int>b(n);for(int i=0;i<n;++i)b[i]=lower_bound(vals.begin(),vals.end(),a[i])-vals.begin();
sort(q.begin(),q.end(),[&](auto x,auto y){int bx=x.l/bs,by=y.l/bs;if(bx!=by)return bx<by;return bx&1?x.r>y.r:x.r<y.r;});
vector<int>f(vals.size()),ans(q.size());int L=0,R=0,d=0;auto add=[&](int i){if(f[b[i]]++==0)++d;};auto del=[&](int i){if(--f[b[i]]==0)--d;};
for(auto x:q){while(L>x.l)add(--L);while(R<x.r)add(R++);while(L<x.l)del(L++);while(R>x.r)del(--R);ans[x.id]=d;}return ans;
}
int main(){int n=5,q=3;vector<int>a={1,2,1,3,2};vector<Query>qs={{0,3,0},{1,5,1},{2,2,2}};if(cin>>n>>q){a.resize(n);for(auto&x:a)cin>>x;qs.resize(q);for(int i=0;i<q;++i){cin>>qs[i].l>>qs[i].r;qs[i].id=i;}}for(int x:mo_distinct(a,qs))cout<<x<<'\n';}
import math,sys
def mo_distinct(a,queries):
n=len(a);bs=max(1,math.isqrt(max(1,n)));vals={x:i for i,x in enumerate(sorted(set(a)))};b=[vals[x] for x in a];order=sorted(range(len(queries)),key=lambda i:(queries[i][0]//bs,queries[i][1] if queries[i][0]//bs%2==0 else -queries[i][1]));f=[0]*len(vals);ans=[0]*len(queries);L=R=d=0
for qi in order:
l,r=queries[qi]
while L>l:L-=1;f[b[L]]+=1;d+=f[b[L]]==1
while R<r:f[b[R]]+=1;d+=f[b[R]]==1;R+=1
while L<l:f[b[L]]-=1;d-=f[b[L]]==0;L+=1
while R>r:R-=1;f[b[R]]-=1;d-=f[b[R]]==0
ans[qi]=d
return ans
if __name__=='__main__':
z=list(map(int,sys.stdin.buffer.read().split()));a=[1,2,1,3,2];qs=[(0,3),(1,5),(2,2)]
if z:n,q=z[:2];a=z[2:2+n];p=2+n;qs=[tuple(z[p+2*i:p+2*i+2]) for i in range(q)]
print(*mo_distinct(a,qs),sep='\n')
Sắp truy vấn tốn O(q log q), nén tốn O(n log n). Với B gần căn n, số lần thêm/bớt của Mo cơ bản thường được chặn O((n+q)sqrt(n)); mỗi lần ở bài này là O(1). Bộ nhớ gồm mảng nén, tần suất, truy vấn và đáp án: O(n+q).
Điều kiện để Mo đáng dùng
Mo phù hợp khi truy vấn ngoại tuyến, mảng không cập nhật, và trạng thái hỗ trợ thêm/bớt một đầu nhanh. Nếu phải trả lời ngay khi truy vấn đến, không thể sắp lại. Nếu có cập nhật xen kẽ, cần Mo ba chiều với “thời gian”, phức tạp hơn đáng kể. Nếu phép hỏi là tổng, prefix sum trả O(1) đơn giản hơn; dùng Mo sẽ thừa.
Đếm mode không tự động O(1), vì bỏ một giá trị có thể làm tần suất cao nhất thay đổi. Cần thêm bảng số lượng theo tần suất hoặc chia căn lần nữa. Câu “Mo xử lý mọi truy vấn đoạn” vì vậy sai; chi phí của add và remove quyết định tổng chi phí.
Không trộn đoạn đóng [l,r] với cửa sổ nửa mở [L,R). Nếu đề cho r đóng, hãy đổi một lần thành r+1 ngay khi đọc.
Vì sao thứ tự zíc zắc tốt hơn?
Nếu mọi khối đều sắp r tăng, khi chuyển khối của l, R có thể nhảy từ gần n về nhỏ rồi lại tăng. Đảo chiều ở khối lẻ tạo đường đi liên tục hơn. Điều này cải thiện hằng số; chặn tiệm cận cơ bản không đổi. Kích thước khối tối ưu thực tế còn phụ thuộc n, q và chi phí cập nhật, nên sqrt(n) là điểm bắt đầu có cơ sở, không phải luật tuyệt đối.
Tự kiểm tra bốn vòng di chuyển con trỏ
Để kiểm tra thuật toán Mo có cập nhật đúng tần suất và trả kết quả đúng thứ tự ban đầu hay không, bạn hãy viết một hàm đơn giản: với mỗi truy vấn [l, r), đưa các phần tử trong đoạn vào một tập hợp set rồi lấy kích thước. Hãy thử các ca có số âm, nhiều giá trị bằng nhau, đoạn chỉ gồm 1 phần tử và đoạn rỗng [l, l). Kết quả của thuật toán Mo phải khớp từng vị trí trong mảng đáp án.
Khi sinh các bộ truy vấn ngẫu nhiên để thử, hãy tạo nhiều cặp (l, r) nhảy lùi tiến thất thường rồi chuẩn hóa l <= r. Khi so sánh kết quả với hàm set, tuyệt đối phải đối chiếu theo đúng thứ tự câu hỏi gốc chứ không sắp xếp mảng đáp án trước khi so: nếu bạn quên gán kết quả qua ans[q.id], tập hợp các con số in ra có thể vẫn đúng nhưng bị gắn nhầm sang truy vấn khác.
Theo dõi bốn con trỏ của Mo
Vẽ trục chỉ số cho mảng 1,2,1,3,2. Bắt đầu [L,R)=[0,0), rồi lần lượt đưa cửa sổ tới [2,2), [0,3) và [1,5) theo thứ tự đề cho (code thật, với B = 2, sẽ xử lý theo thứ tự [0,3), [1,5) rồi [2,2)). Sau mỗi thao tác thêm hoặc bớt, ghi tần suất của 1, 2, 3 và biến distinct.
| Chuyển động | Thao tác | Điều kiện đổi distinct |
|---|---|---|
| R tăng | thêm a[R] |
tần suất cũ bằng 0 |
| R giảm | bỏ a[R-1] |
tần suất mới bằng 0 |
| L giảm | thêm a[L-1] |
tần suất cũ bằng 0 |
| L tăng | bỏ a[L] |
tần suất mới bằng 0 |
Để tự kiểm, tính mỗi đáp án bằng set(a[l:r]) trên mảng ngắn. Giữ nguyên thứ tự truy vấn khi so; một cài đặt quên id có thể tạo đúng tập đáp án nhưng gắn chúng vào sai câu hỏi.
Chọn kích thước khối theo bài
Giá trị căn n là điểm khởi đầu vì cân bằng hai loại chuyển động, không phải con số bắt buộc. Khi q lớn hơn n rất nhiều hoặc thao tác thêm đắt hơn thao tác bỏ, kích thước tốt có thể lệch. Trong thi đấu, nên bắt đầu bằng phân tích số lần di chuyển rồi mới thử vài kích thước trên bộ sinh dữ liệu đại diện.
Thứ tự zíc zắc giảm việc R quay đầu ở biên khối. Hilbert order còn sắp truy vấn theo đường cong Hilbert (một đường cong lấp đầy mặt phẳng) để cả L và R thay đổi êm hơn; nó thường cải thiện hằng số nhưng code khó giải thích và kiểm hơn. Chỉ đổi khi bản Mo cơ bản đã đúng và giới hạn thực sự cần.
Mo trên cây thường biến đường đi thành đoạn trên Euler tour, thêm một đỉnh hai lần có thể triệt tiêu trạng thái. Mo có cập nhật thêm chiều thời gian và thao tác áp dụng/hoàn tác thay đổi. Hai biến thể này không phải sửa vài dòng; cần viết lại bất biến về tập đỉnh hoặc phiên bản mảng đang hoạt động.
Khi nào nên rời Mo
Mo phù hợp nhất khi dữ liệu tĩnh và việc thêm, bỏ một phần tử đều rẻ. Nếu có cập nhật xen kẽ, bản Mo ba chiều phức tạp hơn rõ rệt; nếu phép gộp có tính kết hợp, Segment Tree thường dễ kiểm chứng hơn. Nếu mọi truy vấn chỉ hỏi tổng, prefix sum thắng tuyệt đối. Vì vậy Mo là lời giải cho thống kê khó gộp, không phải mặc định cho mọi truy vấn đoạn.
Luyện ngay trên Big-O Coding
Các bài dưới đây luyện đúng hai phần của bài: thuật toán Mo và chia căn.
Bài đầu là đúng ví dụ trong bài: đếm số giá trị phân biệt trên nhiều đoạn khi biết trước mọi truy vấn. Evangelion luyện chia căn theo một kiểu khác: tách các lần cập nhật theo bước nhảy lớn hay nhỏ.
Câu hỏi thường gặp
Mo có chạy trực tuyến không?
Không ở bản cơ bản, vì nó cần biết và sắp toàn bộ truy vấn trước.
Có thể dùng B bằng 1 không?
Đúng về kết quả nhưng R có thể di chuyển rất nhiều. Chọn gần căn n để cân bằng chuyển động L và R.
Vì sao Python vẫn có thể dùng Mo?
Được nếu giới hạn phù hợp và add/remove nhẹ. Cần tránh cấu trúc nặng trong vòng di chuyển, nén giá trị và dùng danh sách tần suất.
Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.


