Hello there↵
↵
I'm trying to solve this [problem](http://www.spoj.com/problems/XXXXXXXX/) with this [code](http://pastebin.com/HfEfjxPL)↵
↵
Now what I'm doing is building a segment tree with a treap in each node that keeps the position of the next equal number in the array for every number in range↵
↵
after numerous WAs i got TL and while testing my code on extreme cases i found out it really does take a very long time to execute for 50000 ... the extreme case↵
↵
My code's complexity is supposedly N*log^2(N) which should be fast for this size of input↵
↵
what am i doing that's so slow ??↵
↵
please help :/↵
↵
UPDATE :: ↵
↵
I used a different approach for insertion and deletion on treaps where if a node already exists i only increase its value instead of inserting a another node↵
↵
that got the runtime to around 14 seconds on the extreme testcase that never ended with my previous code↵
↵
but it's still too much for O(nlog^2n) complexity ...↵
↵
what am i doing wrong and if that's not the way what is ???↵
↵
here's my current [code](http://pastebin.com/uDD6vJmm)
↵
I'm trying to solve this [problem](http://www.spoj.com/problems/XXXXXXXX/) with this [code](http://pastebin.com/HfEfjxPL)↵
↵
Now what I'm doing is building a segment tree with a treap in each node that keeps the position of the next equal number in the array for every number in range↵
↵
after numerous WAs i got TL and while testing my code on extreme cases i found out it really does take a very long time to execute for 50000 ... the extreme case↵
↵
My code's complexity is supposedly N*log^2(N) which should be fast for this size of input↵
↵
what am i doing that's so slow ??↵
↵
please help :/↵
↵
UPDATE :: ↵
↵
I used a different approach for insertion and deletion on treaps where if a node already exists i only increase its value instead of inserting a another node↵
↵
that got the runtime to around 14 seconds on the extreme testcase that never ended with my previous code↵
↵
but it's still too much for O(nlog^2n) complexity ...↵
↵
what am i doing wrong and if that's not the way what is ???↵
↵
here's my current [code](http://pastebin.com/uDD6vJmm)
