[백준] 5012 불만 정렬

현주는 ai > aj > ak와 i < j < k를 만족하는 세 원소를 선택한 뒤, ak, aj, ai로 순서를 바꾸려고 한다. 현주가 선택할 수 있는 세 원소의 개수를 구하는 프로그램을 작성하시오. → ai, aj, ak 수열이 순서대로 있다면 ai > aj > ak 일 때 이를 선택할 수 있고 1개의 경우의 수가 생긴다. 세개를 모두 비교하기보다 중간값인 j를 골라 비교해보자. j보다 순서가 작은(i) 수 중에서 j 위치의 aj 보다 큰 값을 가지는 경우의 수 ci, j보다 순서가 큰(k) 수 중에서 aj 보다 작은 값을 가지는 경우의 수 ck. 값이 aj일 때 ci와 ck는 위 조건을 만족하는 각각의 경우의 수가 되고, ci*ck 로 곱하면 선택할 수 있는 모든 경우의 수가 된다.

 

예제 입력 1

4
3 3 2 1

예제 출력 1

2

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_n 100001

int n, a, arr[MAX_n];
long long ans = 0, l[MAX_n], r[MAX_n];
int tree[MAX_n*4];

void update(int cur_node, int cur_left, int cur_right, int target_node) {
    if (target_node < cur_left || cur_right < target_node) return ;

    tree[cur_node] += 1;

    if (cur_left != cur_right) {
        update(cur_node*2, cur_left, (cur_left+cur_right)/2, target_node);
        update(cur_node*2+1, (cur_left+cur_right)/2+1, cur_right, target_node);
    }
}

int query(int cur_node, int cur_left, int cur_right, int target_left, int target_right) {
    if (target_right < cur_left || cur_right < target_left) return 0;

    if (target_left <= cur_left && cur_right <= target_right) return tree[cur_node];

    return query(cur_node*2, cur_left, (cur_left+cur_right)/2, target_left, target_right) + query(cur_node*2+1, (cur_left+cur_right)/2+1, cur_right, target_left, target_right);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }

    for (int i = 1; i <= n; ++i) { // 보다 큰거.
        r[i] = query(1, 1, n, 1, n) - query(1, 1, n, 1, arr[i]);
        update(1, 1, n, arr[i]);
    }
    fill(&tree[0], &tree[0]+MAX_n*4, 0);
    for (int i = n; i >= 1; --i) { // 보다 작은거.
        l[i] = query(1, 1, n, 1, arr[i]-1);
        update(1, 1, n, arr[i]);
    }

    for (int i = 1; i <= n; ++i) {
        ans += l[i]*r[i];
    }
    cout << ans;

    return 0;
}