문제 개요

길이가 \(n\)인 순열 \(a\)가 주어진다. 두 원소를 교환할 때마다 역순 쌍의 개수를 2로 나눈 나머지를 출력해야 한다.

입력 형식
첫 번째 줄에는 양의 정수 \(n\)이 주어진다.
두 번째 줄에는 순열 \(a\)를 구성하는 \(n\)개의 숫자가 주어진다.
세 번째 줄에는 질의 수 \(q\)가 주어진다.
다음 \(q\)줄에는 각각 두 개의 양의 정수가 주어지며, 이는 \(a_i\)와 \(a_j\)를 교환함을 의미한다.

출력 형식
총 \(q\)줄에 걸쳐 각 교환 후의 역순 쌍 개수를 2로 나눈 나머지를 출력한다.

예제

[입력 예시 1]

4
1 2 3 4
2
1 2
1 2

[출력 예시 1]

1
0

[입력 예시 2]

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

[출력 예시 2]

0
1
1
1
1
0
0
1
0
1

모든 테스트 케이스에서 \(n,q \le 100000\)이다.

해결 전략

우선 초기 상태의 역순 쌍 수를 계산해야 하며, 이때 Binary Indexed Tree(Fenwick Tree)를 활용한다. 기본 아이디어는 모든 수를 내림차순으로 정렬한 뒤, 위치 순서대로 BIT에 삽입하면서 현재 수보다 앞쪽에 있는 더 큰 수들의 개수를 세는 것이다. 단, 값이 같은 경우는 역순 쌍으로 간주하지 않으므로 위치 기준 내림차순으로 추가 정렬해야 한다.

중요한 점은 문제에서 요구하는 것이 역순 쌍의 정확한 개수가 아니라 그 짝수/홀수 여부라는 것이다. 이는 특정 규칙이 있음을 암시하며, 교환 연산이 역순 쌍의 홀짝성에 어떤 영향을 미치는지 분석하는 것이 핵심이다.

교환 연산 시, 교환되는 두 원소 사이 구간 외의 역순 쌍은 변하지 않는다. 왜냐하면 상대적인 위치가 유지되기 때문이다. 교환되는 두 원소 자체는 서로 다른 값을 가질 경우 반드시 역순 쌍 수에 1만큼의 변화를 주게 되며, 그 사이에 있는 원소들 중 두 값 사이에 위치한 원소들은 역순 쌍 수에 2씩 기여하므로 홀짝성에는 영향을 주지 않는다. 따라서 결론적으로 서로 다른 두 원소를 교환할 때마다 역순 쌍의 홀짝성이 바뀐다.

핵심 구현 코드

#include <bits/stdc++.h>
using namespace std;

#define VALUE first
#define INDEX second

typedef long long ll;
typedef pair<int,int> pii;

const int MAX_N = 100010;
int n, sequence[MAX_N], queries;
ll inversion_count;
pii elements[MAX_N];
int fenwick_tree[MAX_N];

bool descending_compare(pii current, pii next) {
    if(current.VALUE == next.VALUE) 
        return current.INDEX > next.INDEX;
    return current.VALUE > next.VALUE;
}

int get_prefix_sum(int position) {
    int result = 0;
    for(; position; position -= (position & (-position)))
        result += fenwick_tree[position];
    return result;
}

int update_and_query(int position) {
    int prefix_count = get_prefix_sum(position - 1);
    for(; position <= n; position += (position & (-position)))
        fenwick_tree[position]++;
    return prefix_count;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> sequence[i];
        elements[i] = {sequence[i], i};
    }
    
    sort(elements + 1, elements + n + 1, descending_compare);
    
    for(int i = 1; i <= n; ++i)
        inversion_count += update_and_query(elements[i].INDEX);
    
    inversion_count &= 1;
    
    cin >> queries;
    for(int i = 0, x, y; i < queries; ++i) {
        cin >> x >> y;
        if(sequence[x] != sequence[y]) 
            inversion_count ^= 1;
        cout << inversion_count << '\n';
    }
    
    return 0;
}