Problem 71: Range Mode Query using Mo's Algorithm
Problem Statement: Given an array and q queries asking for the most frequent element's frequency in subarrays, answer all queries using Mo's algorithm.
Input
The first line contains integers n and q. The second line contains n integers. Each of the next q lines contains two integers l and r (1-indexed) forming a query.
Output
For each query, print the frequency of the mode in the subarray [l, r].
Examples
Input:
5 3
1 2 2 3 1
1 3
2 5
1 5
Output:
2
2
2
Solution Explanation
Mo's algorithm reorders queries to minimize cost of moving window. Use an auxiliary frequency array and update frequency as the window moves, maintaining the maximum frequency.
Solution in C++
#include
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector a(n);
for(int i = 0; i < n; i++)
cin >> a[i];
int block = sqrt(n);
vector> queries;
for(int i = 0; i < q; i++){
int l, r;
cin >> l >> r;
l--; r--;
queries.push_back({l, r, i});
}
sort(queries.begin(), queries.end(), [&](auto A, auto B){
int l1, r1, l2, r2, id1, id2;
tie(l1, r1, id1) = A;
tie(l2, r2, id2) = B;
if(l1 / block != l2 / block) return l1 / block < l2 / block;
return r1 < r2;
});
vector res(q);
vector freq(100001, 0);
int curL = 0, curR = -1, curMode = 0;
auto add = [&](int pos){
freq[a[pos]]++;
curMode = max(curMode, freq[a[pos]]);
};
auto remove = [&](int pos){
freq[a[pos]]--;
curMode = 0;
for(int i = curL; i <= curR; i++){
curMode = max(curMode, freq[a[i]]);
}
};
for(auto &qu : queries){
int L, R, idx;
tie(L, R, idx) = qu;
while(curR < R){
add(++curR);
}
while(curR > R){
remove(curR);
curR--;
}
while(curL < L){
remove(curL);
curL++;
}
while(curL > L){
add(--curL);
}
int mode = 0;
for(int i = L; i <= R; i++){
mode = max(mode, freq[a[i]]);
}
res[idx] = mode;
}
for(auto r : res)
cout << r << "\n";
return 0;
}