[5012번] 불만 정렬

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 세그먼트 트리

문제에 나와있는 다음 조건을 이용하여 문제를 해결해본다.

(ai > aj > ak와 i < j < k를 만족시켜라.)

결국 우리는 매 입력마다 j번째라 생각하고 입력을 받을 때, 

세그먼트 트리에 왼쪽에 있는 값들의 개수, 오른쪽에 있는 값들의 개수를 저장해둔 뒤,

최종적으로 모두 곱해준다면 정답을 얻을 수 있게 된다.

즉, 핵심은 위의 규칙을 따르되 그때 j번째라 생각하고 풀면 쉽게 해결이 가능하다.

소스 코드 : 

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 66 67 68 69 70 71 72 73 74 75 76

#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <vector>   using namespace std;   int l[100002], r[100002]; vector<int> tree;   void update(int node, int start, int end, int idx) {     if (!(start <= idx && idx <= end))         return;       tree[node] += 1;       if (start != end)     {         int mid = (start + end) / 2;         update( node * 2, start, mid, idx);         update( node * 2 + 1, mid + 1, end, idx);     } }   int query(int node, int start, int end, int left, int right) {     if (right < start || left > end)         return 0;       if (left <= start && end <= right)         return tree[node];          int mid = (start + end) / 2;     return query( node * 2, start, mid, left, right) + query( node * 2 + 1, mid + 1, end, left, right); } int main() {     int n;     scanf("%d", &n);       int h = (int)ceil(log2(n));     int tree_size = (1 << (h + 1));       vector<int> arr(n + 1);     tree = vector<int>(tree_size);       long long ans = 0;     for (int i = 0; i < n; i++)         scanf("%d", &arr[i]);       for (int i = 0; i < n; i++)     {         l[i] = query( 1, 0, n - 1, arr[i], n - 1);         update( 1, 0, n - 1, arr[i] - 1);     }              tree = vector<int>(tree_size);       for (int i = n - 1; i >= 0; i--)     {         r[i] = query( 1, 0, n - 1, 0, arr[i] - 2);         update( 1, 0, n - 1, arr[i] - 1);     }       for (int i = 0; i < n; i++)         ans += 1LL * l[i] * r[i];          printf("%lld", ans);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus