本文主要是介绍hdu1394 Minimum Inversion Number 单点更新，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
首先题目有两个要点：
1.求出原序列的逆序数
2.求出n次移动第一个位置数到最后的逆序数。
对于第一个要点，实际上用暴力也可以解决，当然最好转到线段树的概念上来。
以下我就引用一下别人的话好了。
/ *
先以区间[0,9]为根节点建立val都为0的线段树,再看看怎样求下面序列的逆序数:
1 3 6 9 0 8 5 7 4 2
在线段树中插入1, 插入之前先询问区间[1,9]已插入的节点数(如果存在,必与1构成逆序) v1=0
在线段树中插入3, 插入之前先询问区间[3,9]已插入的节点数(如果存在,必与3构成逆序) v2=0
在线段树中插入6, 插入之前先询问区间[6,9]已插入的节点数(如果存在,必与6构成逆序) v3=0
在线段树中插入9, 插入之前先询问区间[9,9]已插入的节点数(如果存在,必与9构成逆序) v4=0
在线段树中插入0, 插入之前先询问区间[0,9]已插入的节点数(如果存在,必与0构成逆序) v5=4
在线段树中插入8, 插入之前先询问区间[8,9]已插入的节点数(如果存在,必与8构成逆序) v6=1
在线段树中插入5, 插入之前先询问区间[5,9]已插入的节点数(如果存在,必与5构成逆序) v7=3
在线段树中插入7, 插入之前先询问区间[7,9]已插入的节点数(如果存在,必与7构成逆序) v8=2
在线段树中插入4, 插入之前先询问区间[4,9]已插入的节点数(如果存在,必与4构成逆序) v9=5
在线段树中插入2, 插入之前先询问区间[2,9]已插入的节点数(如果存在,必与2构成逆序) v10=7
累加v1+……+v10 =22，这就是1 3 6 9 0 8 5 7 4 2的逆序数了.
*/
第二点：由于数字0~n-1都是连续的，那么我每次把第一个数字移到最后。
例如，我第一个位置的数字是3，那么移动后。
原本不是逆序数对就变成了逆序数对；
原本是逆序数对的就变成了非逆序数对。
所增加的逆序数对 = n-3-1；
所减少的逆序数对 = 3；
这样基本就不难理解了~
以下放出AC代码：
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <iostream>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define min(a,b) a<b?a:b
using namespace std;
const int p = 5005;
int sum [ p<<2 ],cot,a[p];
void build (int l ,int r ,int rt)
{sum[rt]=0;if(l==r)return;int mid = (l + r) >> 1;build(lson);build (rson);
}void query(int l ,int r ,int rt, int x,int y)
{if(x<=l&&r<=y){cot+=sum[rt];return;}int mid = (l + r) >> 1;if(x<=mid) query(lson,x,y);if(y>mid) query(rson,x,y);
}void update(int l ,int r ,int rt,int num)
{if(l == r){sum[rt]=1;return;}int mid = (l + r)>>1;if(num<=mid) update(lson,num);if(num>mid) update(rson,num);sum[ rt ]=sum[ rt<<1 ]+sum[ rt<<1|1 ];
}
int main()
{int N,temp;while(scanf("%d",&N)!=EOF){build(0,N-1,1);cot=0;for(int i=1;i<=N;i++){scanf("%d",&a[i]);query(0,N-1,1,a[i],N-1);update(0,N-1,1,a[i]);}int minn=cot;for(int i=1;i<=N;i++){cot = cot - a[i] + N - a[i] - 1 ;minn = min(minn,cot);}printf("%d\n",minn);}return 0;
}
这篇关于hdu1394 Minimum Inversion Number 单点更新的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
