UPD: O$(N \sqrt N)$ solution
Bucketing
Let's split the array into blocks of $\sqrt N$ size.
For each block let's keep all values in it in an array.
Let's also keep pairs $(Number, Count)$, counting the occurrences of each number, present in the block. We will also keep these pairs in an array, sorted by the $Number$. We also keep partial sums for this array, for each $Number$ indicating number of numbers less than this, in this block. (In the beginning this can be precalculated in $O(N log N)$ ).
Let's also keep a value $Mod$, that indicates that in reality all numbers in these block are not as they are saved, but actually bigger by $Mod$.
Last, for each block let's keep a pointer in the array of pairs, pointing to the first $Number$, such that $Number+Mod$ is more than or equal to the current value of the median.
Answering query
Let's count total number of values in all blocks less than the median - simply sum all partial sums for pointers.
Let's also count number of values equal to the median - by summing second components of pairs, at which our pointers point.
This takes $O(1)$ for each block and therefore $O(\sqrt N)$ for each query.
If we found out that total number of values less than or equal to the median is less than ${N \over 2} + 1$, we may need to shift some of the pointers forward, since the value of median then increases by 1.
In total each query we will at most need to shift $\sqrt N$ pointers by 1, making in total $O(N \sqrt N)$ shift forward.
Updating query $(A,B)$
For blocks fully covered by the interval we can simply increase the $Mod$ values. After that some of the pointers may need to be shifted backward by at most 1, to keep their invariant (pointing at first number more than or equal to the current median). Total number of shifts backwards won't exceed $O(N \sqrt N)$ for one query.
For two blocks half covered by the query let's update values in the array in the naive way:
First, increase each of them by $Mod$ and also increase each value in our sorted array of pairs by $Mod$. Clear $Mod$.
Then let's create a hash map of all values increased by 1 in the query.
Then let's loop through array of pairs and for each $Number$ we decrease it's $Count$ by an appropriate number in the hash map, and create an entry in the second array of pairs, indicating $(Number + 1, Count)$. Once we finish, we will have all numbers in our block presented by 2 array of pairs, both sorted by the first components. Then we can merge these to in the $O(\sqrt N)$.
Finally, recalculate partial sums for this new merged array and naively find the position of the pointer by looping through it.
Seems to be it, $O(\sqrt N)$ per query but I wouldn't want to code it;)
================================================================================
Here is an idea for $O(N \sqrt{N} log N)$ solution.
Observation: (Intuitive, Beautiful, Tested but Unproven):
By increasing the subarray by 1 we can only increase the median
- By 0 or 1, if array has odd length
- By 0 or 0.5 or 1, if array has even length
I tested this hypothesis extensively locally.
Let's assume $N \approx K$.
Bucketing
Then let's split our queries into $\sqrt N$ groups $\sqrt N$ each. At the beginning of each block we do the following:
- Calculate the median. Let it be $M$.
- Let's introduce $L=M-\sqrt N$, $R=M+\sqrt N$, $LC$ - number of elements less than $L$ in the array.
- For each value $X$ between $L$ and $R$ create a sorted list of all positions, in which value $X$ currently resides. We will keep each list as an implicit cartesian tree (data structure that allows cutting and merging subarray in $O(log Length)$. Example - STL Rope). This is the most computationally expensive step of the above and it takes $O(N log N)$ in the worst case, making overall complexity of these steps for all query groups $O(N \sqrt{N} log N)$.
Answering
When we will want to find the median, we will go through all values of $X$ between $L$ and $R$ and calculate sum $LC + CN(L) + CN(L+1) + CN(L+2)+ \cdots$ until it exceeds ${N \over 2} + 1$ for some value $L+t$ which will be new median. (Or average of two consecutive values). Here $CN(L)$ denotes number of items in the sorted list that corresponds to value $L$.
Updating
When we will want to update our structure after the next query ($A$, $B$), we will do the following:
- For each $X$ between $R$ and $L$ find subarray that contains all values between $A$ and $B$ (if we, for example, keep in the node of implicit cartesian tree minimum and maximum values in the corresponding subtree, we can find the appropriate indexes of subarray in $O(log N)$).
- Erase the corresponing subarray and insert a subarray, obtained the same way from the previous list.
- For list with numbers equal to $L$ we don't insert anything since we know that all values less than $L$ will stay less than $L$ in the scope of next $\sqrt N$ queries so we simply add them during summation as variable $LC$
- Splitting and merging implicit cartesian tree requires $O(log N)$ operations, we have $O(\sqrt N)$ cartesian trees, and our actions happen for each of $O(N)$ queries, leaving total complexity at $O(N \sqrt N log N)$.
Finally, we can save all queries in current block and then update our array, for example in $O(N + \sqrt N log \sqrt N)$ time by sorting queries and using scanline.
Afterthoughs:
I wonder if, since median can only increase by 1 or 0.5, we can solve this problem in $O(N log N)$ time somehow.
Also, same as in the answer above, it may be possible that $O(N \sqrt N log N)$ can be optimized to $O(N log^2 N)$, although it is not obvious to me, how.