[1777번] 순열복원

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 세그먼트 트리 :: http://www.crocus.co.kr/648

이 문제는 아래 주소를 참조하여 공부하면 좋을 것 같다.

http://www.crocus.co.kr/887

왜냐면 모든 코드가 동일하고 for문이 1~n까지면 이 문제는 n~1로만 바꾸면 되기 때문이다.

[1849번] 순열 :: http://www.acmicpc.net/problem/1849 문제와 동일하지만

순열 문제는 앞에서 뒤로 세그트리를 query해줘야한다면 이 문제는 뒤에서 앞으로 세그트리를 query해주는 것 차이 뿐이다.

소스 코드 : 

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;   void update(vector<int> &tree, int node, int start, int end, int index, int diff) {     if (!(start <= index && index <= end))         return;       tree[node] += diff;       if(start != end)     {         int mid = (start + end) / 2;           update(tree, node * 2, start, mid, index, diff);         update(tree, node * 2 + 1, mid + 1, end, index, diff);     } }   int query(vector<int> &tree, int node, int start, int end, int val) {     int get;     int mid = (start + end) / 2;       if (start == end)     {         tree[node]--;         return start;     }       if (tree[node * 2] >= val)         get = query(tree, node * 2, start, mid, val);     else         get = query(tree, node * 2 + 1, mid + 1, end, val - tree[node * 2]);       tree[node]--;     return get; } int main() {     int n;     scanf("%d", &n);       vector<int> arr(n + 1);          int h = (int)ceil(log2(n));     int tree_size = 1 << (h + 1);       vector<int> tree(tree_size);       for (int i = 0; i < n; i++)     {         scanf("%d", &arr[i]);         update(tree, 1, 0, n - 1, i, 1);     }       vector<int> ans(n + 1);     for (int i = n - 1; i >= 0; i--)     {         int get = query(tree, 1, 0, n - 1, arr[i] + 1);                  ans[get + 1] = i + 1;     }       for (int i = n; i >= 1; i--)         printf("%d ", ans[i]);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus