본문 바로가기

알고리즘 관련/BOJ

BOJ)5012 불만 정렬

문제: icpc.me/5012


i<j<k 를 만족하는 원소 중에서 Ai>Aj>Ak를 만족하는 경우의 수를 세는 문제이다.


우리는 j를 기준으로 생각해보자.


현재 j를 보고 있을 때 경우의 수에 해당할 수 있는 경우는


result = SUM [ (j보다 먼저 등장하고 Aj보다 큰 수) x (j보다 나중에 등장하고 Aj보다 작은 수) ]  으로 나타낼 수 있다.


따라서 우리는 쿼리를 다 받은 후 앞에서 부터 보면서 j보다 먼저 등장하면서 Aj보다 큰 수들을 먼저 기록 한 후 


다시 한번 뒤에서부터 보면서 j보다 늦게 등장하면서 Aj보다 작은 수들을 기록해준 뒤 곱해주어 더한값을 출력하면 된다.



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
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX_N 100000
using namespace std;
typedef long long ll;
int q[MAX_N + 1], seg[* MAX_N], n, x, a[MAX_N + 1], b[MAX_N + 1];
ll res;
int update(int pos, int val, int node, int x, int y) {
    if (y < pos || pos < x)
        return seg[node];
    if (x == y)
        return seg[node] += val;
    int mid = (x + y) >> 1;
    return seg[node] = update(pos, val, node * 2, x, mid) + update(pos, val, 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"&q[i]);
    }
    for (int i = 1; i <= n; i++) {
        a[i] = query(q[i] + 1, MAX_N, 11, MAX_N);
        update(q[i], 111, MAX_N);
    }
    memset(seg, 0sizeof(seg));
    for (int i = n; i>0; i--) {
        b[i] = query(1, q[i] - 111, MAX_N);
        update(q[i], 111, MAX_N);
    }
    for (int i = 1; i <= n; i++) {
        res += (ll)a[i] * (ll)b[i];
    }
    printf("%lld", res);
    return 0;
}
cs


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

BOJ)10999 구간 합 구하기2  (1) 2017.01.13
BOJ)11505 구간 곱 구하기  (2) 2017.01.12
BOJ)3002 아날로그 다이얼  (0) 2017.01.11
BOJ)1168 조세퍼스 문제2  (0) 2017.01.11
BOJ)9426 중앙값 측정  (7) 2017.01.11