陈启峰SizeBalancedTree官方源码

《陈启峰SizeBalancedTree官方源码》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、{$inlineon}programCQF_SBT;constmaxn=2000000;varkey,s,left,right,a,b:array[0..maxn]oflongint;tt,q:longint;procedureinit;beginreadln(q);forq:=1toqdoreadln(a[q],b[q]);end;procedurework;vart,k:longint;procedureright_rotate(vart:longint);inline;begink:=left[

2、t];left[t]:=right[k];right[k]:=t;s[k]:=s[t];s[t]:=s[left[t]]+s[right[t]]+1;t:=k;end;procedureleft_rotate(vart:longint);inline;begink:=right[t];right[t]:=left[k];left[k]:=t;s[k]:=s[t];s[t]:=s[left[t]]+s[right[t]]+1;t:=k;end;proceduremaintain(vart:longint

3、;flag:boolean);inline;beginifflag=falsethenifs[left[left[t]]]>s[right[t]]thenright_rotate(t)elseifs[right[left[t]]]>s[right[t]]thenbeginleft_rotate(left[t]);right_rotate(t);endelseexitelseifs[right[right[t]]]>s[left[t]]thenleft_rotate(t)elseifs[left[rig

4、ht[t]]]>s[left[t]]thenbeginright_rotate(right[t]);left_rotate(t);endelseexit;maintain(left[t],false);maintain(right[t],true);maintain(t,true);maintain(t,false);end;procedureinsert(vart,v:longint);inline;beginift=0thenbegininc(tt);t:=tt;key[t]:=v;s[t]:=1

5、;left[t]:=0;right[t]:=0;endelsebegininc(s[t]);ifv=key[t]);end;end;functiondelete(vart:longint;v:longint):longint;inline;begindec(s[t]);if(v=key[t])or(vkey[t])and(

6、right[t]=0)thenbegindelete:=key[t];if(left[t]=0)or(right[t]=0)thent:=left[t]+right[t]-0elsekey[t]:=delete(left[t],key[t]+1);endelseifv

7、nift=0thenexit(false);ifv

8、nselect(vart:longint;k:longint):longint;inline;beginifk=s[left[t]]+1thenexit(key[t]);ifk<=s[left[t]]thenselect:=select(left[t],k)elseselect:=select(right[t],k-1-s[left[t]]);end;functionpred(vart,v:longint):longint;inline;beginift