O algoritmo Bubble Sort é um método de ordenação simples, cuja eficiência está intrinsecamente ligada ao número de trocas realizadas. O problema em questão nos desafia a construir uma sequência de inteiros não negativos de comprimento n que minimize o número total de trocas durante a execução do Bubble Sort, sujeito a m condições adicionais. Cada condição i especifica que o valor mínimo no subintervalo a[L_i...R_i] deve ser exatamente V_i.

Pseudocódigo do Bubble Sort e Definição de Trocas

O Bubble Sort funciona repetidamente percorrendo a lista, comparando pares de elementos adjacentes e trocando-os se estiverem na ordem errada. Uma única passagem através da lista garante que o maior elemento "borbulhe" para sua posição correta. O pseudocódigo é o seguinte:

Entrada: Uma sequência a[1...n] de comprimento n
Saída: a ordenada em ordem crescente
para i = 1 até n faça:
    para j = 1 até n - 1 faça:
        se (a[j] > a[j + 1]) então:
            trocar a[j] com a[j + 1]

O número de trocas do Bubble Sort é definido como a quantidade de vezes que a sexta linha do pseudocódigo (a operação de troca) é executada. É um fato bem conhecido que o número de trocas no Bubble Sort é igual ao número de inversões na sequência de entrada. Uma inversão é um par de índices (i, j) tal que i < j e a[i] > a[j]. Assim, o problema se resume a minimizar o número de inversões na sequência final a.

Propriedades Fundamentais

1. Os valores na sequência final a serão derivados dos valores V_i fornecidos nas restrições. Qualquer número que não seja um V_i pode ser ajustado para um V_i sem aumentar o número de inversões ou quebrar as restrições.
2. A minimização das trocas é equivalente à minimização do número de inversões.

Estratégia de Solução

A solução pode ser dividida em várias fases:

1. Discretização de Valores: Reduzir o intervalo dos valores V_i únicos para facilitar o uso em estruturas de dados como Segment Trees e Fenwick Trees.
2. Cálculo dos Limites Inferiores por Posição: Determinar para cada posição i o menor valor limite_inferior[i] que a[i] pode assumir para satisfazer todas as restrições de mínimo que o abrangem.
3. Fixação de Valores Obrigatórios: Identificar e fixar as posições a[k] que devem obrigatoriamente assumir um valor V_i para satisfazer as restrições de intervalo [L_i, R_i].
4. Preenchimento da Sequência e Contagem de Inversões: Preencher os valores restantes em a e, simultaneamente, manter um registro do número de inversões acumuladas usando uma Segment Tree.
5. Cálculo Final das Inversões: Calcular o número total de inversões na sequência a completamente construída usando uma Fenwick Tree (BIT).

Fase 1: Discretização de Valores

Para otimizar o uso de memória e tempo em estruturas de dados baseadas em índices de valor, todos os valores V_i são coletados, ordenados e mapeados para índices contínuos 1, ..., num_valores_distintos. Isso garante que as operações em intervalos de valores sejam eficientes.

Fase 2: Cálculo dos Limites Inferiores por Posição (limite_inferior[])

Para cada posição i na sequência, limite_inferior[i] representa o menor valor possível que a[i] pode assumir. Isso é determinado pelo maior V_j de todas as restrições (L_j, R_j, V_j) que incluem a posição i. Se a[i] faz parte de múltiplas restrições de mínimo, ele deve ser pelo menos o maior desses mínimos exigidos.

Para calcular limite_inferior[] eficientemente, as restrições são processadas em ordem decrescente dos seus valores V_j (já discretizados). Uma estrutura de conjunto (std::set) é usada para manter as posições ainda não atribuídas. Para cada restrição (L_j, R_j, V_j), todas as posições k em [L_j, R_j] que ainda não têm um limite_inferior definido recebem V_j como seu limite_inferior e são removidas do conjunto de posições disponíveis. Isso garante que limite_inferior[k] receba o maior V_j aplicável.

Fase 3: Fixando Valores Obrigatórios (sequencia_a[])

Cada restrição (L_i, R_i, V_i) exige que pelo menos uma posição k dentro de [L_i, R_i] tenha sequencia_a[k] = V_i. Para satisfazer isso, usamos uma estratégia gulosa:

• As restrições são ordenadas em ordem decrescente de L_i (o início do intervalo). Isso significa que as restrições que começam mais à direita são processadas primeiro.

• Para cada valor V discretizado, mantemos dois conjuntos de posições: posicoes_disponiveis[V] contém posições k onde limite_inferior[k] == V e sequencia_a[k] ainda não foi fixado. posicoes_fixadas[V] contém posições k onde sequencia_a[k] já foi definido como V.

• Ao processar uma restrição (L_i, R_i, V_i):

  1. Primeiro, verificamos se já existe uma posição k em posicoes_fixadas[V_i] dentro de [L_i, R_i]. Se sim, esta restrição já está satisfeita e podemos ignorá-la.
  2. Caso contrário, precisamos fixar uma posição. Buscamos a posição k em posicoes_disponiveis[V_i] que seja a menor possível (mais à esquerda) e esteja dentro do intervalo [L_i, R_i]. Se tal posição k for encontrada, definimos sequencia_a[k] = V_i, movemos k de posicoes_disponiveis[V_i] para posicoes_fixadas[V_i].
  3. Se nenhuma posição puder ser encontrada para satisfazer a restrição, a tarefa é impossível, e imprimimos "-1".

  Essa escolha gulosa de fixar o valor no ponto mais à esquerda que respeita o limite inferior e ainda não foi usado, quando as restrições são processadas da direita para a esquerda, é ideal para minimizar o impacto nas inversões para elementos à sua esquerda.

Fase 4: Preenchimento da Sequência e Contagem de Inversões

Após fixar os valores obrigatórios, ainda pode haver posições a[i] que são -1. O objetivo agora é preencher essas posições e calcular o número de inversões de forma otimizada. Usamos uma Segment Tree para isso.

A Segment Tree armazena em cada nó o par (custo_acumulado, valor). O custo_acumulado representa a soma das inversões formadas com os elementos já escolhidos anteriormente. O valor é o valor discretizado que minimiza este custo para aquela faixa.

Inicialmente, a Segment Tree é construída com todos os valores possíveis, cada um com custo 0. Em seguida, percorremos a sequência i de 1 a n:

• **Se sequencia_a[i] já está fixado:**Denotemos sequencia_a[i] por X. Este X foi escolhido na posição i. Para qualquer posição futura j > i:

  • Se escolhermos um valor Y < X para sequencia_a[j], formamos uma inversão (X, Y). Para refletir isso, adicionamos +1 ao custo de todos os valores k < X na Segment Tree.
  • Se escolhermos um valor Y > X para sequencia_a[j], não formamos uma inversão (X, Y). O "custo" de não formar uma inversão é, em comparação, melhor do que formar uma. No contexto de minimização de inversões, isso pode ser modelado subtraindo -1 do custo de todos os valores k > X na Segment Tree. Esta operação incentiva a escolha de valores maiores que X em posições futuras para evitar inversões com X, ou, de forma equivalente, valores menores têm um custo aumentado.

  As atualizações são realizadas na Segment Tree usando operações de lazy propagation em intervalos:

  // O 'valor' X é escolhido
  arvore_segmentos.atualizar_intervalo(1, 1, num_valores_distintos, sequencia_a[i] + 1, num_valores_distintos, 1); // Aumenta o custo para valores maiores que X
  arvore_segmentos.atualizar_intervalo(1, 1, num_valores_distintos, 1, sequencia_a[i] - 1, -1); // Diminui o custo para valores menores que X
  
  

• **Se sequencia_a[i] não está fixado (é -1):**Precisamos escolher um valor para sequencia_a[i] que minimize o custo atual e respeite o limite_inferior[i]. Consultamos a Segment Tree no intervalo [limite_inferior[i], num_valores_distintos] para encontrar o par (custo_minimo, valor_escolhido). Definimos sequencia_a[i] = valor_escolhido. Em seguida, aplicamos as mesmas atualizações na Segment Tree descritas acima para o valor valor_escolhido.

Fase 5: Cálculo Final das Inversões

Uma vez que todos os valores de sequencia_a[] foram determinados, o número total de inversões é calculado usando uma Fenwick Tree (BIT). Iteramos por sequencia_a[i] de 1 a n. Para cada sequencia_a[i], consultamos a BIT para contar quantos números maiores que sequencia_a[i] já foram adicionados (e, portanto, apareceram antes de i). Este é o número de inversões que sequencia_a[i] forma com elementos à sua esquerda. Em seguida, adicionamos sequencia_a[i] à BIT.

ArvoreIndexada arvore_indexada_bit; // Fenwick Tree
long long inversao_total = 0;
for (int i = 1; i <= tamanho_n; ++i) {
    // Conta elementos maiores que sequencia_a[i] já processados (total de elementos - elementos <= sequencia_a[i])
    inversao_total += arvore_indexada_bit.consultar(num_valores_distintos) - arvore_indexada_bit.consultar(sequencia_a[i]);
    arvore_indexada_bit.atualizar(sequencia_a[i], 1); // Adiciona sequencia_a[i] à BIT
}

Complexidade

A discretização, cálculo dos limites inferiores e fixação de valores obrigatórios envolvem operações de ordenação e uso de std::set, resultando em uma complexidade de O(M log M + N log N) ou O((N+M) log N). As operações da Segment Tree e da Fenwick Tree são O(log N). Como há N iterações para preencher a sequência, esta fase contribui com O(N log N). A fase final de contagem de inversões também é O(N log N). A complexidade geral é O((N+M) log N).

Implementação em C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map> // Para discretização, se não houver array unq

// Definir int como long long para evitar overflow em somas de inversões
#define int long long

const int K_MAX_N = 1e6 + 5; // Tamanho máximo de N

int tamanho_n, num_restricoes_m, num_valores_distintos;
int inversao_total; // Armazena a resposta final
int sequencia_a[K_MAX_N]; // A sequência a ser construída
int limite_inferior_posicao[K_MAX_N]; // limite_inferior[i] = menor valor que a[i] pode ter
int restricao_l[K_MAX_N], restricao_r[K_MAX_N], restricao_v[K_MAX_N]; // Detalhes das restrições
int valores_unicos[K_MAX_N]; // Array para discretização

// Conjuntos para a fase de fixação de valores obrigatórios
// posicoes_disponiveis[v_discretizado] = posições i onde limite_inferior[i] == v_discretizado e sequencia_a[i] ainda não foi fixado
std::set<int> posicoes_disponiveis[K_MAX_N];
// posicoes_fixadas[v_discretizado] = posições i onde sequencia_a[i] já foi fixado como v_discretizado
std::set<int> posicoes_fixadas[K_MAX_N];

// Estrutura para Fenwick Tree (BIT)
struct ArvoreIndexada {
    int valores[K_MAX_N];

    void limpar() { std::fill_n(valores + 1, num_valores_distintos + 1, 0); } // Limpa a árvore

    // Adiciona 'delta' ao índice 'idx'
    void atualizar(int idx, int delta) {
        for (; idx <= num_valores_distintos; idx += idx & -idx) {
            valores[idx] += delta;
        }
    }

    // Consulta a soma prefixa até 'idx'
    int consultar(int idx) {
        int soma = 0;
        for (; idx > 0; idx -= idx & -idx) {
            soma += valores[idx];
        }
        return soma;
    }
};

ArvoreIndexada arvore_indexada_bit; // Instância global da Fenwick Tree

// Estrutura para Segment Tree
struct ArvoreSegmentos {
    // no_min[x] = {custo_minimo, valor_que_atinge_custo_minimo}
    std::pair<int int=""> no_min[K_MAX_N * 4];
    int tag_lazy[K_MAX_N * 4]; // Para lazy propagation (soma a um intervalo)

    // Propaga o mínimo para cima
    void propagar_acima(int indice_no) {
        no_min[indice_no] = std::min(no_min[indice_no * 2], no_min[indice_no * 2 + 1]);
    }

    // Adiciona um valor à tag e ao custo do nó
    void aplicar_tag(int indice_no, int valor_add) {
        no_min[indice_no].first += valor_add;
        tag_lazy[indice_no] += valor_add;
    }

    // Propaga a tag lazy para os filhos
    void propagar_abaixo(int indice_no) {
        if (tag_lazy[indice_no] != 0) {
            aplicar_tag(indice_no * 2, tag_lazy[indice_no]);
            aplicar_tag(indice_no * 2 + 1, tag_lazy[indice_no]);
            tag_lazy[indice_no] = 0; // Reseta a tag
        }
    }

    // Constrói a Segment Tree
    void construir(int indice_no, int inicio, int fim) {
        no_min[indice_no] = {0, inicio}; // Custo inicial 0, valor é o próprio índice
        tag_lazy[indice_no] = 0;
        if (inicio == fim) return;
        int meio = (inicio + fim) / 2;
        construir(indice_no * 2, inicio, meio);
        construir(indice_no * 2 + 1, meio + 1, fim);
    }

    // Atualiza um intervalo [query_l, query_r] com 'valor_add'
    void atualizar_intervalo(int indice_no, int inicio, int fim, int query_l, int query_r, int valor_add) {
        if (inicio > query_r || fim < query_l) return; // Fora do intervalo
        if (inicio >= query_l && fim <= query_r) { // Intervalo completamente contido
            return aplicar_tag(indice_no, valor_add);
        }
        propagar_abaixo(indice_no); // Propaga tags antes de descer
        int meio = (inicio + fim) / 2;
        atualizar_intervalo(indice_no * 2, inicio, meio, query_l, query_r, valor_add);
        atualizar_intervalo(indice_no * 2 + 1, meio + 1, fim, query_l, query_r, valor_add);
        propagar_acima(indice_no); // Recomputa o mínimo
    }

    // Consulta o mínimo em um intervalo [query_l, query_r]
    std::pair<int int=""> consultar_intervalo(int indice_no, int inicio, int fim, int query_l, int query_r) {
        if (inicio > query_r || fim < query_l) return {(int)1e18, 0}; // Valor sentinel para 'infinito' (para long long)
        if (inicio >= query_l && fim <= query_r) { // Intervalo completamente contido
            return no_min[indice_no];
        }
        propagar_abaixo(indice_no); // Propaga tags antes de descer
        int meio = (inicio + fim) / 2;
        return std::min(consultar_intervalo(indice_no * 2, inicio, meio, query_l, query_r),
                        consultar_intervalo(indice_no * 2 + 1, meio + 1, fim, query_l, query_r));
    }
};

ArvoreSegmentos arvore_segmentos; // Instância global da Segment Tree

// Função para discretizar os valores V_i
void discretizar_valores() {
    for (int i = 1; i <= num_restricoes_m; ++i) {
        valores_unicos[i] = restricao_v[i];
    }
    std::sort(valores_unicos + 1, valores_unicos + 1 + num_restricoes_m);
    num_valores_distintos = std::unique(valores_unicos + 1, valores_unicos + 1 + num_restricoes_m) - (valores_unicos + 1);
    for (int i = 1; i <= num_restricoes_m; ++i) {
        restricao_v[i] = std::lower_bound(valores_unicos + 1, valores_unicos + 1 + num_valores_distintos, restricao_v[i]) - valores_unicos;
    }
}

// Função para calcular limite_inferior_posicao[i]
void calcular_limites_inferiores() {
    std::vector<int> indices_restricoes_para_lim(num_restricoes_m);
    for (int i = 0; i < num_restricoes_m; ++i) {
        indices_restricoes_para_lim[i] = i + 1; // Armazena índices originais de 1 a m
    }
    // Ordenar restrições por V_i decrescente (já discretizado)
    std::sort(indices_restricoes_para_lim.begin(), indices_restricoes_para_lim.end(), [&](int i, int j) {
        return restricao_v[i] > restricao_v[j];
    });

    std::set<int> posicoes_nao_atribuidas; // Posições sem limite_inferior_posicao definido
    for (int i = 1; i <= tamanho_n; ++i) {
        posicoes_nao_atribuidas.emplace(i);
        limite_inferior_posicao[i] = 1; // Valor mínimo (discretizado) padrão
    }

    for (int idx_restricao : indices_restricoes_para_lim) {
        int L = restricao_l[idx_restricao];
        int R = restricao_r[idx_restricao];
        int V_discretizado = restricao_v[idx_restricao];

        // Itera sobre as posições no intervalo [L, R] que ainda não foram atribuídas
        // A iteração com set::lower_bound e erase é eficiente
        auto it = posicoes_nao_atribuidas.lower_bound(L);
        while (it != posicoes_nao_atribuidas.end() && *it <= R) {
            limite_inferior_posicao[*it] = V_discretizado;
            it = posicoes_nao_atribuidas.erase(it); // Remove e avança o iterador
        }
    }
}

// Função principal que resolve um caso de teste
void resolver_caso_teste() {
    std::cin >> tamanho_n >> num_restricoes_m;

    // Inicializa a sequencia_a com -1 (não fixado)
    std::fill_n(sequencia_a + 1, tamanho_n, -1);
    // Limite inferior padrão (1º valor discretizado)
    // std::fill_n(limite_inferior_posicao + 1, tamanho_n, 1); // Feito em calcular_limites_inferiores

    for (int i = 1; i <= num_restricoes_m; ++i) {
        std::cin >> restricao_l[i] >> restricao_r[i] >> restricao_v[i];
    }

    discretizar_valores();
    calcular_limites_inferiores();
    
    // Para a fase de fixação de valores obrigatórios
    // Vector para armazenar os índices das restrições para ordenação
    std::vector<int> indices_restricoes_para_fixar(num_restricoes_m);
    for (int i = 0; i < num_restricoes_m; ++i) {
        indices_restricoes_para_fixar[i] = i + 1;
    }
    // Ordenar restrições por L_i decrescente
    std::sort(indices_restricoes_para_fixar.begin(), indices_restricoes_para_fixar.end(), [&](int i, int j) {
        return restricao_l[i] > restricao_l[j];
    });

    // Limpa os conjuntos de posições para cada valor discretizado
    for (int i = 1; i <= num_valores_distintos; ++i) {
        posicoes_disponiveis[i].clear();
        posicoes_fixadas[i].clear();
    }

    // Preenche posicoes_disponiveis com base nos limites inferiores calculados
    for (int i = 1; i <= tamanho_n; ++i) {
        posicoes_disponiveis[limite_inferior_posicao[i]].emplace(i);
    }

    // Processa as restrições para fixar os valores obrigatórios
    for (int idx_restricao : indices_restricoes_para_fixar) {
        int L = restricao_l[idx_restricao];
        int R = restricao_r[idx_restricao];
        int V_discretizado = restricao_v[idx_restricao];

        // Verifica se a restrição já foi satisfeita por um valor fixado
        auto it_fixado = posicoes_fixadas[V_discretizado].lower_bound(L);
        if (it_fixado != posicoes_fixadas[V_discretizado].end() && *it_fixado <= R) {
            continue; // Já satisfeito
        }

        // Tenta fixar um valor: encontra a posição mais à esquerda possível no intervalo [L, R]
        // que ainda não foi fixada e cujo limite_inferior_posicao é V_discretizado.
        auto it_disponivel = posicoes_disponiveis[V_discretizado].lower_bound(L);
        if (it_disponivel != posicoes_disponiveis[V_discretizado].end() && *it_disponivel <= R) {
            sequencia_a[*it_disponivel] = V_discretizado; // Fixa o valor
            posicoes_fixadas[V_discretizado].emplace(*it_disponivel); // Move para fixados
            posicoes_disponiveis[V_discretizado].erase(it_disponivel); // Remove dos disponíveis
        } else {
            // Impossível satisfazer a restrição
            std::cout << "-1\n";
            return;
        }
    }

    // Fase de preenchimento e contagem de inversões com Segment Tree
    arvore_segmentos.construir(1, 1, num_valores_distintos); // Constrói a Segment Tree

    // Inicializa a Segment Tree com os valores já fixados
    for (int i = 1; i <= tamanho_n; ++i) {
        if (sequencia_a[i] != -1) { // Se a[i] já foi fixado
            // Atualiza o custo para futuros elementos
            arvore_segmentos.atualizar_intervalo(1, 1, num_valores_distintos, sequencia_a[i] + 1, num_valores_distintos, 1);
            arvore_segmentos.atualizar_intervalo(1, 1, num_valores_distintos, 1, sequencia_a[i] - 1, -1);
        }
    }

    for (int i = 1; i <= tamanho_n; ++i) {
        if (sequencia_a[i] == -1) { // Se a[i] ainda não foi fixado
            // Consulta a Segment Tree para o valor ótimo no intervalo [limite_inferior_posicao[i], num_valores_distintos]
            // Escolhe o valor com o menor custo acumulado.
            sequencia_a[i] = arvore_segmentos.consultar_intervalo(1, 1, num_valores_distintos, limite_inferior_posicao[i], num_valores_distintos).second;
            
            // Aplica as atualizações na Segment Tree para o valor escolhido
            arvore_segmentos.atualizar_intervalo(1, 1, num_valores_distintos, sequencia_a[i] + 1, num_valores_distintos, 1);
            arvore_segmentos.atualizar_intervalo(1, 1, num_valores_distintos, 1, sequencia_a[i] - 1, -1);
        }
    }

    // Fase final: Contagem total de inversões com Fenwick Tree
    arvore_indexada_bit.limpar(); // Limpa a Fenwick Tree
    inversao_total = 0;
    for (int i = 1; i <= tamanho_n; ++i) {
        // Quantidade de elementos já inseridos (à esquerda de 'i') que são maiores que sequencia_a[i]
        inversao_total += arvore_indexada_bit.consultar(num_valores_distintos) - arvore_indexada_bit.consultar(sequencia_a[i]);
        arvore_indexada_bit.atualizar(sequencia_a[i], 1); // Adiciona sequencia_a[i] à Fenwick Tree
    }

    std::cout << inversao_total << '\n';
}

int32_t main() {
    // Configurações para I/O rápido
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int num_testes = 1;
    std::cin >> num_testes;
    while (num_testes--) {
        resolver_caso_teste();
    }

    return 0;
}
</int></int></int></int></int></int></int>