题目链接： http://poj.org/problem?id=2299 题目大意： 给你一个包含N个整数的序列，只能通过交换相邻的数字，最终变为升序顺序，问：最少需要多少次交换。 思路： 其实就是问冒泡排序的交换次数。其实就是求原序列的逆序数。用归并排序、线段树、树状数组都可以做。 但是如果用线段树和树状数组来做的话，因为元素个数是500000，但是元素值范围却是999

POJ 2299，题目链接http://poj.org/problem?id=2299 题意： 给出长度为n的序列，每次只能交换相邻的两个元素，问至少要交换几次才使得该序列为递增序列。 思路： 其实就是求逆序数，那么直接向到的就是冒泡了，交换一次，记录一次即可。但是n的范围达到50W，冒泡O(n^2)的复杂度铁定超时。 然后、、、发现曾经微软有一道笔试题类似就是求逆序数的，对