반응형

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

 

5012번: 불만 정렬

정렬 알고리즘의 상한(upper bound)은 n2이다. 이 사실은 쉽게 증명할 수 있다. 올바른 순서가 아닌 임의의 두 원소(ai > aj, i < j)를 선택하고, 그 위치를 서로 바꿔준다. 이렇게 올바른 순서가 아닌 것

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/364

 

[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

1. arr배열에 수열을 입력받고, 0부터 n-1번까지 for문을 통해 돌면서 자신보다 큰 값을 gop에 저장합니다.

 

2. n-1부터 0까지 for문을 통해 돌면서 자신보다 작은 값을  gop에 곱합니다.

 

3. ans에 모든 gop의 값을 더한 후 출력합니다.

 

[ 소스코드 ]

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
64
65
#include<iostream>
#define ll long long
 
using namespace std;
 
int n;
int segTree[200000];
int arr[100000];
ll gop[100000];
ll ans;
 
void updateTree(int idx)
{
    while (idx) {
        segTree[idx]++;
        idx >>= 1;
    }
}
 
int getTree(int l, int r)
{
    int ret = 0;
 
    while (l <= r) {
        if (l & 1) {
            ret += segTree[l];
            l++;
        }
        if (~r & 1) {
            ret += segTree[r];
            r--;
        }
        l >>= 1;
        r >>= 1;
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < n; i++) {
        gop[i] = getTree(n + arr[i], 2 * n - 1);
        updateTree(n + arr[i] - 1);
    }
 
    fill(segTree, segTree + 2 * n, 0);
 
    for (int i = n - 1; i >= 0; i--) {
        gop[i] *= getTree(n, n + arr[i] - 2);
        updateTree(n + arr[i] - 1);
        ans += gop[i];
    }
    
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 13537번 - 수열과 쿼리 1 (C++)  (0) 2023.08.08
[ 백준 ] 2465번 - 줄 세우기 (C++)  (0) 2023.08.06
[ 백준 ] 17408번 - 수열과 쿼리 24 (C++)  (0) 2023.08.04
[ 백준 ] 14459번 - 소가 길을 건너간 이유 11 (C++)  (0) 2023.08.03
[ 백준 ] 15967번 - 에바쿰 (C++)  (0) 2023.08.02

+ Recent posts

티스토리툴바