[BOJ5012} 불만정렬

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

가운데를 기준으로 생각할 때 (왼쪽에서는 자신보다 큰수의 개수) * ( 오른쪽에서 자신보다 작은 수의 개수) 를 n개의원소마다

구해서 더해준다면 답이 될것입니다.

따라서 우리는 먼저  n번 자신보다 왼쪽에있는 수중에 큰 수를 구해봅시다.

왼쪽에서부터 시작해서 세그먼트트리를 업데이트하면서 자신보다 큰수의 개수를  query 하면서 a 배열에 저장합니다.

seg배열을 리셋한 후 반대방향으로 자신보다 작은 수의 개수를 query 하면서 b배열에 저장합니다.

따라서 a[i]*b[i] 의 합이 답이 됩니다. 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
typedef long long ll;
using namespace std;
const int MAX_N = 101000;
int seg[MAX_N * 4];
 
int update(int pos, int val, int node, int x, int y) {
    if (pos < x || y < pos)    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 (hi < x || y < lo)    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 n;
vector<int> vt;
int a[MAX_N];
int b[MAX_N];
int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    int tmp;
    for (int i = 0; i < n; i++) {
        scanf("%d", &tmp);
        vt.push_back(tmp);
    }
    ll ans = 0;
    
    for (int i = 0; i < n; i++) {
        a[i] = query(vt[i]+1, n,1, 1, MAX_N);
        update(vt[i], 1, 1, 1, MAX_N);
    }
    memset(seg, 0, sizeof(seg));
    for (int i = n-1; i >=0; i--) {
        b[i] = query(0,vt[i]-1, 1, 1, MAX_N );
        update(vt[i], 1,1, 1, MAX_N);
    }
    for (int i = 0; i < n; i++)
        ans += (ll)a[i] * (ll)b[i];
 
    printf("%lld", ans);
}