BZOJ

BZOJ 3295

论线段树の日常MLE…

传送门

一个数的逆序对数=前面比它大的+后面比它小的

设这个数$k$是第$i$个，那么它的逆序对数就是$root[1]-root[i-1]$中范围在$[k+1,n]$里的数的个数+$root[i+1]-root[n]$中范围在$[1,k-1]$里的数的个数

每次删除时从答案中减去它的影响，并修改一下线段树就可以了

开始呢…我逗比地在每次修改时又完全新建了一条$\log n$长度的链…空间复杂度$(n+m)(\log n)^2$…

卡了半天内存发现完全可以利用老版本节点…QAQ


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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
program bzoj_3295;
var s:array[0..10000000]of record lc,rc,size:longint; end;
    root,pos,seq:array[0..100000]of longint;
    n,m,i,tot,p,len,x:longint;
    b:array[1..17]of longint;
    ans:int64;
 
function lowbit(x:longint):longint;
begin
  exit(x and -x);
end;
 
procedure init(x:longint);
begin
  len:=0;
  while x>0 do
  begin
    inc(len);
    b[len]:=root[x];
    dec(x,lowbit(x));
  end;
end;
 
procedure modify(var t:longint;l,r,p,d:longint);
var mid:longint;
begin
  if t=0 then
  begin
    inc(tot);
    t:=tot;
  end;
  inc(s[t].size,d);
  if l=r then exit;
  mid:=(l+r)>>1;
  if p<=mid then modify(s[t].lc,l,mid,p,d) else modify(s[t].rc,mid+1,r,p,d);
end;
 
function query(l,r,ll,rr:longint):longint;
var i,t,mid:longint;
    p:array[1..17]of longint;
begin
  t:=0;
  if (ll<=l)and(rr>=r) then
  begin
    for i:=1 to len do inc(t,s[b[i]].size);
    exit(t);
  end;
  mid:=(l+r)>>1;
  for i:=1 to len do p[i]:=b[i];
  if ll<=mid then
  begin
    for i:=1 to len do b[i]:=s[p[i]].lc;
    inc(t,query(l,mid,ll,rr));
  end;
  if rr>mid then
  begin
    for i:=1 to len do b[i]:=s[p[i]].rc;
    inc(t,query(mid+1,r,ll,rr));
  end;
  for i:=1 to len do b[i]:=p[i];
  exit(t);
end;
 
function count(l,r,ll,rr:longint):longint;
begin
  if l>r then exit(0);
  init(r);
  count:=query(1,n,ll,rr);
  init(l-1);
  dec(count,query(1,n,ll,rr));
end;
 
begin
  readln(n,m);
  tot:=0;
  fillchar(root,sizeof(root),0);
  for i:=1 to n do
  begin
    readln(seq[i]);
    pos[seq[i]]:=i;
    p:=i;
    while p<=n do
    begin
      modify(root[p],1,n,seq[i],1);
      inc(p,lowbit(p));
    end;
  end;
  ans:=0;
  for i:=1 to n do inc(ans,count(i+1,n,1,seq[i]));
  for i:=1 to m do
  begin
    writeln(ans);
    readln(x);
    dec(ans,count(1,pos[x]-1,x,n)+count(pos[x]+1,n,1,x));
    p:=pos[x];
    while p<=n do
    begin
      modify(root[p],1,n,x,-1);
      inc(p,lowbit(p));
    end;
  end;
end.