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.