백준 10090번 Counting Inversions

문제

A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once.

Two integers in а permutation form an inversion, when the bigger one is before the smaller one.

As an example, in the permutation 4 2 7 1 5 6 3, there are 10 inversions in total. They are the following pairs: 4–2, 4–1, 4–3, 2–1, 7–1, 7–5, 7–6, 7–3, 5–3, 6–3.

Write program invcnt that computes the number of the inversions in a given permutation.

입력

The value for the number n is written on the first line of the standard input. The permutation is written on the second line: n numbers, delimited by spaces. (2 ≤ n ≤ 1000000)

출력

Write the count of inversions on the standard output.

 

ans 값은 long long 으로 할 것!

 

#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;


int arr[1000005];
int temp[1000005];
int N;
long long ans;

void merge_sort(int left, int mid, int right)
{
	int low = left;
	int high = mid + 1;
	int k = left;

	while (low <= mid && high <= right)
	{
		if (arr[low] <= arr[high])
		{
			temp[k++] = arr[low++];
		}
		else
		{
			ans += (mid - low + 1);
			temp[k++] = arr[high++];
		}
	}

	if (high <= right)
	{
		for (int i = high; i <= right; i++)
		{
			temp[k++] = arr[i];
		}
	}
	if (low <= mid)
	{
		for (int i = low; i <= mid; i++)
		{
			temp[k++] = arr[i];
		}
	}

	for (int i = left; i <= right; i++)
	{
		arr[i] = temp[i];
	}
}


void merge(int left, int right)
{
	if (left < right)
	{
		int mid = (left + right) / 2;
		merge(left, mid);
		merge(mid + 1, right);
		merge_sort(left, mid, right);

	}
}


int main()
{
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> arr[i];
	}

	merge(1, N);
	cout << ans << endl;
	
}