﻿HDU 1394 Minimum Inversion Number(线段树)-Ocrosoft

# Minimum Inversion Number

Problem Description
The inversion number of a given number sequence a1, a2, …, an is the number of pairs (ai, aj) that satisfy i < j and ai > aj.
For a given sequence of numbers a1, a2, …, an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:
a1, a2, …, an-1, an (where m = 0 – the initial seqence)
a2, a3, …, an, a1 (where m = 1)
a3, a4, …, an, a1, a2 (where m = 2)

an, a1, a2, …, an-1 (where m = n-1)
You are asked to write a program to find the minimum inversion number out of the above sequences.

Input
The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 5000); the next line contains a permutation of the n integers from 0 to n-1.

Output
For each case, output the minimum inversion number on a single line.

Sample Input
```

10
1 3 6 9 0 8 5 7 4 2

```

Sample Output
```

16

```

Author
CHEN, Gaoli

Solution

(线段树封装真难，这次还要注释掉最后那一句。)

```#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
//#include "inc/SegmentTree.h"//线段树
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
#define  rep(a,b) for(int a=0;a<b;a++)
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 5000 + 10;
const int MOD = 1000000009;
int gcd(int a, int b)
{
if (!b)return a;
return gcd(b, a%b);
}
using namespace std;
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
/*(◕‿‿◕) 签订契约,成为马猴烧酒吧 (◕‿‿◕)*/
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/

template <typename T>
class SegmentTree
{
private:
T *sum;//区间和
T *a = nullptr;//初始数据
int left, right;//左端点，右端点
private:
/// <summary>
/// 线段树构建
/// </summary>
/// <param name="pos">数组中的位置</param>
/// <param name="left">区间左端点</param>
/// <param name="right">区间右端点</param>
/// <param name="empty">是否创建空树</param>
void build(int pos, int left, int right, bool empty = false)
{
if (left == right)
{
if (!empty)sum[pos] = a[left];
}
else
{
int mid = (left + right) >> 1;
build(pos * 2, left, mid, empty);
build(pos * 2 + 1, mid + 1, right, empty);
sum[pos] = sum[pos * 2] + sum[pos * 2 + 1];
}
}
/// <summary>线段树区间更新</summary>
/// <param name="pos">数组中的位置</param>
/// <param name="left">区间左端点</param>
/// <param name="right">区间右端点</param>
void pushDown(int pos, int left, int right)
{
int mid = (left + right) >> 1;
sum[pos * 2] += add[pos] * (mid - left + 1);
sum[pos * 2] += add[pos] * (right - mid);
}
public:
///<summary>左端点为1，数组起始位置为1，区间为整个数组，构建线段树\n</summary>
///<param name="Size">线段树大小</param>
///<param name="Array">初始数据数组,数据要从Array[1]开始，为nullptr时创建空树</param>
SegmentTree(int Size, T *Array)
{
sum = new T[4 * Size];
add = new T[4 * Size];
this->a = Array;//保留引用
this->left = 1; this->right = Size;
build(1, 1, Size, Array == nullptr ? true : false);
}
///<summary>指定左端点，数组起始位置，区间大小，构建线段树</summary>
///<param name="Size">线段树大小</param>
///<param name="Array">初始数据数组，为nullptr时创建空树</param>
///<param name="pos">数组中的位置</param>
///<param name="left">区间左端点</param>
///<param name="right">区间右端点</param>
SegmentTree(int Size, T *Array, int pos, int left, int right)
{
sum = new int[10 * Size];
add = new int[10 * Size];
this->a = Array;//保留引用
this->left = left; this->right = right;
build(pos, left, right, Array == nullptr ? true : false);
}
~SegmentTree()
{
delete sum;
};
/// <summary>
/// 清空数组，相对比较费时，一般不需要使用
/// </summary>
void clear()
{
memset(sum, 0, sizeof(sum));
}
/// <summary>线段树单点更新(简易版，仅适用于默认构造的线段树)</summary>
/// <param name="opPoint">操作点</param>
/// <param name="value">数值</param>
void insert(int opPoint, T value)
{
insert(opPoint, opPoint, value);
}
/// <summary>线段树区间更新(简易版，仅适用于默认构造的线段树)</summary>
/// <param name="opLeft">操作区间左端点</param>
/// <param name="opRight">操作区间右端点</param>
/// <param name="value">数值</param>
void insert(int opLeft, int opRight, T value)
{
insert(1, left, right, opLeft, opRight, value);
}
/// <summary>线段树单点更新</summary>
/// <param name="pos">数组中的位置</param>
/// <param name="left">区间左端点</param>
/// <param name="right">区间右端点</param>
/// <param name="opPoint">操作点</param>
/// <param name="value">数值</param>
void insert(int pos, int left, int right, int opPoint, T value)
{
insert(pos, left, right, opPoint, opPoint, value);
}
/// <summary>线段树区间更新</summary>
/// <param name="pos">数组中的位置</param>
/// <param name="left">区间左端点</param>
/// <param name="right">区间右端点</param>
/// <param name="opLeft">操作区间左端点</param>
/// <param name="opRight">操作区间右端点</param>
/// <param name="value">数值</param>
void insert(int pos, int left, int right, int opLeft, int opRight, T value)
{
/*标记下传*/
if (add[pos] != 0)pushDown(pos, left, right);
/*操作区间包含线段树区间*/
if (opLeft <= left&&right <= opRight)
{
sum[pos] += (right - left + 1)*value;
}
/*拆分对左右进行更新*/
else
{
int mid = (left + right) >> 1;
if (opLeft <= mid)insert(pos * 2, left, mid, opLeft, opRight, value);
if (opRight > mid)insert(pos * 2 + 1, mid + 1, right, opLeft, opRight, value);
sum[pos] = sum[pos * 2] + sum[pos * 2 + 1];
}
}
/// <summary>线段树区间查询(简易版，仅适用于默认构造的线段树)</summary>
/// <param name="queryLeft">查询区间左端点</param>
/// <param name="queryRight">查询区间右端点</param>
T query(int queryLeft, int queryRight)
{
return query(1, left, right, queryLeft, queryRight);
}
/// <summary>线段树区间查询</summary>
/// <param name="pos">数组中的位置</param>
/// <param name="left">区间左端点</param>
/// <param name="right">区间右端点</param>
/// <param name="queryLeft">查询区间左端点</param>
/// <param name="queryRight">查询区间右端点</param>
T query(int pos, int left, int right, int queryLeft, int queryRight)
{
/*标记下传*/
if (add[pos] != 0)pushDown(pos, left, right);
if (queryLeft <= left&&right <= queryRight)
return sum[pos];
/*拆分对左右进行更新*/
else
{
int mid = (left + right) >> 1; T ans = 0;
if (queryLeft <= mid)ans += query(pos * 2, left, mid, queryLeft, queryRight);
if (queryRight > mid)ans += query(pos * 2 + 1, mid + 1, right, queryLeft, queryRight);
//sum[pos] = sum[pos * 2] + sum[pos * 2 + 1];
return ans;
}
}
};
int main()
{
int n;
int a[MAXN];
while (cin >> n)
{
ms(a);
SegmentTree<int> st(n, nullptr, 1, 0, n - 1); st.clear();
int ans = 0;
rep(i, n)
{
scanf("%d", &a[i]);
ans += st.query(1, 0, n - 1, a[i] + 1, n - 1);
st.insert(1, 0, n - 1, a[i], 1);
}
int minn = ans;
rep(i, n)
{
ans = ans + n - 2 * a[i] - 1;
if (ans < minn)minn = ans;
}
printf("%d\n", minn);
}
return 0;
}```