treap！
var i,n,x,y,ans,a,b,root,tot,ft:longint; l,r,s,v,hr:array[0..100000] of longint; procedure r_rotate(var x:longint); var y:longint; begin y:=l[x]; l[x]:=r[y]; r[y]:=x; s[y]:=s[x]; s[x]:=s[l[x]]+s[r[x]]+1; x:=y; end; procedure l_rotate(var x:longint); var y:longint; begin y:=r[x]; r[x]:=l[y]; l[y]:=x; s[y]:=s[x]; s[x]:=s[l[x]]+s[r[x]]+1; x:=y; end; procedure insert(var k,key:longint); begin if k=0 then begin inc(tot); k:=tot; l[k]:=0; r[k]:=0; s[k]:=1; v[k]:=key; hr[k]:=random(maxlongint); exit; end; inc(s[k]); if key<=v[k] then begin insert(l[k],key); if hr[l[k]]>hr[k] then r_rotate(k); end else begin insert(r[k],key); if hr[r[k]]>hr[k] then l_rotate(k); end; end; function delete(var k:longint;key:longint):longint; begin dec(s[k]); if (key=v[k]) or ((key<=v[k]) and (l[k]=0)) or ((key>v[k]) and (r[k]=0)) then begin delete:=v[k]; if (l[k]=0) or (r[k]=0) then k:=l[k]+r[k] else v[k]:=delete(l[k],key+1); exit; end; if key<=v[k] then exit(delete(l[k],key)) else exit(delete(r[k],key)); end; function pre(var k,key:longint):longint; begin if k=0 then exit(-1); if key<=v[k] then exit(pre(l[k],key)) else begin pre:=pre(r[k],key); if pre=-1 then pre:=v[k]; end; end; function suc(var k,key:longint):longint; begin if k=0 then exit(-1); if key>v[k] then exit(suc(r[k],key)) else begin suc:=suc(l[k],key); if suc=-1 then suc:=v[k]; end; end; procedure main; begin readln(n); ans:=0;tot:=0;root:=0;s[root]:=0; for i:=1 to n do begin readln(x,y); if x=ft then insert(root,y) else if s[root]=0 then begin ft:=x; insert(root,y); end else begin a:=pre(root,y);b:=suc(root,y); if a=-1 then a:=-maxlongint div 10; if b=-1 then b:=-maxlongint div 10; if abs(b-y)<abs(y-a) then begin ans:=(ans+abs(b-y)) mod 1000000; b:=delete(root,b); end else begin ans:=(ans+abs(y-a)) mod 1000000; a:=delete(root,a); end; end; end; writeln(ans); end; begin main; end.
插入操作还有另一种写法：
procedure maintain(var t:longint;flag:boolean); begin if not flag then if s[l[l[t]]]>s[r[t]] then right_rotate(t) else if s[r[l[t]]]>s[r[t]] then begin left_rotate(l[t]); right_rotate(t); end else exit else if s[r[r[t]]]>s[l[t]] then left_rotate(t) else if s[l[r[t]]]>s[l[t]] then begin right_rotate(r[t]); left_rotate(t); end else exit; maintain(l[t],false); maintain(r[t],true); maintain(t,true); maintain(t,false); end; procedure insert(var t,v:longint); begin if t=0 then begin inc(tt); t:=tt; s[t]:=1; l[t]:=0; r[t]:=0; key[t]:=v; end else begin inc(s[t]); if v<key[t] then insert(l[t],v) else insert(r[t],v); maintain(t,v>=key[t]); end; end;
还需要注意的是，如果题目中明确要求求前驱，即小于它的最大数。那么pre操作的返回值应设为正在查找中的关键值，这样可以使整个操作的返回值不会与原值相同。
如果题中并没有说明必须不同，例如本题，一个数的前驱可以是这个数，那么pre的返回值应设为-1.
（update：20140810 这不叫另一种写法。。。这叫SBT。。。当时真无知）