[树状数组] 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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.