I was barely able to pass the TL by using the segment tree. That part probably works OK, but what causes troubles is the way I locate the array index by given content value (i.e. we want do delete 8, so I search for 8's index and replace it with 0). For that purpose I was using map from STL and wasn't able to come up with anything better (except some hash-like storage). What did you use for that purpose or could you avoid such situation at all?
Yes it does help. My solution (sqrt) was TLE 17. after this line it is AC 0.421. Just put this into main as the first line. thanks for the suggestion, I was too lazy to use scanf:) dont forget though that if you use this, then you cannot use printf and scanf in the same program with cin