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\le a_i\le 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 $\ge 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 $\le med$. Is $f$ monotonic now?

Yes, because if the actual median is $actua{l}_{m}ed$, then all $f(i)$ where $i<actua{l}_{m}ed$ will be false and all $f(i)$ where $i\ge actua{l}_{m}ed$ 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 $\le mid$. Then, if the total number of elements in $[0,mid]$ is $\ge 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 $\ge 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 $\le 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]\mathrm{\%}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$?