Hi
I couldn't solve this problem, but I think I have some partial result what is slow that's running time is about N*sqrt(N)+Q*sqrt(N)*log(N).
The draft of my solution is: First step change from max norm (L infinity norm) to [L1 norm](http://en.wikipedia.org/wiki/Norm_(mathematics) . This means if we transorm (A,B) pairs to (C,D)=(B-A,B+A), than we can solve the problem with independently in the "x" and the "y" directions (or dimensions). We need to find the range medians of the C's. (and independantly D's.) (Of course after that we need the sum from the medians but I've just mention the position, because it is simpler, and the sum from the medians is very similiar.)
Second step I've sorted C's and calculate every 'v' value of C, and every index 'i' from 1 to n how many C's smaller than v are in the (C_1,C_(i-1)) intervall. I've try to illustrate this (this is a slower solution what I've speed up later..)
C-s: 5,1,8,3
| 1 | 3 | 5 | 8 |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 1 | 1 | 2 | 2 |
| 1 | 1 | 2 | 3 |
| 1 | 2 | 3 | 4 |
The third column third row shows we have 2 smaller or equal value in the (C1-C3) than 5.. So if we would like to find the median of (C2-C4) than we should calculate the last row minus first row, so we've got :
| 1 | 2 | 2 | 3 |
|---|
So the 3 is the median :) (here switch from 1 to 2..).
In the third step I've speed up this solution (and decrease the memory usage) with square root trick and binary search (because this matrix is totally monoton I've "just" store every log N row in this matrix), so I used N*sqrt(N) memory, and the running time was N*sqrt(N)+Q*sqrt(N)*log(N).
I have some bugs so I've just past 4 test, but I don't have time at the weekend to fix this, so I've got some WA, and some TLE. So I would be very interesting how can solve this problem faster?
My first solution(which gets 56.67) was
O(log^3(n)). Instead of sqrt decomposition it makes a segment tree of sorted arrays. http://pastebin.com/PaNcW98Q.My accepted solution was
O(log^2(n))and uses persistent segment tree. As you know problem is: given array a[], for every query [l,r] find the median of [l,r]. As a[i] can be up to 10^9, lets assign every a[i] an id[i] , that for every i, j compare(a[i], a[j])==compare(id[i], id[j]) and id[i]<=10^5 for every i).For every prefix of a[] we can build segment tree for numbers 0..10^5, where every segment [l,r] in segment tree represents count of i , that l<=id[i]<=r. This will take O(n^2) memory. So we can make these segment trees persistent, by adding a[i] from left to right and saving roots for every prefix. Now we can do binary search for median( it is the first number for which count of numbers in [l,r] less than that number is greater than (r-l+1)/2 + 1 ). To calculate count of numbers in [l,r] less than given number we can calculate that number for prefix(r) and substract that number for prefix(l-1) using our segment trees. Here is the code http://pastebin.com/bEM2p7Vq.
Can you link me any tutorial of persistent segment tree ?
http://e-maxx.ru/algo/segment_tree in part "Дерево отрезков с сохранением истории его значений (улучшение до persistent-структуры данных)"
thank you , I once read that topic , but I couldn't understand it , I think I got it now :)
I think it can be improved to
per query: instead of bin-searching for the answer, we traverse our tree from root to leaves and choose whether to go left or right based on how many numbers there are in the current node's right child.
I have thought about that when wrote the comment above, but don't know why I thought that that is wrong idea :) . Everything is clear now, so we have solution to static range kth search problem in O(logn) time.
for each C and D array you must make the pair of the number with it's position and sort it. Then for the permutation of the positions you must build the segment tree , where in each node there is a sorted vector and in the vector all the numbers are which are below that node.if the query is [L,R] you must find (R-L+2)/2 th number such that its position is in segment [L,R] . Now for each Query you must go down from the root of segment tree . check how many numbers are from the segment [L,R] (with binary search) in the left child , if it is less then (R-L+2)/2 go to the right , if not go to the left . you'll find the median in the leaf. running time is NlogN(for building) + QlogN^2(queries) . I think QlogN^2 can be improved to QlogN , this method is written here http://e-maxx.ru/algo/segment_tree in this part "Поиск наименьшего числа, больше либо равного заданного, в указанном отрезке. Ускорение с помощью техники "частичного каскадирования""
Thats my code http://pastebin.com/ATi5Uqjq