浅谈逆序对做法

由于最近考试触及到了逆序对,所以这里来讲一下这个最简单的做法。

权值线段树做法

我们知道逆序对定义: a[i]>a[j] 且 i<j,所以朴素发方法就很容易想到。

1
2
3
for i:=1 to n do
     for j:=i+1 to n do 
           Operate;

然后我们试着把O(n^2)改为O(nlogn),我们可以把j这个循环删掉,用更伪的代码表示

1
2
3
for i:=1 to n do
         //i前面的比它小的数
          Operate;

然后我们就可以想到前面的数进行存储然后直接查询的方法,然后又可以想到神奇的权值线段树,因为这样子可以保持叶子节点单调,但是需要离散化。

查询操作

我们把那些已经存储的点按照普通线段树区间查询出来就可以了。如图:

4.png

蓝色的部分肯定就是比3小且符合i<j(因为我是倒序插入的)。

插入(修改)操作

修改操作就非常简单,直接在特定位置把数放进去。要注意tree[k]:=tree[k*2]+tree[k*2+1]。

Code

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

var
    n,find,ans:int64;
    i:longint;
    num,place,numm:array[-1..110000] of int64;
    tree:array[-1..440000] of int64;

procedure Query(l,r,k:longint);
var
    mid:longint;
begin
    if (1<=l)and(r<=num[i]) then
    begin
        inc(find,tree[k]);
        exit;
    end;
    mid:=(l+r) div 2;
    if 1<=mid then
        Query(l,mid,k*2);
    if num[i]>mid then
        Query(mid+1,r,k*2+1);
end;

procedure Change(l,r,k:longint);
var
    mid:longint;
begin
    if l=r then
    begin
        inc(tree[k]);
        exit;
    end;
    mid:=(l+r) div 2;
    if num[i]<=mid then
        Change(l,mid,k*2)
    else
        Change(mid+1,r,k*2+1);
    tree[k]:=tree[k*2]+tree[k*2+1];
end;

procedure Sort(l,r:longint);
var
    s,t:int64;
    i,j:longint; 
begin
    i:=l; j:=r; s:=num[(l+r) div 2];
    repeat
        while num[i]<s do i:=i+1;
        while num[j]>s do j:=j-1;
        if i<=j then
        begin
            t:=num[i]; num[i]:=num[j]; num[j]:=t;
            t:=place[i]; place[i]:=place[j]; place[j]:=t;
            inc(i); dec(j);
         end;
    until i>=j;
    if i<r then  Sort(i,r);
    if j>l then  Sort(l,j);
end;

begin
    read(n);
    for i:=1 to n do
    begin
        read(num[i]);
        place[i]:=i;
    end;
    Sort(1,n);
    for i:=1 to n do
        numm[place[i]]:=i;
    num:=numm;

    i:=n;
    Change(1,n,1);
    for i:=n-1 downto 1 do
    begin
        find:=0;
        Query(1,n,1);
        inc(ans,find);
        Change(1,n,1);
    end;
    writeln(ans);
end.