import Ġjava . util . Random Ċ import Ġjava . util . Tree Set Ċ Ċ // Ġhttps :// en . wikipedia . org / wiki / Tre ap Ċ object ĠTre ap Ġ{ ĊĠĠĠ Ġval Ġrandom Ġ= ĠRandom () ĊĊĠĠĠ Ġdata Ġclass ĠTre ap ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġkey : ĠInt , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġleft : ĠTre ap ? Ġ= Ġnull , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġright : ĠTre ap ? Ġ= Ġnull , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġsize : ĠInt Ġ= Ġ 1 , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpri o : ĠLong Ġ= Ġrandom . next Long () ĊĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠ Ġfun Ġupdate () Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsize Ġ= Ġ 1 Ġ+ Ġget Size ( left ) Ġ+ Ġget Size ( right ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġget Size ( root : ĠTre ap ?) Ġ= Ġroot ?. size Ġ?: Ġ 0 ĊĊĠĠĠ Ġfun Ġsplit ( root : ĠTre ap ?, Ġmin Right : ĠInt ): ĠPair < Tre ap ?, ĠTre ap ?> Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( root Ġ== Ġnull ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠPair ( null , Ġnull ) ĊĠĠĠĠĠĠĠ Ġif Ġ( root . key Ġ>= Ġmin Right ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġleft Split Ġ= Ġsplit ( root . left , Ġmin Right ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroot . left Ġ= Ġleft Split . second ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroot . update () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠPair ( left Split . first , Ġroot ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġright Split Ġ= Ġsplit ( root . right , Ġmin Right ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroot . right Ġ= Ġright Split . first ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroot . update () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠPair ( root , Ġright Split . second ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġmerge ( left : ĠTre ap ?, Ġright : ĠTre ap ?): ĠTre ap ? Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( left Ġ== Ġnull ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġright ĊĠĠĠĠĠĠĠ Ġif Ġ( right Ġ== Ġnull ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġleft ĊĠĠĠĠĠĠĠ Ġif Ġ( left . prio Ġ> Ġright . prio ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft . right Ġ= Ġmerge ( left . right , Ġright ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft . update () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġleft ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġright . left Ġ= Ġmerge ( left , Ġright . left ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġright . update () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġright ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġinsert ( root : ĠTre ap ?, Ġkey : ĠInt ): ĠTre ap ? Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġt Ġ= Ġsplit ( root , Ġkey ) ĊĠĠĠĠĠĠĠ Ġreturn Ġmerge ( merge ( t . first , ĠTre ap ( key )), Ġt . second ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġremove ( root : ĠTre ap ?, Ġkey : ĠInt ): ĠTre ap ? Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġt Ġ= Ġsplit ( root , Ġkey ) ĊĠĠĠĠĠĠĠ Ġreturn Ġmerge ( t . first , Ġsplit ( t . second , Ġkey Ġ+ Ġ 1 ). second ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġk th ( root : ĠTre ap , Ġk : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( k Ġ< Ġget Size ( root . left )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġk th ( root . left !! , Ġk ) ĊĠĠĠĠĠĠĠ Ġelse Ġif Ġ( k Ġ> Ġget Size ( root . left )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġk th ( root . right !! , Ġk Ġ- Ġget Size ( root . left ) Ġ- Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġreturn Ġroot . key ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġprint ( root : ĠTre ap ?) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( root Ġ== Ġnull ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠ Ġprint ( root . left ) ĊĠĠĠĠĠĠĠ Ġprintln ( root . key ) ĊĠĠĠĠĠĠĠ Ġprint ( root . right ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// Ġrandom Ġtest ĊĠĠĠ Ġ@ Jvm Static ĊĠĠĠ Ġfun Ġmain ( args : ĠArray < String >) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġtime Ġ= ĠSystem . currentTimeMillis () ĊĠĠĠĠĠĠĠ Ġvar Ġtre ap : ĠTre ap ? Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġval Ġset Ġ= ĠTree Set < Int >() ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 .. 9 9 9 9 9 9 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġkey Ġ= Ġrandom . nextInt ( 1 0 0 0 0 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( random . next Boolean ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtre ap Ġ= Ġremove ( tre ap , Ġkey ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset . remove ( key ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ(! set . contains ( key )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtre ap Ġ= Ġinsert ( tre ap , Ġkey ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset . add ( key ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( set . size Ġ!= Ġget Size ( tre ap )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthrow ĠRuntimeException () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġget Size ( tre ap )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! set . contains ( k th ( tre ap !! , Ġi ))) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthrow ĠRuntimeException () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġprintln ( System . currentTimeMillis () Ġ- Ġtime ) ĊĠĠĠ Ġ} Ċ } Ċ