This seems like a very good problem unfortunately my mind has been unable to make much progress. Therefore hints would be very appreciated :D. Here is the problem:
Today, we have a very interesting problem for you. Given an array A of N integers indexed from 1 to N, you need to perform following two types of queries :
• Change the value of A[x] to k.
• Find the kth ranked element in the subarray A[x..y] (x and y inclusive). An element is said to have kth rank if its position is k when the subarray is sorted in ascending order.
Can you perform these queries efficiently?