Poj 2299 Ultra-QuickSort 樹狀數組 解法

本題的樹狀數組稍微有點特點，就是需要所謂的離散化一下，開始聽這個名稱好像很神秘的，不過其實很簡單。

就是把一個數組arr的值，其中的值是不連續的，變成一組連續的值，因為這樣他們的順序是不變的，所以，不影響結果。

例如：9 1 0 5 4 ->變為：5 2 1 4 3看出他們的相對位置不變的。

9和5為最大值在第一個位置，1和2為第二大的值在第二個位置，0和1在第一個位置等，看出對應順序了嗎？

對，就是這麼簡單的方法， 就叫做離散化。

如果你對counting sort熟悉的話，那麼這樣的思想理解並寫出程序是毫不費力的。

當然本題如果使用歸並排序會更好，不過歸並太簡單了。

原題：http://poj.org/problem?id=2299

我們這裡使用樹狀數組加上上面說的離散化。

class UltraQuickSort2299
{
	const static int SIZE = 500005;
	int *reflect, *tree;
	inline int lowbit(int x)
	{
		return x & (-x);
	}

	void update(int x, int val, int len)
	{
		while (x <= len)
		{
			tree[x] += val;
			x += lowbit(x);
		}
	}

	long long query(int x)
	{
		long long ans = 0;
		while (x > 0)
		{
			ans += tree[x];
			x -= lowbit(x);
		}
		return ans;
	}

	struct Node
	{
		int val, pos;
		bool operator<(const Node a) const
		{
			return val < a.val;
		}
	};

	Node *arr;
public:
	UltraQuickSort2299():arr((Node *)malloc(sizeof(Node) * SIZE)),
		tree((int *)malloc(sizeof(int) * SIZE)),
		reflect((int *)malloc(sizeof(int) * SIZE))
	{
		int N;
		while (scanf("%d", &N) && N != 0)
		{
			for (int i = 1; i <= N; i++)
			{
				scanf("%d", &arr[i].val);
				arr[i].pos = i;
			}

			std::sort(arr+1, arr+N+1);

			for (int i = 1; i <= N; i++)
			{
				reflect[arr[i].pos] = i;//所謂的離散化，即對應到新的值，相對位置不變，下標記得變為1起點，如此倒騰的思維帶counting sort的思維
			}

			std::fill(tree, tree+N+1, 0);
			long long ans = 0;
			for (int i = 1; i <= N; i++)
			{
				update(reflect[i], 1, N);
				ans += i - query(reflect[i]);
			}
			printf("%lld\n", ans);
		}
	}

	~UltraQuickSort2299()
	{
		free(tree);
		free(arr);
		free(reflect);
	}
};