Este artigo apresenta uma introdução prática ao algoritmo de Mo, um método eficiente para resolver conusltas em intervalos com atualizações. Embora o foco inicial fosse abordar variantes avançadas como Mo com rollback, Mo em árvores e Mo bidimensional, a dificuldade em dominá-las levou à decisão de documentar apenas as versões básicas — Mo simples e Mo com atualizações — que são fundamentais para entender o conceito.
Mo Simples: O Poder da Ordenação Estratégica
O algoritmo de Mo é frequentemente descrito como "violência elegante", pois aproveita a estrutura das consultas para reduzir drasticamente o tempo de execução quando comparado à abordagem direta.
Problema Modelo
Dada uma sequência de números e múltiplas consultas, cada uma pede a contagem de elementos distintos em um intervalo [l, r]. A solução ingênua, que itera sobre cada consulta e verifica todos os elementos no intervalo, tem complexidade O(q × n²), o que inevitavelmente leva ao timeout (TLE).
Abordagens Iterativas
- Primeira melhoria: Em vez de contar distinções no final, mantém-se um contador dinâmico durante a expansão do intervalo. Isso reduz a complexidade para O(n²q), mas ainda é inaceitável.
- Segunda melhoria: Aplica-se processamento offline — todas as consultas são lidas antes de qualquer cálculo. A partir de um estado inicial vazio, os ponteiros
lersão movidos passo a passo entre consultas, atualizando o resultado conforme novos elementos entram ou saem do intervalo. - Terceira melhoria: Para evitar movimentos excessivos dos ponteiros, especialmente quando as consultas estão mal ordenadas, ordena-se as consultas por bloco do índice esquerdo. Ainda assim, a complexidade permanece em O(qn log n).
A Solução: Partição em Blocos
A chave está na divisão da sequência em blocos de tamanho aproximadamente √n. As consultas são ordenadas primeiro pelo bloco do início (l), e dentro do mesmo bloco, pelo valor do fim (r). Essa estratégia garante que os movimentos dos ponteiros sejam mais locais, resultando em uma complexidade total de O(n√n).
Código Implementado
const int MAXN = 1000010;
int cnt[MAXN], arr[MAXN];
struct Query {
int left, right, idx;
int ans;
} queries[MAXN];
int block_size;
int result[MAXN];
bool compare(const Query& a, const Query& b) {
if (a.left / block_size != b.left / block_size)
return a.left / block_size < b.left / block_size;
return a.right < b.right;
}
void add_element(int val) {
if (cnt[val] == 0) ++result[0]; // Incrementa contagem de valores únicos
cnt[val]++;
}
void remove_element(int val) {
cnt[val]--;
if (cnt[val] == 0) --result[0];
}
int main() {
std::ios::sync_with_stdio(false);
int n, q;
std::cin >> n;
block_size = static_cast<int>(std::sqrt(n));
for (int i = 1; i <= n; ++i)
std::cin >> arr[i];
std::cin >> q;
for (int i = 1; i <= q; ++i) {
std::cin >> queries[i].left >> queries[i].right;
queries[i].idx = i;
}
std::sort(queries + 1, queries + q + 1, compare);
int current_left = 1, current_right = 0;
result[0] = 0;
for (int i = 1; i <= q; ++i) {
while (current_right < queries[i].right) add_element(arr[++current_right]);
while (current_right > queries[i].right) remove_element(arr[current_right--]);
while (current_left > queries[i].left) add_element(arr[--current_left]);
while (current_left < queries[i].left) remove_element(arr[current_left++]);
result[queries[i].idx] = result[0];
}
for (int i = 1; i <= q; ++i)
std::cout << result[i] << '\n';
return 0;
}
Esse código resolve o problema "HH's Necklace" no Luogu, embora tenha sido desafiado por dados de entrada fortificados — mesmo assim, é um bom exemplo para validar a implementação básica.
Otimização por Paridade
Uma pequena otimização útil consiste em alternar a ordem do right dependendo do bloco par ou ímpar do left:
bool compare(const Query& a, const Query& b) {
int block_a = a.left / block_size;
int block_b = b.left / block_size;
if (block_a != block_b)
return block_a < block_b;
if (block_a % 2 == 1)
return a.right < b.right;
return a.right > b.right;
}
Essa técnica reduz o número de movimentos desnecessários nos casos extremos, sendo especialmente útil em competições onde o tempo limite é apertado.
Exemplo Prático: Consultas com Soma de Quadrados
Um problema típico após HH's Necklace é calcular a soma dos quadrados das frequências de elementos em um intervalo.
Solução: Ao adicionar ou remover um elemento, atualiza-se a soma usando a fórmula:
ans -= freq[x] * freq[x];
freq[x]++;
ans += freq[x] * freq[x];
Essa abordagem permite responder perguntas como "qual é a soma dos quadrados das contagens de cada número no intervalo?" com eficiência.
Mo com Atualizações
Quando operações de modificação (alterar um valor em uma posição) estão presentes, o algoritmo precisa lidar com três dimensões: posição esquerda, posição direita e tempo (número de atualizações realizadas).
Princípio Geral
As consultas agora têm formato (l, r, t), onde t representa o número de atualizações ocorridas antes da consulta. O algoritmo deve mover-se não apenas pelos índices l e r, mas também pelo tempo, aplicando ou revertendo modificações conforme necessário.
Ordenação Tripla
As consultas são ordanadas por:
- Bloco do início (l)
- Bloco do fim (r)
- Tempo (t)
O tamanho ideal do bloco é n^(2/3), resultando em cerca de n^(1/3) blocos. A complexidade total torna-se O(n^(5/3)), embora provas formais sejam complexas.
Implementação
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;
int block_size;
struct Query {
int l, r, time_id, id;
};
struct Update {
int pos, new_val;
};
Query queries[MAXN];
Update updates[MAXN];
int values[MAXN];
int count[MAXN];
int answer[MAXN];
int current_time = 0;
int current_l = 1, current_r = 0;
bool cmp(const Query& a, const Query& b) {
int block_a_l = a.l / block_size;
int block_b_l = b.l / block_size;
if (block_a_l != block_b_l)
return block_a_l < block_b_l;
int block_a_r = a.r / block_size;
int block_b_r = b.r / block_size;
if (block_a_r != block_b_r)
return block_a_r < block_b_r;
return a.time_id < b.time_id;
}
void add(int x) {
if (count[x] == 0) ++answer[0];
count[x]++;
}
void remove(int x) {
count[x]--;
if (count[x] == 0) --answer[0];
}
int main() {
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> values[i];
int q_count = 0, u_count = 0;
block_size = pow(n, 0.666); // n^(2/3)
for (int i = 1; i <= m; ++i) {
char op;
int x, y;
cin >> op >> x >> y;
if (op == 'Q') {
queries[++q_count] = {x, y, u_count, q_count};
} else {
updates[++u_count] = {x, y};
}
}
sort(queries + 1, queries + q_count + 1, cmp);
for (int i = 1; i <= q_count; ++i) {
// Mover l e r
while (current_l < queries[i].l) remove(values[current_l++]);
while (current_l > queries[i].l) add(values[--current_l]);
while (current_r < queries[i].r) add(values[++current_r]);
while (current_r > queries[i].r) remove(values[current_r--]);
// Aplicar ou reverter atualizações
while (current_time < queries[i].time_id) {
++current_time;
int pos = updates[current_time].pos;
int old_val = values[pos];
int new_val = updates[current_time].new_val;
if (current_l <= pos && pos <= current_r) {
remove(old_val);
add(new_val);
}
swap(values[pos], updates[current_time].new_val);
}
while (current_time > queries[i].time_id) {
int pos = updates[current_time].pos;
int old_val = values[pos];
int new_val = updates[current_time].new_val;
if (current_l <= pos && pos <= current_r) {
remove(old_val);
add(new_val);
}
swap(values[pos], updates[current_time].new_val);
--current_time;
}
answer[queries[i].id] = answer[0];
}
for (int i = 1; i <= q_count; ++i)
cout << answer[i] << '\n';
return 0;
}
Esse código resolve o problema "Color the Array" (ou similar), um clássico exercício de Mo com atualizações.