Hints: Sakurako's Test

There is a very standard trick of converting Median based problems to Sum based problems. I learnt it from a recent Codeforces Problem : Med-imize

Notice that $1 \leq a_i \leq n$. So, let’s draw a number line from $0$ to $n$ where $line[num]$ represents the frequency of $num$.

From this number line, how do you locate the median?

Let’s define $half = (n + 2)/2$.

The median would be the first position where the prefix sum of this number line is $\geq half$.

Now, I’ll show you an alternate way to compute the median.

If you define $f(med)$ to be true if the median of the array is $med$. Is $f$ monotonic?

That’s a trick question. $f$ is not monotonic. Only 1 value of $f$ would be true and all other values would be false.

So, let’s modify it a bit. Define $f(med)$ to be true if the median of the array is $\leq med$. Is $f$ monotonic now?

Yes, because if the actual median is $actual_med$, then all $f(i)$ where $i < actual_med$ will be false and all $f(i)$ where $i \geq actual_med$ will be true.

Hence, we can binary search on this $f$ to locate the median of an array. Suppose we want to check if median is $\leq mid$. Then, if the total number of elements in $[0, mid]$ is $ \geq half$, then $f(mid)$ is true.

So, even though you could traverse from left to right and compute the median at the first point where the prefix sum becomes $\geq half$, I’ve just showed you a binary search technique to locate this median. But why? Because this technique will be useful for us when there are modifications to array elements. Notice that the monotonicity of $f$ does not change even after modifications.

So now, suppose you are given an $x$ and you want to figure out if the final median can be $\leq mid$. How do you do it?

$f(mid)$ will be true only if we can stuff atleast $half$ elements to the left of $mid$. Why don’t we be a bit lenient and stuff eveything to the left of $mid$ if it is possible (there’s no harm in having a large number of elements there). And even after this leniency, if the count remains less than half, we know that it median has to be $> mid$.

Recall Euclid’s divison lemma

$a[i] = q \cdot x + rem$

Therefore, the leftmost position that we could stuff $a[i]$ into is $rem$, so let’s do it.

For each $a[i]$, increase frequency of $a[i]\%x$. Then, if the prefix sum till $mid$ is less than half, the $f(med)$ is false, else it is true.

Notice that $x$ can be only in the range $[1, n]$. So let’s precompute the answer for all $x$. How do you avoid recomputation of the prefix sum?

Think about cyclicity of modulo and sum of Harmonic Series.

Notice that on the number lines, the modulo would look like

$$0, 1, 2, x, 0, 1, 2, x$$

If $med < x$, then it means that you can only take a prefix of elements of size $med$ starting from every $0$. So, let’s brute force all positions of such $0$ (under modulo $x$), and take the subarray sum of size $med$ starting from that element.

What is the total number of occurrences of such 0s across all $x$ from $1$ to $n$?