用树状数组 求逆序对 pascal语言

用树状数组 求逆序对 pascal语言

var
n,i,ans,j,t,m:longint;
a,b,c:array[0..200000] of longint;
function lowbit(i:longint):longint;
begin
exit(i and (-i));
end;
procedure add(k:longint);
var
t:longint;
begin
while k<=n do
begin
inc(c[k]);
inc(k,lowbit(k));
end;
end;
function getsum(k:longint):longint;
begin
getsum:=0;
while k>0 do
begin
inc(getsum,c[k]);
dec(k,lowbit(k));
end;
end;
procedure qsort(l,r:longint);
var
i,j,t,p:longint;
begin
if l>=r then exit;
i:=random(r-l+1)+l;t:=a[i];p:=b[i];
a[i]:=a[l];b[i]:=b[l];i:=l;j:=r;
while i begin
while (i while (i if i=j then break;a[j]:=a[i];b[j]:=b[i];dec(j);
end;
a[i]:=t;b[i]:=p;
qsort(l,i-1);qsort(i+1,r);
end;
begin
randomize;
read(n);
for i:=1 to n do
begin
read(a[i]);
b[i]:=i;
end;
qsort(1,n);c:=a;
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;
write(ans);
end.