BOJ 5012 | 불만 정렬

= (#28020)

코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ll long long

#define debug if constexpr (local) std::cout
#define endl '\n'

class SegTree{
private:
	vector<ll> tree;
public:
	SegTree(int N){
		tree.resize(4*N);
	}
	
	void clear(){
		for (int i = 0; i < tree.size(); i++) tree[i] = 0;
	}
	
	ll init(vector<ll> &nums, ll node, int s, int e){
		if (s == e) return tree[node] = nums[s];
		return tree[node] = init(nums, node*2, s, (s+e)/2) + init(nums, node*2+1, (s+e)/2+1, e);
	}
	
	ll update(ll node, int s, int e, int idx, int add){
		if (idx < s || e < idx) return tree[node];
		if (s == e) return tree[node] += add;
		
		return tree[node] = update(node*2,s,(s+e)/2,idx,add)+update(node*2+1,(s+e)/2+1,e,idx,add);
	}
	
	ll query(ll node, int s, int e, int l, int r){
		if (e < l || r < s) return 0;
		if (l <= s && e <= r) return tree[node];
		
		return query(node*2,s,(s+e)/2,l,r) + query(node*2+1,(s+e)/2+1,e,l,r);
	}
};

int main(){
	FASTIO;
	int N; cin >> N;
	SegTree SG(N);
	vector<ll> lis;
	for (int i = 0; i < N; i++){
		int t; cin >> t;
		lis.push_back(t);
	}
	reverse(lis.begin(), lis.end());
	
	vector<ll> smaller(N);
	vector<ll> larger(N);
	for (int i = 0; i < N; i++){
		smaller[i] = SG.query(1, 1, N, 1, lis[i]-1);
		SG.update(1, 1, N, lis[i], 1);
	}
	SG.clear();
	
	for (int i = N-1; i >= 0; i--){
		larger[i] = SG.query(1, 1, N, lis[i]+1, N);
		SG.update(1, 1, N, lis[i], 1);
		
		//debug << lis[i] << ' ' << larger[i] << endl;
	}
	
	ll sum = 0;
	for (int i = 0; i < N; i++){
		sum += smaller[i] * larger[i];
	}
	
	cout << sum;
	
}