比较裸,可以有好多的优化,比如根本没有删除的点没有加在树套树中的必要,预处理
出来每个不会被删除的值可以减少不少时间,也可以写成树状数组套平衡树,都会快很多
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/
//By BLADEVIL
type
rec =record
left, right, root :longint;
end;
var
n, m :longint;
high, cur :array[..] of longint;
t :array[..] of rec;
b_left, b_right, b_key :array[..] of longint;
b_size :array[..] of longint;
tot :longint;
ans :int64;
procedure swap(var a,b:longint);
var
c :longint;
begin
c:=a; a:=b; b:=c;
end;
procedure insert(var t:longint;v:longint);
begin
if t= then
begin
inc(tot);
t:=tot;
b_size[t]:=;
b_left[t]:=;
b_right[t]:=;
b_key[t]:=v;
end else
begin
inc(b_size[t]);
if v<b_key[t] then insert(b_left[t],v) else insert(b_right[t],v);
end;
end;
function b_delete(var t:longint;v:longint):longint;
begin
dec(b_size[t]);
if (b_key[t]=v) or (v>b_key[t]) and (b_right[t]=) or (v<b_key[t]) and (b_left[t]=) then
begin
b_delete:=b_key[t];
if (b_left[t]=) or (b_right[t]=) then t:=b_left[t]+b_right[t] else
b_key[t]:=b_delete(b_left[t],v+);
end else
if v>=b_key[t] then exit(b_delete(b_right[t],v)) else exit(b_delete(b_left[t],v));
end;
procedure build(x,l,r:longint);
var
mid :longint;
i :longint;
begin
t[x].left:=l; t[x].right:=r; t[x].root:=;
for i:=l to r do insert(t[x].root,high[i]);
if l=r then exit;
with t[x] do mid:=(left+right) div ;
build(*x,l,mid);
build(*x+,mid+,r);
end;
function b_less(var t:longint;v:longint):longint;
begin
if t= then exit();
if b_key[t]>=v then exit(b_less(b_left[t],v)) else
exit(b_size[b_left[t]]++b_less(b_right[t],v));
end;
function less(x,l,r,v:longint):longint;
var
mid :longint;
begin
if (t[x].left=l) and (t[x].right=r) then
exit(b_less(t[x].root,v));
with t[x] do mid:=(left+right) div ;
if mid<l then exit(less(*x+,l,r,v)) else
if mid>=r then exit(less(*x,l,r,v)) else
exit(less(*x,l,mid,v)+less(*x+,mid+,r,v));
end;
function b_greater(var t:longint; v:longint):longint;
begin
if t= then exit();
if b_key[t]<=v then exit(b_greater(b_right[t],v)) else
exit(b_size[b_right[t]]++b_greater(b_left[t],v));
end;
function greater(x,l,r,v:longint):longint;
var
mid :longint;
begin
if (t[x].left=l) and (t[x].right=r) then
exit(b_greater(t[x].root,v));
with t[x] do mid:=(left+right) div ;
if mid<l then exit(greater(*x+,l,r,v)) else
if mid>=r then exit(greater(*x,l,r,v)) else
exit(greater(*x,l,mid,v)+greater(*x+,mid+,r,v));
end;
procedure change(x,y,v:longint);
var
mid :longint;
begin
insert(t[x].root,v);
if (t[x].left=t[x].right) then exit;
with t[x] do mid:=(left+right) div ;
if mid<y then change(*x+,y,v) else change(*x,y,v);
end;
procedure delete(x,y,v:longint);
var
mid :longint;
begin
b_delete(t[x].root,v);
if (t[x].left=t[x].right) then exit;
with t[x] do mid:=(left+right) div ;
if mid<y then delete(*x+,y,v) else delete(*x,y,v);
end;
procedure init;
var
i :longint;
begin
read(n,m);
for i:= to n do read(high[i]);
for i:= to n do cur[high[i]]:=i;
build(,,n);
end;
procedure main;
var
i :longint;
x, y :longint;
begin
for i:= to n- do
ans:=ans+less(,i+,n,high[i]);
for i:= to m do
begin
writeln(ans);
read(x);
y:=cur[x];
delete(,y,x);
if y<> then ans:=ans-greater(,,y-,x);
if y<>n then ans:=ans-less(,y+,n,x);
end;
end;
begin
init;
main;
end.