본문 바로가기

알고리즘 관련/BOJ

BOJ)10090 Counting Inversions

문제: icpc.me/10090


1~N의 숫자들로 구성 된 수열이 주어질 때 먼저 나온 수보다 늦게 나온 수가  더 작은 경우의 수를 구하는 문제이다.


N이 100만이기 때문에 N^2 완전 탐색으로 해결하기에는 문제가 있다.


따라서 우리는 쿼리를 받는 순서대로 온라인으로 처리를 해줄 것이다.


우선 내가 현재 보는 수가 x라면 나보다 작은 수의 개수는 x-1개다 그러면 나보다 먼저 나온 수들 중 나보다 작은 수의 개수가 a개라면


x에 의하여 결정되는 경우의 수는 x-1-a가 된다.


따라서 우리는 세그먼트 트리를 이용하여 수열을 받을때마다 x보다 작은 수의 개수들을 구해주어 x-1-a를 답에 더해주고 x의 위치에 1을 업데이트 시켜주면 된다.


주의 할점은 답을 저장할 자료형을 long long으로 사용해야 한다는 것이다.


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
#include <cstdio>
#include <algorithm>
#define MAX_N 1000000
using namespace std;
int seg[* MAX_N], x, n;
long long r;
int update(int pos, int node, int x, int y) {
    if (pos < x || y < pos)return seg[node];
    if (x == y)return seg[node] += 1;
    int mid = (x + y) >> 1;
    return seg[node] = update(pos, node * 2, x, mid) + update(pos, node * + 1, mid + 1, y);
}
int query(int lo, int hi, int node, int x, int y) {
    if (y < lo || hi < x)
        return 0;
    if (lo <= x&&<= hi)
        return seg[node];
    int mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * + 1, mid + 1, y);
}
int main() {
    scanf("%d"&n);
    for (int i = 1; i <= n; i++) {
        scanf("%d"&x);
        r += (long long)(x - - query(1, x - 111, n));
        update(x, 11, n);
    }
    printf("%lld\n", r);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)11377 열혈강호3  (0) 2017.02.16
BOJ)11376 열혈강호2  (0) 2017.02.15
BOJ)2262 토너먼트 만들기  (0) 2017.02.15
BOJ)14226 이모티콘  (0) 2017.02.14
BOJ)5398 틀렸습니다  (0) 2017.02.11