DAMPER's 낙서장

세그먼트 트리 - (2). Counting Inversions 본문

Problem Solving/Algorithms

세그먼트 트리 - (2). Counting Inversions

DAMPER 2022. 5. 28. 23:57
728x90

이번 글은 세그먼트 트리를 활용 방법 중 하나인 Counting Inversions 이다.

 

길이가 N이고 1부터 N까지의 수를 1개씩 가지고 있는 순열이 있다고 하자.

Counting Inversions는 각 수에서 오른쪽으로 자기 자신보다 작은 수의 갯수의 합(또는 왼쪽으로 자기 자신보다 큰 수의 갯수의 합)을 말한다.

 

예를 들어, A ={4, 1, 3, 2} 라는 수열이 있다고 하자.

4-1, 4-3, 4-2, 3-2 총 4개의 inversion이 존재한다.

 

이를 세그먼트 트리로 해결할 수 있는데,

저번 글에서 우리는 먼저 세그먼트 트리를 구성해놓고, 최소값을 찾으러 갔다.

하지만 이 문제에서는 먼저 세그먼트 트리를 구성하는 것이 아니라, 세그먼트 트리를 구성하면서 답을 찾아가는 것이다.

 

배열에 수열을 저장할 때 인덱스도 함께 저장한다.

그리고 이를 수에 대해서 정렬을 한다.

 

작은 수부터 세그먼트 트리에 넣으면서 구간 합을 구한다.

1. [A_i의 인덱스, n-1] 구간에서 구간합을 구한다. -> 해당 구간에서의 A_i 보다 작은 수의 갯수를 구할 수 있다.

2. 세그먼트 트리에서 A_i의 인덱스(정확히는 A_i의 인덱스 + leaf_size)에 1을 추가하고 update 한다.

 

1에서 구한 수를 모두 더하면 답을 구할 수 있다.

https://www.acmicpc.net/problem/10090

 

10090번: Counting Inversions

A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once. Two integers in а permutation form an inversion, when the bigger one is before the smaller one. As an example

www.acmicpc.net

 

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
 
using namespace std;
 
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
 
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
void update(int nodeNum, int value, vector<int>& seg_tree)
{
    seg_tree[nodeNum] = value;
    while(nodeNum > 1)
    {
        nodeNum /= 2;
        seg_tree[nodeNum] = seg_tree[nodeNum*2] + seg_tree[nodeNum*2+1];
    }
}
 
int get_seg_cal(int L, int R, int nodeNum, int left, int right, vector<int>& seg_tree)
{
    if(L > right || R < left) return 0;
    if(L <= left && right <= R) return seg_tree[nodeNum];
    int mid = (left+right)/2;
    return get_seg_cal(L, R, nodeNum*2, left, mid, seg_tree) + 
get_seg_cal(L, R, nodeNum*2+1, mid+1, right, seg_tree);
}
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n;
    cin >> n;
    vector<pii> v(n, {0, 0});
    for(int i=0;i<n;i++)
    {
        cin >> v[i].first;
        v[i].second = i;
    }
    sort(v.begin(), v.end());
 
    int depth = (int)ceil(log2(n))+1;
    int tree_size = 1 << depth;
    int leaf_size = tree_size/2;
 
    vector<int> seg_tree(tree_size, 0);
    int ans = 0;
    for(int i=0;i<n;i++)
    {
        int cnt = get_seg_cal(v[i].second, n-1, 1, 0, leaf_size-1, seg_tree);
        ans += cnt;
        update(v[i].second+leaf_size, 1, seg_tree);
    }
    cout << ans;
    return 0;
}
 cs
 
 
  

 

728x90

'Problem Solving > Algorithms' 카테고리의 다른 글

알고리즘과 효율성 분석  (0) 2023.02.14
세그먼트 트리 - (3). K번째 원소 찾기  (0) 2022.07.03
세그먼트 트리 - (1). 기본 구조  (0) 2022.05.27
'Problem Solving/Algorithms' Related Articles more