【以前的空间】BIT的两个小小运用

剩下一点点时间，就来说说最近才会的关于bit的两个妙用。

求一组数的逆序对

求最长不下降序列

其实两个东西思想差不多，就已第一个为例讲讲。

就是所有数排一遍后，再按照原序列顺序（从后往前），做如下操作：

1、1-(这个数排名-1）的区间和，结果加到答案中

2、把这个数排名为+1

操作1、2分别对应区间查询和单点修改，于是就是bit维护。

为什么这样就是答案呢？

因为如果有比这个数更小的，且在这个数之后，那么在这个更小的数在之前就已经加入到bit中，也就是排名小于当前数的数且都在bit中的数（也就意味着在这个数之后且小于这个数），便与这个数成逆序对。

最长不下降序列也差不多，只是询问的是区间最值罢了。

最后注意数值重复的情况！！！

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
var
  i,j,k,l,n,ans,tot:longint;
  a,b,c,tree:array[0..100000]of longint;
 
procedure swap(var x,y:longint);
var
  i:longint;
begin
  i:=x;
  x:=y;
  y:=i;
end;
 
procedure qsort(l,r:longint);
var
  i,j,k,mid:longint;
begin
  i:=l;
  j:=r;
  mid:=a[(l+r)>>1];
  repeat
    while a[i]>mid do inc(i);
    while a[j]<mid do dec(j);
    if i<=j then begin
      swap(a[i],a[j]);
      swap(b[i],b[j]);
      inc(i);
      dec(j);
    end;
  until i>j;
  if l<j then qsort(l,j);
  if i<r then qsort(i,r);
end;
 
function lowbit(x:longint):longint;
begin
  exit(x and (-x));
end;
 
function ask(x:longint):longint;
var
  sum:longint;
begin
  sum:=0;
  while x>0 do begin
    inc(sum,tree[x]);
    dec(x,lowbit(x));
  end;
  exit(sum);
end;
 
procedure add(x:longint);
begin
  while x<=n do begin
    inc(tree[x]);
    inc(x,lowbit(x));
  end;
end;
 
begin
  readln(n);
  for i:=1 to n do begin
    read(a[i]);
    b[i]:=i;
  end;
  qsort(1,n);
  tot:=0;
  for i:=n downto 1 do begin
    if a[i]<>a[i+1] then inc(tot);
    c[b[i]]:=tot;
  end;
  for i:=n downto 1 do begin
    ans:=ans+ask(c[i]-1);
    add(c[i]);
    writeln(ans);
  end;
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
var
  a,b,c,tree,f:array[0..100000]of longint;
  i,j,k,l,n,m,tot:longint;
 
procedure swap(var x,y:longint);
var
  i:longint;
begin
  i:=x;
  x:=y;
  y:=i;
end;
 
function max(x,y:longint):longint;
begin
  if x>y then exit(x);
  exit(y);
end;
 
procedure qsort(l,r:longint);
var
  i,j,k,mid:longint;
begin
  i:=l;
  j:=r;
  mid:=a[(l+r)>>1];
  repeat
    while a[i]>mid do inc(i);
    while a[j]<mid do dec(j);
    if i<=j then begin
      swap(a[i],a[j]);
      swap(b[i],b[j]);
      inc(i);
      dec(j);
    end;
  until i>j;
  if l<j then qsort(l,j);
  if i<r then qsort(i,r);
end;
 
function lowbit(x:longint):longint;
begin
  exit(x and (-x));
end;
 
function ask(x:longint):longint;
var
  sum:longint;
begin
  sum:=0;
  while x>0 do begin
    sum:=max(sum,tree[x]);
    dec(x,lowbit(x));
  end;
  exit(sum);
end;
 
procedure add(x,y:longint);
begin
  while x<=n do begin
    tree[x]:=max(tree[x],y);
    inc(x,lowbit(x));
  end;
end;
 
 
begin
  readln(n);
  for i:=1 to n do begin
    read(a[i]);
    b[i]:=i;
  end;
  qsort(1,n);
  tot:=0;
  k:=0;
  for i:=1 to n do begin
    if a[i]<>a[i-1] then inc(tot);
    c[b[i]]:=tot;
  end;
  for i:=n downto 1 do begin
    f[i]:=ask(c[i]-1)+1;
    add(c[i],f[i]);
    if f[i]>k then k:=f[i];
  end;
  writeln(k);
end.