Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### brdy's blog

By brdy, history, 9 months ago, ,

Here is my AC code: https://hastebin.com/ewobuzater.cpp

It uses offline BIT + sorting.

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

Can anyone think of a case where que[200000] faces out of bound access?

•
• +2
•

 » 9 months ago, # |   0 Since I am new to this programming will you please explain your solution?
•  » » 9 months ago, # ^ |   0 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.
•  » » » 9 months ago, # ^ |   0 thanks,I got it now..
 » 9 months ago, # | ← Rev. 2 →   0 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.
•  » » 9 months ago, # ^ |   -8 Thanks, I tried that and it works.