백준21823 Swap Swap Sort

작성일 | In

문제 링크

  • http://icpc.me/21823

문제 출처

  • 2021 CCO Day1 1번

사용 알고리즘

  • Regions Trick

시간복잡도

  • $O((N+K)\sqrt N \log N)$

풀이

어떤 수열 $A$와 target permutation $P$가 주어졌을 때, $i < j$이면서 $P$에서 $A[i]$가 $A[j]$보다 뒤에 있는 순서쌍 $(i, j)$의 개수를 구하는 문제입니다.
$P = \left{ 1, 2, \cdots, N \right}$인 초기 상태에서의 순서쌍의 개수는 단순한 inversion counting 문제입니다. $P$에서 인접한 두 수 $P[t]$와 $P[t+1]$의 위치를 교환할 때 inversion 개수의 변화를 살펴봅시다.

편의상 $u = P[t], v = P[t+1]$이라고 하겠습니다. $A[i] = u, A[j] = v$인 모든 순서쌍 $(i, j)$에 대해, $i < j$였다면 inversion의 개수가 1 증가하고, 반대로 $i > j$였다면 1 감소합니다. 따라서 $A[i] = u$인 모든 $i$를 보면서, 자신보다 앞에 있는 $v$의 개수와 뒤에 있는 $v$의 개수를 구하면 문제를 해결할 수 있습니다.
각 수가 등장하는 위치를 알고 있다면 $A[i] = u$인 모든 $i$를 순회하면서 $v$가 등장하는 위치에 대해 이분 탐색을 수행해서 원하는 값을 구할 수 있습니다. 따라서 각 쿼리의 시간 복잡도는 $O(\min(S[u], S[v]) \log \max(S[u], S[v]))$입니다.

이 방법을 그대로 적용하면 전체 시간 복잡도가 $O(KN \log N)$이지만, 쿼리의 결과를 저장해서 중복 계산을 방지하면(IOI’09 Regions Trick) $O((N+K)\sqrt N \log N)$에 문제를 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int N, K, Q, A[101010], B[101010], T[101010];
vector<int> P[101010]; ll R;
void Add(int x, int v){ for(x+=3; x<101010; x+=x&-x) T[x] += v; }
int Get(int x){ int ret = 0; for(x+=3; x; x-=x&-x) ret += T[x]; return ret; }

map<pair<int,int>, ll> Cache;
ll Swap(int u, int v){
    auto it = Cache.lower_bound(make_pair(u, v));
    if(it != Cache.end() && it->first == make_pair(u, v)) return it->second;

    ll res = 0;
    if(P[u].size() < P[v].size()){
        for(auto i : P[u]){
            int cnt = P[v].end() - lower_bound(P[v].begin(), P[v].end(), i);
            res += cnt - ((int)P[v].size() - cnt);
        }
    }
    else{
        for(auto i : P[v]){
            int cnt = lower_bound(P[u].begin(), P[u].end(), i) - P[u].begin();
            res += cnt - ((int)P[u].size() - cnt);
        }
    }
    Cache.emplace_hint(it, make_pair(u, v), res);
    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K >> Q; iota(B+1, B+K+1, 1);
    for(int i=1; i<=N; i++) cin >> A[i], P[A[i]].push_back(i);
    for(int i=N; i>=1; i--) R += Get(A[i]-1), Add(A[i], 1);
    for(int q=1; q<=Q; q++){
        int t; cin >> t;
        R += Swap(B[t], B[t+1]); swap(B[t], B[t+1]);
        cout << R << "\n";
    }
}