Help me in solving RMID2 - Running Median Again problem from SPOJ.
@vikram91 @rs_710 @purendra_ @hemanth_1 @shraeyas @vidyut_1 @aryanc403 @meooow @alexthelemon @vijju123 @ram_24 @harrypotter0 @pankaj_chopra @algmyr
Use segment tree and compression
Process it offlyn,so that u know what values are going to be there ,map values to small values
Now create a segment tree which stores no.of elements in a range ,so each time if +1,add to segment,if -1,we know how many elements we have so query the segment tree for the n/2th element assumning we have n elements upto now(we can easily calculate xth element-if left child value>=x ,xth element lies in left part,else in right part)
We can delete the median after that