CF 785E Anton and Permutation

문제

• 링크 - http://codeforces.com/problemset/problem/785/E

문제 풀이

순열 \(a[ \ ] = \{1, 2, ..., n\} \ (1 \le n \le 200000)\) 에 대하여 특정 위치 \(l_i\) 과 \(r_i\) 의 값을 바꾸는 연산이 \(q \ (1 \le q \le 50000)\) 번 수행될 때, 매 연산 후 순열에 존재하는 역접(inversion)의 수를 세는 문제다. 

역접의 수는 크기가 \(a[x] > a[y] \ (x < y)\)인 쌍 \((x, y)\)의 수를 세는 것이므로, 간단하게 모든 원소에 대해서 자신보다 앞에 있으면서 큰 원소의 개수를 일일히 다 세서 구할 수 있다. 하지만 전체 시간복잡도 \(O(q \times n^2)\)가 예상되므로 문제를 주어진 제한시간내에 해결하기에는 크게 역부족인 방법이다.

매 연산 후, 역접의 수가 어떻게 변하는지를 관찰하면 보다 효율적인 방법이 나온다. 현재 순열의 상태가 다음과 같다고 하자.

현재 순열에서 역접의 수는 7이다. 이때, 다음 연산으로 4와 7의 위치가 변경된 후 역접의 수가 어떻게 변하는지 보자. 먼저 확인할 수 있는 것은 위치가 변하지 않은 수들간(검정색 수들)의 역접 여부는 변하지 않는다는 사실이다. 위치가 변하는 값(빨간색 수)과 변하지 않는 값들 사이의 역접 여부와, 위치가 변하는 두 값 사이에 역접 여부는 변할 수 있으므로 역접의 수에 영향을 줄 수 있다.

그리고 위치가 변하는 두 값(4와 7) 사이에 위치한 값들간의 관계만이 연산 후 역접의 수에 영향을 준다는 사실도 알 수 있다. (4의 왼쪽 수들을 4가 오른쪽으로 더 이동하더라도 4와의 역접 여부는 변하지 않는다. 마찬가지로 7의 오른쪽 수들은 7이 왼쪽으로 더 이동하더라도 7과의 역접 여부는 변하지 않는다)

위치 \(l\) 과 \(r\) 의 값을 교환했을 때, 그들과 그들 사이에 있는 값들과의 역접 여부가 어떻게 변하는지 따져보면 아래와 같이 세부적으로 정리할 수 있다.

1. \((l, \ r)\) 중 \(a[l]\) 보다 큰 값들의 수만큼 역접의 수는 늘어난다.
2. \((l, \ r)\) 중 \(a[l]\) 보다 작은 값들의 수만큼 역접의 수는 줄어든다.
3. \((l, \ r)\) 중 \(a[r]\) 보다 큰 값들의 수만큼 역접의 수는 줄어든다.
4. \((l, \ r)\) 중 \(a[r]\) 보다 큰 값들의 수만큼 역접의 수는 늘어난다.
5. \(a[l] < a[r]\) 이면 역접의 수가 1 증가하고, \(a[l] > a[r]\) 이면 역접의 수가 1 감소한다.

위의 내용들에서 서로 상쇄되는 것들을 제거하고, 통합하면 아래와 같이 간결하게 역접의 수 변화를 확인할 수 있다.

1. \(a[l] < a[r]\) 이면, \((l<i<r)\) 에 대하여 '(\(a[l]<a[i]<a[r]\) 인 \(i\) 의 개수) \(\times \ 2 + 1\)' 만큼 역접의 수가 증가한다.
2. \(a[l] > a[r]\) 이면, \((l<i<r)\) 에 대하여 '(\(a[l]>a[i]>a[r]\) 인 \(i\) 의 개수) \(\times \ 2 + 1\)' 만큼 역접의 수가 감소한다.

위에서 정리한대로라면, 구간 \((l, \ r)\) 에서 두 원소 \(a[l]\) 와 \(a[r]\) 사이에 존재하는 값의 개수를 최대한 빠르게 세는 것이 문제를 해결하는 관건이 된다.

구간 \((l, \ r)\) 에서 두 원소 \(a[l]\) 와 \(a[r]\) 사이에 존재하는 값의 개수를 빠르게 세기 위해서 우리는 평방 분할 기법(square root decomposition)과 펜윅 트리(fenwick tree)를 이용할 수 있다. 순열 \(a[ \ ] = \{1, 2, ..., n\}\) 를 \(\sqrt{n}\) 크기의 블록들로 분할한 후, 각 블록마다 어떤 원소값이 블록에 포함되어 있는지를 펜윅 트리로 표현(있으면 1, 없으면 0)해두면 된다. 그러면 각 블록에서 \(a[l]\) 와 \(a[r]\) 사이에 존재하는 값의 개수를 \(O(log_2n)\) 만에 구할 수 있고, 전체 \(q\) 번의 질문에 \(O(q \times \sqrt{n} \times log_2n)\)의 시간이 소요된다.

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

const int MAX_N = 2e5 + 5;

int n, q;
int arr[MAX_N];
int blkSz, numOfBlks;

struct FenwickTree {
    vector<int> tree;
    FenwickTree(int n) : tree(n + 1) {}
    int sum(int pos) {
        int ret = 0;
        while (pos > 0) {
            ret += tree[pos];
            pos -= (pos & -pos);
        }
        return ret;
    }
    void add(int pos, int val) {
        while (pos < tree.size()) {
            tree[pos] += val;
            pos += (pos & -pos);
        }
    }
    int query(int l, int r) {
        return sum(r) - sum(l - 1);
    }
};

vector<FenwickTree> ftrees;

void preprocess() {
    blkSz = (int)sqrt(n);
    numOfBlks = n / blkSz + 1;

    ftrees.assign(numOfBlks, FenwickTree(n));

    int idx = -1;
    for (int i = 0; i < n; i++) {
        arr[i] = i + 1;
        if (i % blkSz == 0) ++idx; 
        ftrees[idx].add(i + 1, 1); 
    }
}


int countBetween(int l, int r) {
    int lb = l / blkSz, rb = r / blkSz;
    int minX = min(arr[l], arr[r]), maxX = max(arr[l], arr[r]);
    int between = 0;
    if (lb == rb) {
        for (int i = l + 1; i < r; i++) {
            between += (minX < arr[i] && arr[i] < maxX);
        }
    } else {
        for (int i = l + 1; (i / blkSz) == lb; i++) {
            between += (minX < arr[i] && arr[i] < maxX);
        }
        for (int i = r - 1; (i / blkSz) == rb; i--) {
            between += (minX < arr[i] && arr[i] < maxX);
        }
        for (int idx = lb + 1; idx < rb; idx++) {
            between += ftrees[idx].query(minX + 1, maxX - 1);
        }
    }
    return between;
}

void swapping(int l, int r) {
    int blockL = l / blkSz, blockR = r / blkSz;

    if (blockL == blockR) {
        swap(arr[l], arr[r]);
        return;
    }

    ftrees[blockL].add(arr[l], -1);
    ftrees[blockL].add(arr[r], +1);
    ftrees[blockR].add(arr[r], -1);
    ftrees[blockR].add(arr[l], +1);
    swap(arr[l], arr[r]);
}

int main() {
    scanf("%d %d", &n, &q);

    preprocess();

    int64_t ans = 0; // # of inversion
    for (int i = 0; i < q; i++) {
        int l, r;
        scanf("%d %d", &l, &r);
        l--; r--;

        if (l > r) swap(l, r);
        
        if (arr[l] < arr[r]) {
            ans += 2 * countBetween(l, r) + 1;
        }
        if (arr[l] > arr[r]) {
            ans -= 2 * countBetween(l, r) + 1;
        }

        swapping(l, r);

        printf("%I64d\n", ans);
    }
}