Contagem de Inversões via Merge Sort

Para resolver o problema, primeiro é necessário calcular inversões em uma sequência. O algortimo de merge sort modificado abaixo realiza essa contagem eficientemente:

#include<iostream>
#include<vector>
using namespace std;

long contador;

void combinar(vector<int>& seq, int inicio, int meio, int fim) {
    vector<int> temp;
    int i = inicio, j = meio + 1;
    
    while (i <= meio && j <= fim) {
        if (seq[i] <= seq[j]) {
            temp.push_back(seq[i++]);
        } else {
            temp.push_back(seq[j++]);
            contador += meio - i + 1;
        }
    }
    
    while (i <= meio) temp.push_back(seq[i++]);
    while (j <= fim) temp.push_back(seq[j++]);
    
    for (int k = 0; k < temp.size(); k++) {
        seq[inicio + k] = temp[k];
    }
}

void ordenar(vector<int>& seq, int inicio, int fim) {
    if (inicio >= fim) return;
    int meio = inicio + (fim - inicio) / 2;
    ordenar(seq, inicio, meio);
    ordenar(seq, meio + 1, fim);
    combinar(seq, inicio, meio, fim);
}

int main() {
    int n;
    cin >> n;
    vector<int> seq(n);
    for (int i = 0; i < n; i++) cin >> seq[i];
    
    contador = 0;
    ordenar(seq, 0, n - 1);
    cout << contador;
    return 0;
}

Estrutura de Dados para Atualizações Dinâmicas

O problema principal requer operações de troca de elementos adjacentes e consultas sobre inversões após k iterações de bubble sort. Implementamos uma árvore de segmentos para atualizações eficientes:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct No {
    long min, max, soma;
    int esq, dir;
};

vector<No> arvore;
vector<long> inversoes;
vector<int> posicao, idx_original;

void construir(int no, int esq, int dir) {
    arvore[no].esq = esq;
    arvore[no].dir = dir;
    
    if (esq == dir) {
        arvore[no].min = inversoes[esq];
        arvore[no].max = inversoes[esq];
        arvore[no].soma = inversoes[esq];
        return;
    }
    
    int meio = (esq + dir) / 2;
    construir(no*2, esq, meio);
    construir(no*2+1, meio+1, dir);
    
    arvore[no].soma = arvore[no*2].soma + arvore[no*2+1].soma;
    arvore[no].min = min(arvore[no*2].min, arvore[no*2+1].min);
    arvore[no].max = max(arvore[no*2].max, arvore[no*2+1].max);
}

long consultar(int no, int l, int r) {
    if (l > r) return 0;
    if (arvore[no].esq == l && arvore[no].dir == r) {
        return arvore[no].soma;
    }
    
    int meio = (arvore[no].esq + arvore[no].dir) / 2;
    if (r <= meio) return consultar(no*2, l, r);
    if (l > meio) return consultar(no*2+1, l, r);
    return consultar(no*2, l, meio) + consultar(no*2+1, meio+1, r);
}

void atualizar(int no, int pos, long val) {
    if (arvore[no].esq == arvore[no].dir) {
        arvore[no].soma = val;
        arvore[no].min = val;
        arvore[no].max = val;
        return;
    }
    
    int meio = (arvore[no].esq + arvore[no].dir) / 2;
    if (pos <= meio) atualizar(no*2, pos, val);
    else atualizar(no*2+1, pos, val);
    
    arvore[no].soma = arvore[no*2].soma + arvore[no*2+1].soma;
    arvore[no].min = min(arvore[no*2].min, arvore[no*2+1].min);
    arvore[no].max = max(arvore[no*2].max, arvore[no*2+1].max);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    vector<long> valores(n+1);
    inversoes.resize(n+1);
    posicao.resize(n+1);
    idx_original.resize(n+1);
    arvore.resize(4*(n+1));
    
    // Inicialização e pré-processamento
    // ... (cálculo inicial de inversões omitido por brevidade)
    
    construir(1, 1, n);
    
    while (m--) {
        int tipo, k;
        cin >> tipo >> k;
        
        if (tipo == 1) {
            // Lógica de troca de elementos adjacentes
            // ... (atualizações na árvore omitidas por brevidade)
        } else {
            if (k >= arvore[1].max) cout << "0\n";
            else if (k == 0) cout << arvore[1].soma << "\n";
            else {
                // Cálculo do limite para consulta
                long total = consultar(1, k+1, n) - k*(n - k);
                cout << total << "\n";
            }
        }
    }
    return 0;
}