NOIC - Ideia 01 - Exemplo 1

noic-ideia01-ex01.cpp

// NOIC - Ideia 1
// Exemplo 1
// Complexidade: O(N log N)

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

int n, V[maxn], bit[maxn];

// somar v na posição x
void upd(int x, int v)
{
	for (; x <= n; x += (x&-x))
		bit[x] += v;
}

// soma de 1 até x
int soma(int x)
{
	int ans = 0;
	for (; x > 0; x -= (x&-x))
		ans += bit[x];
	return ans;
}

int main(void)
{
	cin >> n;

	vector<int> C; // vetor auxiliar

	for (int i = 1; i <= n; i++)
	{
		cin >> V[i];

		C.push_back(V[i]);
	}

	sort(C.begin(), C.end()); // ordenamos C

	int ind = 0;
	map<int, int> Mp;

	for (int i = 0; i < C.size(); i++)
		if (Mp.find(C[i]) == Mp.end()) // se C[i] não foi mapeado ainda
			Mp[C[i]] = ++ind; // valor mapeado de C[i]

	long long ans = 0; // resposta (que pode chegar a long long)
	for (int i = n; i >= 1; i--)
	{
		// a partir de agora trocamos os V[i]s pelos seus valores mapeados
		
		ans += soma(Mp[V[i]]-1); // inversões que i participa

		upd(Mp[V[i]], 1);
	}

	cout << ans << "\n";
}