Este artigo aborda uma solução para o problema de calcular o número de pares invertidos em um dado intervalo de uma permutação, com a restrição de que as consultas são online. A abordagem central emprega a técnica de decomposição em blocos (ou raiz quadrada).
Descrição do Problema
Dada uma permutação de comprimento \(n\), responda a \(q\) consultas sobre o número de inversões em um subintervalo \([l, r]\). As consultas são online, o que significa que o resultado da consulta anterior afeta os parâmetros da consulta atual.
- \(1 \le n, q \le 10^5\)
- Limite de tempo: \(750ms\), Limite de memória: \(512MB\).
Metodologia: Decomposição em Blocos
A estratégia para resolver este problema com eficiência é dividir a permutação em blocos de tamanho aproximadamente \(\sqrt{N}\). Para cada índice \(i\), bloco\_id\[i\] indica o número do bloco ao qual ele pertence. inicio\_bloco\[k\] e fim\_bloco\[k\] armazenam os limites de cada bloco \(k\).
Para otimizar o tempo de consulta, diversas informações são pré-calculadas:
elementos\_ordenados\[k\]: Uma lista dos pares(valor, indice\_original)dos elementos no bloco \(k\), ordenados por valor. Esta estrutura é útil para operações de mesclagem e busca binária dentro de um bloco.inversoes\_parcial\_prefixo\[i\]: O número de inversões no intervalo \([inicio\_bloco[bloco\_id[i]], i]\).inversoes\_parcial\_sufixo\[i\]: O número de inversões no intervalo \([i, fim\_bloco[bloco\_id[i]]]\).inversoes\_entre\_blocos\[k1\]\[k2\]: O número de inversões no intervalo que abrange do início do bloco \(k1\) até o final do bloco \(k2\).contagem\_elementos\[k\]\[val\]: A quantidade de elementos com valor menor ou igual avalpresentes nos blocos de 1 até \(k\). Isso permite consultas eficientes sobre elementos menores/maiores que um certo valor em blocos inteiros.
A pré-computação de inversoes\_entre\_blocos\[k1\]\[k2\] pode ser realizada de forma incremental. Uma relação de recorrência possível é: inversoes\_entre\_blocos\[k1\]\[k2\] = inversoes\_entre\_blocos\[k1\]\[k2-1\] + inversoes\_entre\_blocos\[k1+1\]\[k2\] - inversoes\_entre\_blocos\[k1+1\]\[k2-1\] + Contribuição(bloco\[k1\], bloco\[k2\]). A Contribuição(bloco\[k1\], bloco\[k2\]) representa as inversões entre os elementos do bloco \(k1\) e do bloco \(k2\), o que pode ser calculado eficientemente usando uma operação de mesclagem (merge-like) sobre os elementos ordenados de cada bloco.
A função de mesclagem para contar inversões entre dois arrays ordenados é um componente crítico. A implementação eficiente é a seguinte:
inline long long contar_inversoes_merge(int *array_a, int *array_b, int tam_a, int tam_b) {
long long total_inversoes = 0;
int ptr_a = 1;
for (int ptr_b = 1; ptr_b <= tam_b; ++ptr_b) {
while (ptr_a <= tam_a && array_a[ptr_a] <= array_b[ptr_b]) {
ptr_a++;
}
total_inversoes += (long long)(tam_a - ptr_a + 1);
}
return total_inversoes;
}
Esta versão é crucial para a performance, sendo significativamente mais rápida que uma abordagem de dois ponteiros que itera sobre ambos os arrays simultaneamente para construir um novo array mesclado enquanto conta inversões.
Processamento de Consultas
Para uma consulta no intervalo \([L, R]\), a lógica se divide em dois casos principais:
-
Consulta Dentro do Mesmo Bloco (\(bloco\_id[L] == bloco\_id[R]\)):
Se \(L\) e \(R\) estão no mesmo bloco, o cálculo das inversões é feito diretamente. Podemos usar
inversoes\_parcial\_prefixo\[R\] - inversoes\_parcial\_prefixo\[L-1\]para obter as inversões em \([inicio\_bloco[bloco\_id[L]], R]\) menos \([inicio\_bloco[bloco\_id[L]], L-1]\). No entanto, esta diferença remove inversões onde ambos os elementos estão em \([enicio\_bloco[bloco\_id[L]], L-1]\), mas também inversões onde um elemento está em \([inicio\_bloco[bloco\_id[L]], L-1]\) e o outro em \([L, R]\). Para corrigir isso, a contribuição das inversões entre \([inicio\_bloco[bloco\_id[L]], L-1]\) e \([L, R]\) precisa ser subtraída. Esta última parte é calculada on-the-fly usando a funçãocontar\_inversoes\_mergeem sub-arrays temporários construídos a partir dos elementos ordenados do bloco. -
Consulta Abrangendo Múltiplos Blocos (\(bloco\_id[L] \neq bloco\_id[R]\)):
Neste cenário, o intervalo é dividido em três partes:
- **Bloco parcial esquerdo:** \([L, fim\_bloco[bloco\_id[L]]]\).
- **Blocos inteiros do meio:** \([inicio\_bloco[bloco\_id[L]+1], fim\_bloco[bloco\_id[R]-1]]\).
- **Bloco parcial direito:** \([inicio\_bloco[bloco\_id[R]], R]\).
O total de inversões é a soma das inversões internas de cada parte mais as inversões entre as partes:
- **Inversões internas:**
- Inversões no bloco parcial esquerdo:
inversoes\_parcial\_sufixo\[L\]. - Inversões nos blocos inteiros do meio:
inversoes\_entre\_blocos\[bloco\_id\[L\]+1\]\[bloco\_id\[R\]-1\]. - Inversões no bloco parcial direito:
inversoes\_parcial\_prefixo\[R\].
- Inversões no bloco parcial esquerdo:
- **Inversões entre as partes:**
- **Elementos do bloco parcial esquerdo versus blocos inteiros do meio:** Para cada elemento \(p[i]\) no bloco parcial esquerdo \([L, fim\_bloco[bloco\_id[L]]]\), contamos quantos elementos nos blocos do meio são menores que \(p[i]\). Isso é feito eficientemente usando a matriz
contagem\_elementos. - **Blocos inteiros do meio versus elementos do bloco parcial direito:** Similarmente, para cada elemento \(p[j]\) no bloco parcial direito \([inicio\_bloco[bloco\_id[R}], R]\), contamos quantos elementos nos blocos do meio são maiores que \(p[j]\).
- **Elementos do bloco parcial esquerdo versus bloco parcial direito:** Essa contribuição é calculada usando a função
contar\_inversoes\_mergeem sub-arrays temporários contendo os elementos relevantes de cada bloco parcial.
- **Elementos do bloco parcial esquerdo versus blocos inteiros do meio:** Para cada elemento \(p[i]\) no bloco parcial esquerdo \([L, fim\_bloco[bloco\_id[L]]]\), contamos quantos elementos nos blocos do meio são menores que \(p[i]\). Isso é feito eficientemente usando a matriz
A complexidade temporal resultante é de aproximadamente \(\mathcal{O}(N\sqrt{N})\) para pré-computação e \(\mathcal{O}(\sqrt{N})\) por consulta. Embora esta complexidade seja teórica, otimizações de constante são vitais para passar nos limites de tempo rigorosos.
Código Completo
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#define LL long long
#define PRIMEIRO first
#define SEGUNDO second
#define PAR_INT_INT std::pair<int, int>
const int TAM_BLOCO = 320; // Ajustado para otimização de cache/performance
const int NUM_MAX_ELEMENTOS = 100005;
const int NUM_MAX_BLOCOS = NUM_MAX_ELEMENTOS / TAM_BLOCO + 5;
int n_elementos, n_consultas;
int permutacao[NUM_MAX_ELEMENTOS];
int id_bloco[NUM_MAX_ELEMENTOS];
PAR_INT_INT elementos_ordenaveis[NUM_MAX_ELEMENTOS]; // Guarda (valor, indice_original)
// Fenwick Tree (BIT) para contagem de inversões
int arvore_fenwick[NUM_MAX_ELEMENTOS];
// Estruturas de decomposição em blocos
int inicio_bloco[NUM_MAX_BLOCOS];
int fim_bloco[NUM_MAX_BLOCOS];
int tamanho_bloco_atual[NUM_MAX_BLOCOS]; // Número de elementos no bloco (fim - inicio + 1)
int contagem_prefixo_global[NUM_MAX_BLOCOS][NUM_MAX_ELEMENTOS]; // contagem_prefixo_global[k][v] = # de elementos <= v até o bloco k
// Pré-computações de inversões
int inversoes_parcial_prefixo[NUM_MAX_ELEMENTOS]; // Inversões em [inicio_bloco[bloco_id[i]], i]
int inversoes_parcial_sufixo[NUM_MAX_ELEMENTOS]; // Inversões em [i, fim_bloco[bloco_id[i]]]
LL inversoes_entre_blocos[NUM_MAX_BLOCOS][NUM_MAX_BLOCOS]; // Inversões entre bloco k1 e k2
int temp_elementos_bloco[NUM_MAX_ELEMENTOS]; // Array temporário para elementos ordenados de um bloco
// Arrays temporários para a função de merge
int temp_esquerda_merge[TAM_BLOCO + 5];
int temp_direita_merge[TAM_BLOCO + 5];
inline int ler_inteiro() {
int val = 0;
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') {
val = val * 10 + ch - '0';
ch = getchar();
}
return val;
}
inline void escrever_long_long(LL x) {
if (x == 0) {
putchar('0');
return;
}
char buf[20];
int p = 0;
while(x) {
buf[p++] = (x % 10) + '0';
x /= 10;
}
while(p--) {
putchar(buf[p]);
}
}
// Funções da Fenwick Tree
inline void atualizar_fenwick(int indice, int valor) {
while (indice <= n_elementos) {
arvore_fenwick[indice] += valor;
indice += indice & (-indice);
}
}
inline int consultar_fenwick(int indice) {
int resultado = 0;
while (indice > 0) {
resultado += arvore_fenwick[indice];
indice -= indice & (-indice);
}
return resultado;
}
// Conta inversões entre dois arrays ordenados (array_a tem elementos anteriores no índice)
inline LL contar_inversoes_merge(int *array_a, int tam_a, int *array_b, int tam_b) {
LL total_inversoes = 0;
int ptr_a = 1; // 1-indexed
for (int ptr_b = 1; ptr_b <= tam_b; ++ptr_b) {
while (ptr_a <= tam_a && array_a[ptr_a] <= array_b[ptr_b]) {
ptr_a++;
}
total_inversoes += (LL)(tam_a - ptr_a + 1);
}
return total_inversoes;
}
// Obtém a contagem de elementos menores/maiores que 'valor_limite'
// nos blocos de 'bloco_inicio_idx' a 'bloco_fim_idx'
inline int obter_contagem_range(int bloco_inicio_idx, int bloco_fim_idx, int valor_limite, int tipo_contagem) {
// tipo_contagem = 0: conta elementos <= valor_limite (menores ou iguais)
// tipo_contagem = 1: conta elementos > valor_limite (maiores)
int total_na_faixa = contagem_prefixo_global[bloco_fim_idx][n_elementos] - contagem_prefixo_global[bloco_inicio_idx - 1][n_elementos];
int menores_ou_iguais = contagem_prefixo_global[bloco_fim_idx][valor_limite] - contagem_prefixo_global[bloco_inicio_idx - 1][valor_limite];
if (tipo_contagem == 0) {
return menores_ou_iguais;
} else {
return total_na_faixa - menores_ou_iguais;
}
}
int main() {
n_elementos = ler_inteiro();
n_consultas = ler_inteiro();
// Inicializa a permutação e associa elementos aos seus blocos
for (int i = 1; i <= n_elementos; ++i) {
permutacao[i] = ler_inteiro();
elementos_ordenaveis[i] = {permutacao[i], i};
id_bloco[i] = (i - 1) / TAM_BLOCO + 1;
}
int total_blocos = id_bloco[n_elementos];
// Pré-computação para blocos individuais
for (int k = 1; k <= total_blocos; ++k) {
inicio_bloco[k] = (k - 1) * TAM_BLOCO + 1;
fim_bloco[k] = std::min(k * TAM_BLOCO, n_elementos);
tamanho_bloco_atual[k] = fim_bloco[k] - inicio_bloco[k] + 1;
// Calcula inversoes_parcial_prefixo para o bloco
for (int i = inicio_bloco[k]; i <= fim_bloco[k]; ++i) {
if (i != inicio_bloco[k]) {
inversoes_parcial_prefixo[i] = inversoes_parcial_prefixo[i - 1] + (consultar_fenwick(n_elementos) - consultar_fenwick(permutacao[i]));
} else {
inversoes_parcial_prefixo[i] = 0;
}
atualizar_fenwick(permutacao[i], 1);
}
// Limpa Fenwick Tree para o próximo bloco
for (int i = inicio_bloco[k]; i <= fim_bloco[k]; ++i) {
atualizar_fenwick(permutacao[i], -1);
}
// Calcula inversoes_parcial_sufixo para o bloco
for (int i = fim_bloco[k]; i >= inicio_bloco[k]; --i) {
if (i != fim_bloco[k]) {
inversoes_parcial_sufixo[i] = inversoes_parcial_sufixo[i + 1] + consultar_fenwick(permutacao[i] - 1);
} else {
inversoes_parcial_sufixo[i] = 0;
}
atualizar_fenwick(permutacao[i], 1);
}
// Limpa Fenwick Tree
for (int i = inicio_bloco[k]; i <= fim_bloco[k]; ++i) {
atualizar_fenwick(permutacao[i], -1);
}
// Ordena elementos_ordenaveis dentro de cada bloco
std::sort(elementos_ordenaveis + inicio_bloco[k], elementos_ordenaveis + fim_bloco[k] + 1);
for(int i = inicio_bloco[k]; i <= fim_bloco[k]; ++i) {
temp_elementos_bloco[i] = elementos_ordenaveis[i].PRIMEIRO;
}
}
// Pré-computação de inversoes_entre_blocos
// Primeiro, os blocos internos
for (int k = 1; k <= total_blocos; ++k) {
inversoes_entre_blocos[k][k] = inversoes_parcial_prefixo[fim_bloco[k]]; // Total de inversões dentro do bloco
}
// Agora, para blocos adjacentes e estendidos
for (int len_blocos = 2; len_blocos <= total_blocos; ++len_blocos) {
for (int k_esq = 1; k_esq <= total_blocos - len_blocos + 1; ++k_esq) {
int k_dir = k_esq + len_blocos - 1;
inversoes_entre_blocos[k_esq][k_dir] = inversoes_entre_blocos[k_esq][k_dir - 1] +
inversoes_entre_blocos[k_esq + 1][k_dir] -
inversoes_entre_blocos[k_esq + 1][k_dir - 1] +
contar_inversoes_merge(
temp_elementos_bloco + inicio_bloco[k_esq],
tamanho_bloco_atual[k_esq],
temp_elementos_bloco + inicio_bloco[k_dir],
tamanho_bloco_atual[k_dir]
);
}
}
// Pré-computação de contagem_prefixo_global
for (int k = 1; k <= total_blocos; ++k) {
for (int j = 1; j <= n_elementos; ++j) {
contagem_prefixo_global[k][j] = contagem_prefixo_global[k-1][j];
}
for (int i = inicio_bloco[k]; i <= fim_bloco[k]; ++i) {
contagem_prefixo_global[k][permutacao[i]]++;
}
for (int j = 1; j <= n_elementos; ++j) {
contagem_prefixo_global[k][j] += contagem_prefixo_global[k][j-1];
}
}
LL ultimo_resultado = 0;
while (n_consultas--) {
int l = ler_inteiro() ^ ultimo_resultado;
int r = ler_inteiro() ^ ultimo_resultado;
int id_bloco_l = id_bloco[l];
int id_bloco_r = id_bloco[r];
LL resultado_atual = 0;
if (id_bloco_l == id_bloco_r) {
// Caso 1: L e R no mesmo bloco
// Usamos Fenwick Tree para calcular inversões on-the-fly de forma precisa
// Isso é mais fácil do que lidar com inversoes_parcial_prefixo e merge para esse caso.
int idx_temp_e = 0;
int idx_temp_d = 0;
for(int i = inicio_bloco[id_bloco_l]; i <= fim_bloco[id_bloco_l]; ++i) {
if(elementos_ordenaveis[i].SEGUNDO >= l && elementos_ordenaveis[i].SEGUNDO <= r) {
temp_esquerda_merge[++idx_temp_e] = elementos_ordenaveis[i].PRIMEIRO;
}
}
// Aqui, a lógica é diferente do merge tradicional para inversões.
// Para (i,j) ser uma inversão em [L, R], i < j e p[i] > p[j].
// Itera e usa BIT para contar.
for(int i = 1; i <= idx_temp_e; ++i) {
resultado_atual += consultar_fenwick(n_elementos) - consultar_fenwick(temp_esquerda_merge[i]);
atualizar_fenwick(temp_esquerda_merge[i], 1);
}
for(int i = 1; i <= idx_temp_e; ++i) {
atualizar_fenwick(temp_esquerda_merge[i], -1);
}
} else {
// Caso 2: L e R em blocos diferentes
resultado_atual = inversoes_parcial_sufixo[l] + inversoes_entre_blocos[id_bloco_l + 1][id_bloco_r - 1] + inversoes_parcial_prefixo[r];
// Inversões entre o bloco parcial esquerdo e os blocos centrais
for (int i = l; i <= fim_bloco[id_bloco_l]; ++i) {
resultado_atual += obter_contagem_range(id_bloco_l + 1, id_bloco_r - 1, permutacao[i], 0); // Conta menores ou iguais
}
// Inversões entre os blocos centrais e o bloco parcial direito
for (int i = inicio_bloco[id_bloco_r]; i <= r; ++i) {
resultado_atual += obter_contagem_range(id_bloco_l + 1, id_bloco_r - 1, permutacao[i], 1); // Conta maiores
}
// Inversões entre o bloco parcial esquerdo e o bloco parcial direito
int idx_temp_e = 0;
for (int i = inicio_bloco[id_bloco_l]; i <= fim_bloco[id_bloco_l]; ++i) {
if (elementos_ordenaveis[i].SEGUNDO >= l) {
temp_esquerda_merge[++idx_temp_e] = elementos_ordenaveis[i].PRIMEIRO;
}
}
int idx_temp_d = 0;
for (int i = inicio_bloco[id_bloco_r]; i <= fim_bloco[id_bloco_r]; ++i) {
if (elementos_ordenaveis[i].SEGUNDO <= r) {
temp_direita_merge[++idx_temp_d] = elementos_ordenaveis[i].PRIMEIRO;
}
}
resultado_atual += contar_inversoes_merge(temp_esquerda_merge, idx_temp_e, temp_direita_merge, idx_temp_d);
}
ultimo_resultado = resultado_atual;
escrever_long_long(ultimo_resultado);
putchar('\n');
}
return 0;
}