本文主要是介绍SBT(pet)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题：HNOI2004 宠物收养所
方法：SBT 维护
program size_balanced_tree;{$inline on}
constmaxn=80000;
typepoint=^longint;
vars,l,r,w:array[0..maxn] of longint; a,b:point;ans,m,t,k,now,root,sto:longint;
procedure left(var i:longint);inline;
var j:longint;
beginj:=r[i];r[i]:=l[j];l[j]:=i;s[j]:=s[i];s[i]:=s[l[i]]+s[r[i]]+1;i:=j;
end;
procedure right(var i:longint);inline;
var j:longint;
beginj:=l[i];l[i]:=r[j];r[j]:=i;s[j]:=s[i];s[i]:=s[l[i]]+s[r[i]]+1;i:=j;
end;
procedure maintain(var t:longint; flag:boolean);inline;
beginif not flag then beginif s[l[l[t]]]>s[r[t]] then right(t) elseif s[r[l[t]]]>s[r[t]] then begin left(l[t]); right(t);end else exit;end else beginif s[r[r[t]]]>s[l[t]] then left(t) elseif s[l[r[t]]]>s[l[t]] then begin right(r[t]); left(t);end else exit;end;maintain(l[t],false);maintain(r[t],true);maintain(t,false);maintain(t,true);
end;
procedure insert(var x:longint; const k:longint);
beginif x=0 then begin inc(sto); x:=sto; w[x]:=k; s[x]:=1; exit; end;inc(s[x]); if k<w[x] then insert(l[x],k) else insert(r[x],k);maintain(x,k>=w[x]);
end;
procedure delete(var x:longint);
beginif (l[x]=0)or(r[x]=0) then begin x:=l[x]+r[x]; exit; end;left(x);right(l[x]);delete(r[l[x]]);
end;
function pred(var x:longint; const k:longint):point;
beginif (x=0)or(k=w[x]) then exit(@x);if k<w[x] then pred:=pred(l[x],k)else beginpred:=pred(r[x],k);if pred^=0 then exit(@x);end;
end;
function succ(var x:longint; const k:longint):point;
beginif (x=0)or(k=w[x]) then exit(@x);if k>w[x] then succ:=succ(r[x],k)else beginsucc:=succ(l[x],k);if succ^=0 then exit(@x);end;
end;
function getch:char; var k:byte;
beginfor k:=1 to 5 do read(getch);
end;
procedure readspace; var ch:char;
begin repeat read(ch); until ch=' '; end;beginassign(input,'input.txt'); reset(input); assign(output,'output.txt'); rewrite(output);readln(m);for m:=1 to m do beginreadln(t,k);if root=0 then now:=t;if t=now then begin insert(root,k); continue; end;a:=pred(root,k);b:=succ(root,k);if a^=0 then begin add(ans,w[b^]-k); delete(b^); end elseif b^=0 then begin add(ans,k-w[a^]); delete(a^); end elseif k-w[a^]<=w[b^]-k thenbegin add(ans,k-w[a^]); delete(a^); end elsebegin add(ans,w[b^]-k); delete(b^); end; end;writeln(ans);close(input); close(output);
end.
这篇关于SBT(pet)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
