[树状数组] Inverse

【问题描述】

给你n个整数，每个数a[i]都是不超过109的非负整数。求其中逆序对的个数，即所有这样的数对(i,j)满足1≤i<j≤n且a[i]>a[j]。

【输入文件】inverse.in

第一行一个正整数n(1≤n≤500000)，代表数字的个数。

接下来一行n个用空格分隔的整数，代表要处理的数字序列。

【输出文件】inverse.out

一行一个整数，代表逆序对的个数。

【样例输入】

5

2 3 1 5 4

【样例输出】

3

【数据及时间与空间限制】

对于20%的数据，n≤20000，对于100%的数据，n≤500000。

时间限制：1秒，空间限制：256MB。

【算法分析】

1.离散化 由于输入数据较为离散，我们对其采用保持大小关系但改变数值的办法，如以9 1 0 5 4为例，离散化后变成5 2 1 4 3，去除冗余内存空间和计算，有助于树状数组的高效运算。

2.树状数组 对于当前操作数a[i]，计算getsum(m)-getsum(a[i]) {m为数列中数字个数} 并用add(a[i])将a[i]加入树状数组。

注：add过程实际为birtree中的change过程，由于本题的特殊性，每次调整数组只需+1，因此调整为add函数，只需一个参数。

【程序描述】

a数组 原始数列

b数组 快速排序后数列，用于离散化。

c数组 树状数组

lowbit函数、add函数、getsum函数 参考Birtree

【反思】

表示我读代码的水平越来越次了，然后快排居然忘记怎么写了跳进死循环了TAT，真心对不起老师啊。

【源程序】

program inverse;
var a,b,c:array[0..500000] of longint;
n,i:longint;
procedure qsort(l,r:longint);
var i,j,mid,temp:longint;
begin
i:=l;j:=r;mid:=a[(l+r) div 2];
while i<=j do
begin
while a[i]<=mid do inc(i);
while a[j]>=mid do dec(j);
if i<=j then
begin
temp:=a[i];a[i]:=a[j];a[j]:=temp;
temp:=b[i];b[i]:=b[j];b[j]:=temp;
inc(i);dec(j);
end;
end;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end;
function lowbit(i:longint):longint;
begin
lowbit:=i-(i and (i-1));
end;
procedure add(i:longint);
begin
while i<=n do
begin
c[i]:=c[i]+1;
i:=i+lowbit(i);
end;
end;
function getsum(i:longint):longint;
begin
getsum:=0;
while i>0 do
begin
getsum:=getsum+c[i];
i:=i-lowbit[i];
end;
end;
begin {main}
readln(n);
for i:=1 to n do
begin
read(a[i]);
b[i]:=i;
end;
qsort(1,n);
c:=a; c[0]:=-1;
for i:=1 to n do
if c[i]<>c[i-1] then
begin
inc(m);a[b[i]]:=m;
end
else
a[b[i]]:=m;
fillchar(c,sizeof(c),0);
for i:=1 to n do
begin
inc(ans,getsum(m)-getsum(a[i]);
add(a[i]);
end;
writeln(ans);
end.