Dada uma permutação de tamanho n, precisamos processar q operações de troca entre dois elementos. Após cada troca, determinamos o número total de inversões na permutação módulo 2.

Formato de Entrada
A primeira linha contém o inteiro n.
A segunda linha contém n enteiros, representando a permutação inicial.
A terceira linha contém o inteiro q.
As q linhas seguintes contêm pares de inteiros i e j, indicando a troca entre as posições i e j.

Formato de Saída
Para cada operação, imprima uma linha com o resultado: o número de inversões módulo 2 após a troca.

Exemplo 1

Entrada:
4
1 2 3 4
2
1 2
1 2

Saída:
1
0

Exemplo 2

Entrada:
8
4 1 5 2 6 8 7 3
10
6 4
7 8
2 2
1 1
7 7
1 7
3 3
2 4
2 6
5 7

Saída:
0
1
1
1
1
0
0
1
0
1

Restrições
Para 100% dos casos, n, q ≤ 100000.

Abordagem Técnica

Inicialmente, calculamos a paridade do número de inversões na permutação original. Utiliza-se uma árvore de Fenwick para isso, processando os elementos em ordem decrescente de valor e, para valores iguais, em ordem decrescente de posição. Ao inserir cada posição na estrutura, contamos quantas posições menores já foram adicionadas, acumulando o total de inversões.

Ao considerar uma troca entre dois elementos distintos, a paridade do número de inversões é sempre invertida. Isso ocorre porque a alteração nas inversões envolvendo o par trocado contribui com uma mudança ímpar, enquanto as inversões com elementos intermediários sofrem mudanças pares, não afetando a paridade. Portanto, basta verificar se os valores trocados são diferentes para determinar se a paridade muda.

Desta forma, a solução eficiente consiste em: calcular a paridade inicial uma única vez; para cada consulta, se os valores nas posições fornecidos forem distintos, inverte-se a paridade corrente.

Implementação em C++

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

const int LIMITE = 100005;
int arr[LIMITE];
int BIT[LIMITE];
int tamanho;

struct Par {
    int valor;
    int indice;
};

bool comparar(const Par &a, const Par &b) {
    if (a.valor != b.valor) return a.valor > b.valor;
    return a.indice > b.indice;
}

int consulta(int pos) {
    int res = 0;
    for (int i = pos; i > 0; i -= i & -i) {
        res += BIT[i];
    }
    return res;
}

void atualiza(int pos) {
    for (int i = pos; i <= tamanho; i += i & -i) {
        BIT[i]++;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> tamanho;
    vector<Par> elementos(tamanho);
    for (int i = 1; i <= tamanho; ++i) {
        cin >> arr[i];
        elementos[i-1] = {arr[i], i};
    }

    sort(elementos.begin(), elementos.end(), comparar);
    long long total = 0;
    for (const auto &elem : elementos) {
        total += consulta(elem.indice - 1);
        atualiza(elem.indice);
    }
    int paridade = total & 1;

    int consultas;
    cin >> consultas;
    while (consultas--) {
        int x, y;
        cin >> x >> y;
        if (arr[x] != arr[y]) {
            paridade ^= 1;
        }
        cout << paridade << '\n';
    }

    return 0;
}

O código acima calcula a paridade inicial das inversões usando uma árvore de Fenwick e, em seguida, para cada operação de troca, atualiza a paridade conforme necessário.