MO Algorithm
The MO Algorithm, also known as the Square Root Decomposition technique, is an efficient method used for solving problems that involve processing a large number of queries on array elements. It is particularly useful in situations where the array remains static and does not undergo any modifications during the query processing, making it suitable for offline query processing. The algorithm's main idea is to divide the array into smaller blocks of size approximately √n, where n is the size of the array. Then, for each query, the algorithm calculates the result by considering only the relevant blocks and the elements within them. This approach significantly reduces the time complexity, resulting in fast query processing.
To implement the MO algorithm, the queries are first sorted based on their block numbers and, in case of a tie, their end indices. This enables the algorithm to process the queries in a specific order, minimizing the number of operations needed to compute the results. The algorithm maintains a data structure that keeps track of the current state of the solution, which is updated incrementally as the queries are processed. As the algorithm iterates through the queries, it adds or removes elements from the data structure, depending on whether they are part of the current query range or not. This allows for efficient computation of the query results, with a time complexity of O((n + q) * √n), where n is the size of the array, and q is the number of queries. The MO algorithm's effectiveness lies in its ability to minimize redundant operations, making it a popular choice for solving complex computational problems.
#include <iostream>
using namespace std;
const int N = 1e6 + 5;
int a[N], bucket[N], cnt[N];
int bucket_size;
struct query
{
int l, r, i;
} q[N];
int ans = 0;
void add(int index)
{
cnt[a[index]]++;
if (cnt[a[index]] == 1)
ans++;
}
void remove(int index)
{
cnt[a[index]]--;
if (cnt[a[index]] == 0)
ans--;
}
bool mycmp(query x, query y)
{
if (x.l / bucket_size != y.l / bucket_size)
return x.l / bucket_size < y.l / bucket_size;
return x.r < y.r;
}
int main()
{
int n, t, i, j, k = 0;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
bucket_size = ceil(sqrt(n));
scanf("%d", &t);
for (i = 0; i < t; i++)
{
scanf("%d %d", &q[i].l, &q[i].r);
q[i].l--;
q[i].r--;
q[i].i = i;
}
sort(q, q + t, mycmp);
int left = 0, right = 0;
for (i = 0; i < t; i++)
{
int L = q[i].l, R = q[i].r;
while (left < L)
{
remove(left);
left++;
}
while (left > L)
{
add(left - 1);
left--;
}
while (right <= R)
{
add(right);
right++;
}
while (right > R + 1)
{
remove(right - 1);
right--;
}
bucket[q[i].i] = ans;
}
for (i = 0; i < t; i++)
printf("%d\n", bucket[i]);
return 0;
}
