SPOJ CODECHEF TEMPLEQ TLE

binary-search
segment-tree
spoj

#1

http://www.codechef.com/problems/TEMPQUE

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.