SPOJ CODECHEF TEMPLEQ TLE

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.