[백준] 5012 불만정렬

전에 공장 문제에서 i<j 일때 arr[i]>arr[j]인 수를 찾는 것을 했다.

이 문제는 i<j<k && arr[i] > arr[j] > arr[k] 이므로 j를 기준으로

1. i<j && arr[i] > arr[j]

2. j<k && arr[j] < arr[k] 

두 개를 찾아서 곱하면 경우의 수가 나온다

1번을 역으로하면 2번을 바로 구할 수 있다

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define ll long long
#define MAXN 100010
int n;
int _sum(vector<int>&arr, int x) {
    int ret = 0;
    for (int i = x; i > 0; i -= (i&-i)) ret += arr[i];
    return ret;
}
int sum(vector<int>&arr, int s, int e) {
    return _sum(arr, e) - _sum(arr, s - 1);
}
void update(vector<int>&arr, int x, int val) {
    for (int i = x; i <= n; i += (i&-i)) arr[i] += val;
}
 
int main() {
    scanf(" %d", &n);
    vector<int>arr(n + 1, 0), l(n + 1, 0), r(n + 1, 0),tree(n+1,0);
    for (int i = 1; i <= n; i++) scanf(" %d", &arr[i]);
    for (int i = 1; i <= n; i++) {
        l[i] = sum(tree, arr[i] + 1, n);
        update(tree, arr[i], 1);
    }
    fill(tree.begin(), tree.end(), 0);
    for (int i = n; i >= 1; i--) {
        r[i] = sum(tree, 1, arr[i] - 1);
        update(tree, arr[i], 1);
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) ans += (ll)r[i] * l[i];
    printf("%lld\n", ans);
}