HDU 1394 Minimum Inversion Number（线段树单点更新）

http://acm.hdu.edu.cn/showproblem.php?pid=1394

题意：有0～n-1数字组成的序列,然后进行这样的操作,每次将最前面一个元素放到最后面去会得到一个序列,每得到一个序列都可得出该序列的逆序数（如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数）。要求求出最小的逆序数。

思路：（一直在做线段树的题，看列表里有这一题。想了很久不会，看解题报告做出来的。）

说一下自己的想法：
1、对于某一序列，其中的某一个数a[i]能构成多少个逆序，只须判断在a[i]+1~n的范围内找之前的数是否出现过的次数；
2、然后求出第一个序列的逆序数。
3、由第一个序列的逆序数可以推出它下一个序列的逆序数。有规律下一个序列的逆序数 sum = 上一个的sum - a[i] - 1 - a[i];如果得出呢比如说：

序列 3 6 9 0 8 5 7 4 2 1 把3移到后面，则它的逆序数会减少3个（0 2 1） 但同时会增加 n - a[i] - 1个。

对于1中如何求其出现的次数呢？具体见Update函数 原理是，由开始往后更新，每输一个数就在其对应的位置标志其出现过。如输了 3 6 9 则 node[u].l = node[u].r = 3 6 9 的sum都为1 当输入0时，查找区间1～10内之前输入的有哪些数出现就是它的逆序数 此时 3 6 9 都出现过了

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

#define manx 5005
struct Tree
{
	int left;
	int right;
	int num;
}tree[4 * manx];
int a[manx];

void BuildTree(int i, int l, int r);
void Update(int i, int id);
int Query(int i, int l, int r);

int main()
{
	int n;
	while(~scanf("%d", &n))
	{
		int ans = 0;
		BuildTree(1, 1, n);
		for(int i = 0; i < n; i++)
		{
			scanf("%d", &a[i]);
			Update(1, a[i] + 1);
			ans += Query(1, a[i] + 2, n);
			//printf("ans = %d
", ans);
		}
		int m = ans;
		for(int i = 0; i < n; i++)
		{
			m = m + n - 2 * a[i] - 1;
			if(m < ans)
				ans = m;
		}
		printf("%d
", ans);
	}
	return 0;
}

void BuildTree(int i, int l, int r)
{
	tree[i].left = l;
	tree[i].right = r;
	tree[i].num = 0;
	if(tree[i].left == tree[i].right) return;
	int mid = (l + r) >> 1;
	BuildTree(i << 1, l, mid);
	BuildTree(i << 1 | 1, mid + 1, r);
}

void Update(int i, int id)
{
	if(tree[i].left == id && tree[i].right == id)
	{
		tree[i].num++;//以防有重复的点
		return;
	}
	int mid = (tree[i].left + tree[i].right) >> 1;
	if(id > mid)  Update(i << 1 | 1, id);
	else   Update(i << 1, id);
	tree[i].num = tree[i << 1].num + tree[i << 1 | 1].num;
}

int Query(int i, int l, int r)
{
	//printf("%d %d %d
", i, l, r);
	if(l > r) return 0;
	if(tree[i].left == l && tree[i].right == r) return tree[i].num;
	int mid = (tree[i].left + tree[i].right) >> 1;

	if(r <= mid) return Query(i << 1, l, r);
	else if(l > mid) return Query(i << 1 | 1, l, r);
	else return Query(i << 1, l, mid) + Query(i << 1 | 1, mid + 1, r);
}

HDU 1394 Minimum Inversion Number（线段树单点更新）

相关推荐