### brdy's blog

By brdy, history, 3 years ago, Here is my AC code: https://hastebin.com/ewobuzater.cpp

It uses offline BIT + sorting.

Here is the strange thing: que works perfectly fine, but if you change it to que it will segfault. However, it is zero based indexing and q is at max 200000.

Can anyone think of a case where que faces out of bound access?  Comments (5)
 » Since I am new to this programming will you please explain your solution?
•  » » que[] stores the queriesThe idea behind my solution is that instead of solving for each query individually, we sort them in decreasing order of k.Now we can change this problem into:Which values are greater than k?Think about a binary array:1 means that the number in the i'th position is greater than k, and 0 means it is not.How to find how many is greater from position [i,j]?We use some data structures such as segment tree/BIT which gives us range sum in O(logn) and allows us to set a position to 1 in O(logn).We can make the observation that if a > b and the value v > a, then v > b.Thus, once we go from a higher k to a lower k, the values greater than the higher k will also be greater than the lower k. This is why we sort it in decreasing order.We query [l,r] like prefix sums in the bit to count which ones are greater.Since queries are not in the order they came in we need another array to store answers.Complexity is O(q + nlogn)Solution is very similar to classical problem of counting inversions with BIT + sorting.
•  » » » thanks,I got it now..
 » 3 years ago, # | ← Rev. 2 →   Your operator< returns true for equal elements. sort assumes this is not the case to save some out-of-bounds checks; the extra que element is probably acting as a sentinel. You shouldn't need the extra position if you replace the implementation by return one.k > two.k.
•  » » Thanks, I tried that and it works.