杭电 hdu 1394 Minimum Inversion Number 【线段树 + 详细诠释 + 有难度】

杭电 hdu 1394 Minimum Inversion Number 【线段树 + 详细注释 + 有难度】

/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------//    Copyright (c) 2011 panyanyany All rights reserved.    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1394    Name  : 1394 Minimum Inversion Number    Date  : Saturday, September 17, 2011    Time Stage : 4 hours    Result: 46189412011-09-17 18:27:45Accepted139462MS280K2745 BC++pyy46189082011-09-17 18:22:09Accepted139462MS280K2707 BC++pyy46189032011-09-17 18:21:09Compilation Error13940MS0K1662 BC++pyyTest Data :Review :呃，线段树，难度还是蛮大的。一看就不会做，然后看解题报告，一开始看不明白，人家的都没注释，真是很纠结啊，后来终于明白了什么是“逆序数”以及下面所述的特性，然后线段树的部分就只有自己想了……希望大家以后写代码也能多加点注释，即能锻炼自己的书写能力，理清思路，又能帮助后进的学生，同时将此美德于万万人类中传承下去，何乐而不为呢……//----------------------------------------*/#include <stdio.h>#include <string.h>int max (int lhs, int rhs){return (lhs > rhs ? lhs : rhs) ;}int min (int lhs, int rhs){return lhs < rhs ? lhs : rhs ;}typedef struct {int left, right ;int sum ;} NODE ;#define MAXSIZE 5001int n ;int a[MAXSIZE] ;NODE segTree[MAXSIZE * 2] ;// 构造线段树void build (int id, int left, int right){segTree[id].left= left ;segTree[id].right= right ;segTree[id].sum = 0 ;if (left == right)return ;int mid = (left + right) / 2 ;build (id * 2, left, mid) ;build (id * 2 + 1, mid + 1, right) ;}int query (int id, int left, int right){// 当前节点所代表的区间与要查找的区间 (left, right) 没有交集if (segTree[id].left > right || segTree[id].right < left)return 0 ;// 当前节点所代表的区间在要查找的区间之内if (left == segTree[id].left && segTree[id].right == right)return segTree[id].sum ;int mid = (segTree[id].left + segTree[id].right) / 2 ;int sum = 0 ;if (right < mid)// 若待查区间在当前区间的左半边sum += query (id * 2, left, right) ;// 若待查区间在当前区间的右半边, 可能是 hdu 数据不严谨，// 下面判断中换成 mid < left 也能过……else if (mid + 1 < left)sum += query (id * 2 + 1, left, right) ;else// 若待查区间 横跨 当前区间的中部sum += query (id * 2, left, mid) + query (id * 2 + 1, mid + 1, right) ;return sum ;}int update (int id, int val){// 找到叶子if (segTree[id].left == val && segTree[id].right == val){return segTree[id].sum = 1 ;}// val 不在当前节点所代表的范围内if (segTree[id].left > val || segTree[id].right < val)return 0 ;int mid = (segTree[id].left + segTree[id].right) / 2 ;// val 分布在当前区间的右半边if (mid < val)// 不能等于segTree[id].sum += update (id * 2 + 1, val) ;// val 分布在当前区间的左半边elsesegTree[id].sum += update (id * 2, val) ;return 1 ;}int main (){int i, j ;int sum, res ;while (scanf ("%d", &n) != EOF){// 构造线段树build (1, 1, n) ;sum = 0 ;for (i = 0 ; i < n ; ++i){scanf ("%d", &a[i]) ;// 查询比 a[i] 大的数是否出现过，返回出现的次数，// 即为 满足 x > a[i] 的逆序数对sum += query (1, a[i] + 1, n - 1) ;// 查询完之后，将 a[i] 加入线段树中update (1, a[i]) ;}// 首先要知道这么个性质：对任意的一列逆序数，设其第一个数为 a // 则在 a 之后比 a 小的数必然有 a 个：0, 1, 2, ... , a - 1res = sum ;for (i = 0 ; i < n ; ++i){sum = sum - a[i] + (n - a[i] - 1) ;res = min (res, sum) ;}printf ("%d\n", res) ;}return 0 ;}