[백준BOJ] 5012 불만 정렬

 

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

5012번: 불만 정렬

---

문제해설

"펜윅 트리"를 사용하여 풀었습니다.

이 문제는 밑의 문제와 굉장히 유사한 문제라고 할 수 있습니다.

2019/10/06 - [알고리즘/BOJ] - [백준BOJ] 3006 터보소트

[백준BOJ] 3006 터보소트

i < j < k 이면서 Ai > Aj > Ak

인 경우의 수를 찾기 위해서는

j를 기준으로 왼쪽, 오른쪽을 탐색하면 됩니다.

 

< 변수 >

#define MAX_N 100000
int tree_left[MAX_N + 1];
int tree_right[MAX_N + 1];
vector<int> l, r;

 

case1 : 자신 기준 왼쪽에 있으면서 큰 값의 수

case2 : 자신 기준 오른쪽에 있으면서 작은 값의 수

< case1 >

int left =  query(tree_left, MAX_N) - query(tree_left, data_left);

위의 코드처럼 구간합으로 자신보다 왼쪽에 있으면서 큰 값들의 갯수를 구할 수 있습니다.

 

< case2 >

int right =  query(tree_right,  data_right-1);

위의 코드처럼 구간합으로 자신보다 오른쪽에 있으면서 작은 값들의 갯수를 구할 수 있습니다. 

---

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
vector<int> vec;
#define MAX_N 100000
int tree_left[MAX_N + 1];
int tree_right[MAX_N + 1];
vector<int> l, r;

void update(int tree[],int target, int value) {
     while (target <= MAX_N) {
          tree[target] += value;
          target += (target & -target);
     }
}

int query(int tree[],int target) {
     int ret = 0;
     while (target >= 1) {
          ret += tree[target];
          target -= (target &-target);
     }
     return ret;
}

int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     int N;
     cin >> N;
     for (int i = 1; i <= N; i++) {
          int data; cin >> data;
          vec.push_back(data);
     }

     long long ans = 0;
     for (int i = 0, j = vec.size()-1; i < vec.size(); i++, j--) {
          int data_left = vec[i]; 
          int data_right = vec[j];

          int right =  query(tree_right,  data_right-1);
          int left =  query(tree_left, MAX_N) - query(tree_left, data_left);
          l.push_back(left); r.push_back(right);

          update(tree_right, data_right, 1);
          update(tree_left, data_left, 1);

     }
     for (int i = 0, j = r.size()-1; i < l.size(); i++,j--) {
          ans += ((long long)l[i] * r[j]);
     }
     cout << ans << "\n";
}