http://www.spoj.com/problems/TEMPLEQ/
http://www.codechef.com/problems/TEMPQUE
https://ideone.com/0WIYXr
I have mapped the indices of sorted elements with the original array using HashMap.
The time complexity of my solution is O(logn) for type 1 and 2 queries.
And for type 3 queries its O(n+logn)
I am only using an array,not a segment tree.
Can anyone explain the O(nlogn+ q*log^2n) approach and the O(nlogn+ q*logn) approach?
The solution I posted is taking 9.89 secs on the worst case input of 499999 queries of type 3 and 1 query of type 2.
asked
10 Jan '15, 14:45
1★abeyaar
334●2●21●40
accept rate:
30%