作者：一根吃兔子的萝卜 | 来源：互联网 | 2014-08-22 18:11
Problem Description
The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i 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
Sample Output
Author
CHEN, Gaoli
Source
求最小逆序对数，什么事逆序数呢？ 这是对于两个数来说的，例如 2 1, 2在1的前面，2却比1大，那么就是一对逆序对数，
题目求将序列头一个依次放到末尾，这么多序列中逆序对数最少的输出来
首先数据太大，应该用线段树，线段树里面存储的是le 到 ri 的数的数量，例如输入 3，我们就要查询 0到3有多少个已经存在的数
，废话不多说了，直接看代码吧
#include
#include
#include
#include
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)
using namespace std;
#define N 5005
int a[N];
struct stud{
int le,ri;
int va;
}f[N*4];
void build(int pos,int le,int ri)
{
f[pos].le=le;
f[pos].ri=ri;
f[pos].va=0;
if(le==ri) return ;
int mid=MID(le,ri);
build(L(pos),le,mid);
build(R(pos),mid+1,ri);
}
void update(int pos,int le)
{
f[pos].va++;
if(f[pos].le==le&&f[pos].ri==le)
return ;
int mid=MID(f[pos].le,f[pos].ri);
if(mid>=le)
update(L(pos),le);
else
update(R(pos),le);
}
int query(int pos,int le,int ri)
{
if(f[pos].le>=le&&f[pos].ri<=ri)
return f[pos].va;
int mid=MID(f[pos].le,f[pos].ri);
if(mid>=ri)
return query(L(pos),le,ri);
else
if(mid
京公网安备 11010802041100号