Submedians (Hard Version)

For one subarray, medians are not necessarily a single value. Sort its values as

$b_1 \le b_2 \le \dots \le b_m.$

An integer $v$ is a median iff at least $\lceil m/2 \rceil$ elements are $\le v$ and at least $\lceil m/2 \rceil$ elements are $\ge v$. So the median values are exactly

$[b_{(m+1)/2},\ b_{(m+2)/2}],$

with integer division in the indices. For even length, this can include values not present in the array. That little detail is where a lot of wrong solutions go to die.

Finding The Extremes

First find the largest submedian.

For a fixed value $v$, define

$big_i = \begin{cases} 1 & a_i \ge v \\ -1 & a_i < v. \end{cases}$

A subarray has some median at least $v$ iff at least half of its elements are $\ge v$, which is exactly

$\sum big_i \ge 0$

over that subarray.

So checking whether there exists a subarray of length at least $k$ with median at least $v$ becomes the classic prefix-sum check: for every right endpoint $r$, keep the minimum prefix sum among positions at most $r-k$. If

$pref[r] - \min pref[0..r-k] \ge 0,$

then such a subarray exists.

This predicate is monotonic in $v$, so binary search gives the maximum submedian $R$ and a witness subarray for it.

The minimum submedian $L$ is symmetric. Define

$small_i = \begin{cases} 1 & a_i \le v \\ -1 & a_i > v. \end{cases}$

Now binary search the smallest $v$ for which some length-at-least-$k$ subarray has nonnegative transformed sum. That gives $L$ and its witness.

The witnesses are valid for the exact extreme values: for the maximum, the found subarray has some median $\ge R$. If $R$ itself were not a median of it, then there would be a submedian greater than $R$, contradiction. Same logic works for the minimum.

Why The Answer Is One Whole Range

Take two subarrays where one is obtained from the other by adding or deleting one endpoint. Their median intervals always intersect.

Why? If you insert one element into a sorted multiset:

• odd length becomes even: the old median becomes one of the two middle values or lies between them;
• even length becomes odd: the new middle value lies inside the old middle interval.

Deleting is just the reverse operation. So adjacent subarrays share at least one median.

Now take the witness for $L$, say $[l_1,r_1]$, and the witness for $R$, say $[l_2,r_2]$. We build a path of valid subarrays:

1. start at $[l_1,r_1]$;
2. move the right endpoint to $n$;
3. move the left endpoint to $l_2$;
4. move the right endpoint down to $r_2$.

Every subarray on this path has length at least $k$. Consecutive subarrays have intersecting median intervals, so the union of all median intervals along the path is connected. It contains $L$ at the start and $R$ at the end, therefore it contains every integer from $L$ to $R$.

Since $L$ and $R$ are the global minimum and maximum submedians, there is nothing outside this range. So the full answer is exactly every value in $[L,R]$.

Maintaining The Current Median Interval

As we walk along the path, endpoints move one step at a time. We maintain frequencies of values in the current subarray using a Fenwick tree.

For current length $m$, the median interval is

$[kth((m+1)/2),\ kth((m+2)/2)].$

The Fenwick tree supports updates and order-statistic queries in $O(\log n)$.

When a current subarray contributes median interval $[x,y]$, we need to assign this subarray as a witness for every still-unanswered value in that interval. Doing that naively can be quadratic. So use a DSU-next structure:

• find(v) returns the smallest unanswered value at least $v$;
• after assigning value $v$, erase it by linking it to find(v+1).

Each value is erased once, so all interval-filling work is almost linear.

Correctness Proof

First, the binary search for $R$ is correct because the transformed sum condition with $big_i$ is equivalent to the existence of a subarray whose median interval reaches at least $v$. The predicate is monotone, so binary search finds the largest possible such $v$, which is exactly the largest submedian. The same argument with $small_i$ finds the smallest submedian $L$.

Second, every subarray contributes a contiguous interval of medians, namely its two middle order statistics. Also, two subarrays differing by one endpoint have intersecting median intervals. Therefore, along any endpoint-by-endpoint path of valid subarrays, the union of median intervals is contiguous.

The constructed path starts at a subarray containing $L$ as a median and ends at a subarray containing $R$ as a median. Hence the union of median intervals processed by the algorithm contains all values from $L$ to $R$.

Every value assigned by the algorithm is assigned from the actual median interval of the stored witness subarray, so every output triple is valid. The DSU-next structure only skips values that already have a valid witness, so every value is output at most once.

Thus the algorithm outputs exactly all submedians, each with a valid witness.

Complexity

Each binary search check is $O(n)$, and there are $O(\log n)$ checks. The endpoint walk has $O(n)$ moves, each doing Fenwick work in $O(\log n)$. DSU assignment is amortized near-linear.

Total complexity per test case:

$O(n \log n).$

Memory usage is $O(n)$.