I tried this problem with segment tree first and got TLE. Then I used square-root but again got TLE. To solve the problem with square-root i used tree which size is sqrt(n) * sqrt(n), where n is the size of the array. In every block of the tree I kept sqrt(n) elements of the array sorted in ascending order. When update occur I push the element in a block where it's index remain and again sort this block. And when i got query operation for every block which is in the range I found how many elements are less than the given value. This can be done with binary search for every block. Please tell me where i should optimize my code. Here you can have a look at my code .
Cant u just use some BIT instead of resorting block everytime?(i mean, to update with O(log(n)) instead of O(sqrt(n)*log(n)))
Then we should compress the value of the array. Isn't it???
I am having problem with it too. First, i used BIT which made complexity of per update log(n) and per query sqrt(n)*log(n) + sqrt(n). But i got TLE. I don't know why! Then, i used 2D BIT and update became log(n)*log(n) and query log(n)*log(n) + sqrt(n). But still getting TLE. Please help me. Here is my Code . Thanks in advance.
UPD: Problem Solved :)