I have this problem and haven't solve it, yet. who has any idea, please give me :)
the problem is: give a sequence with n elements (n<=10^6), for example 4 3 2 1 and 2 number L,R (left and right)
count how many pair (i,j), i<=j that:
someone will think this problem is easy, but the normal solution is O(n^2), and it will be run in long time. (limit is 3s). So, anyone else has some idea. I think this problem can solve in O(NlogN).