BOJ)5012 불만 정렬

문제: icpc.me/5012

i<j<k 를 만족하는 원소 중에서 Ai>Aj>Ak를 만족하는 경우의 수를 세는 문제이다.

우리는 j를 기준으로 생각해보자.

현재 j를 보고 있을 때 경우의 수에 해당할 수 있는 경우는

result = SUM [ (j보다 먼저 등장하고 Aj보다 큰 수) x (j보다 나중에 등장하고 Aj보다 작은 수) ]  으로 나타낼 수 있다.

따라서 우리는 쿼리를 다 받은 후 앞에서 부터 보면서 j보다 먼저 등장하면서 Aj보다 큰 수들을 먼저 기록 한 후 

다시 한번 뒤에서부터 보면서 j보다 늦게 등장하면서 Aj보다 작은 수들을 기록해준 뒤 곱해주어 더한값을 출력하면 된다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX_N 100000
using namespace std;
typedef long long ll;
int q[MAX_N + 1], seg[4 * MAX_N], n, x, a[MAX_N + 1], b[MAX_N + 1];
ll res;
int update(int pos, int val, int node, int x, int y) {
    if (y < pos || pos < x)
        return seg[node];
    if (x == y)
        return seg[node] += val;
    int mid = (x + y) >> 1;
    return seg[node] = update(pos, val, node * 2, x, mid) + update(pos, val, node * 2 + 1, mid + 1, y);
}
int query(int lo, int hi, int node, int x, int y) {
    if (y < lo || hi < x)
        return 0;
    if (lo <= x&&y <= hi)
        return seg[node];
    int mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * 2 + 1, mid + 1, y);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &q[i]);
    }
    for (int i = 1; i <= n; i++) {
        a[i] = query(q[i] + 1, MAX_N, 1, 1, MAX_N);
        update(q[i], 1, 1, 1, MAX_N);
    }
    memset(seg, 0, sizeof(seg));
    for (int i = n; i>0; i--) {
        b[i] = query(1, q[i] - 1, 1, 1, MAX_N);
        update(q[i], 1, 1, 1, MAX_N);
    }
    for (int i = 1; i <= n; i++) {
        res += (ll)a[i] * (ll)b[i];
    }
    printf("%lld", res);
    return 0;
}