BOJ 1517 버블 소트

출처 : https://www.acmicpc.net/problem/1517
inversion counting

나는 merge sort tree 모른다.

아래 풀이는 segment tree 사용

#include<stdio.h>
#include<malloc.h>
struct info
{
	int idx;
	long long val;
};
long long answer, * tree;
struct info *list, *sorted;
void msort(struct info *, int, int);
void merge(struct info *, int, int, int);
int cmp(struct info, struct info);
long long qu(int, int, int, int, int);
void update(int);
long long make_answer();
int main(void)
{
	answer = make_answer();
	printf("%lld\n", answer);
	return 0;
}
long long make_answer()
{
	int n, l, r, g, s, e, node, i;
	long long ans;
	scanf("%d", &n);
	for (list = (struct info*)malloc(sizeof(struct info) * n), sorted = (struct info*)malloc(sizeof(struct info) * n), s = node = l = r = 1; r - l + 1 < n; l <<= 1, r <<= 1, r |= 1);
	for (tree = (long long *)calloc(r + 1, sizeof(long long)), i = 0, g = l - 1, e = r - l + 1; i < n; i++)
	{
		scanf("%lld", &list[i].val);
		list[i].idx = i + 1;
		tree[i + 1 + g] = 1;
	}
	for (i = g; i; i--)
	{
		tree[i] = tree[i << 1] + tree[i << 1 | 1];
	}
	msort(list, 0, n - 1);
	for (i = 0, ans = 0; i < n; i++)
	{
		ans += qu(node, s, e, 1, list[i].idx - 1);
		update(list[i].idx + g);
	}
	free(tree);
	free(list);
	free(sorted);
	return ans;
}
void msort(struct info * list, int left, int right)
{
	int mid;
	if (left < right)
	{
		mid = (left + right) >> 1;
		msort(list, left, mid);
		msort(list, mid + 1, right);
		merge(list, left, mid, right);
	}
}
void merge(struct info * list, int left, int mid, int right)
{
	int i, j, k, l;
	i = k = left;
	j = mid + 1;
	while (i <= mid && j <= right)
	{
		if (cmp(list[i], list[j]))
		{
			sorted[k++] = list[i++];
		}
		else
		{
			sorted[k++] = list[j++];
		}
	}
	if (mid < i)
	{
		for (l = j; l <= right; l++)
		{
			sorted[k++] = list[l];
		}
	}
	else
	{
		for (l = i; l <= mid; l++)
		{
			sorted[k++] = list[l];
		}
	}
	for (l = left; l <= right; l++)
	{
		list[l] = sorted[l];
	}
}
int cmp(struct info a, struct info b)
{
	return a.val <= b.val;
}
long long qu(int node, int start, int end, int left, int right)
{
	int mid;
	if (left > end || right < start)
	{
		return 0;
	}
	else if (left <= start && end <= right)
	{
		return tree[node];
	}
	mid = (start + end) >> 1;
	return qu(node << 1, start, mid, left, right) + qu(node << 1 | 1, mid + 1, end, left, right);
}
void update(int idx)
{
	tree[idx] = 0;
	idx >>= 1;
	while (idx)
	{
		tree[idx] = tree[idx << 1] + tree[idx << 1 | 1];
		idx >>= 1;
	}
}