G2. Big Wins! (hard version)

The problem asks us to find a subarray $a[l, r]$ such that $med(a[l, r]) - min(a[l, r])$ is maximized. Here, $med$ is the median (the element at position $\lceil (k+1)/2 \rceil$ after sorting, where $k$ is the length) and $min$ is the minimum element. The constraint $a_i \le n$ is crucial for the provided solution.

Let’s break down the solution step by step.

1. Rephrasing the Goal and High-Level Approach:

The goal is to maximize $MED - MN$, where $MED$ is the median and $MN$ is the minimum of a subarray. The solution proposes a two-pointer-like approach. It fixes a candidate minimum value, $MN$, and then tries to find the largest possible candidate median value, $MED$, such that there exists a subarray whose minimum is exactly $MN$ and whose median is at least $MED$.

2. Fixing the Minimum ($MN$) and Characterizing Subarrays:

For a fixed $MN$, any subarray $a[l, r]$ whose minimum is $MN$ must satisfy two conditions:

• It must contain at least one element $a_u = MN$.
• All elements $a_i$ within the subarray $a[l, r]$ must be greater than or equal to $MN$ (i.e., $a_i \ge MN$ for $l \le i \le r$).

To efficiently handle the second condition, the solution uses the concept of “maximal span where $a_u$ is the strict minimum”. For each index $u$, we find $l_u$ and $r_u$:

• $l_u$: The first index to the left of $u$ (or $0$ if none) such that $a_{l_u} < a_u$. This means all elements in $(l_u, u]$ are $\ge a_u$.
• $r_u$: The first index to the right of $u$ (or $n+1$ if none) such that $a_{r_u} < a_u$. This means all elements in $[u, r_u)$ are $\ge a_u$.

These $l_u$ and $r_u$ values can be computed for all $u$ in $O(n)$ time using a monotonic stack. Specifically, for a given $u$, $l_u$ is the index of the first element to its left that is less than $a_u$, and $r_u$ is the index of the first element to its right that is less than $a_u$. So, any subarray $a[l, r]$ where $a_u$ is the minimum and $a_u = MN$ must have $l_u < l \le u \le r < r_u$.

3. Defining the sign Array for Median Check:

For a given potential median value $M$, we define a sign array:

• sign_i = +1 if $a_i \ge M$
• sign_i = -1 if $a_i < M$

A crucial insight: a subarray $a[l, r]$ has a median $\ge M$ if and only if the sum of sign values over that subarray is positive. Let $k = r - l + 1$ be the length of the subarray. The median is $\ge M$ if at least $\lceil (k+1)/2 \rceil$ elements are $\ge M$. If $S$ is the sum of sign values in $a[l, r]$, let $N_+$ be the count of elements $\ge M$ and $N_-$ be the count of elements $< M$. Then $S = N_+ \cdot (+1) + N_- \cdot (-1) = N_+ - N_-$. Also, $N_+ + N_- = k$. So $N_- = k - N_+$. Substituting, $S = N_+ - (k - N_+) = 2 N_+ - k$. The condition $N_+ \ge \lceil (k+1)/2 \rceil$ is equivalent to $2 N_+ \ge 2 \lceil (k+1)/2 \rceil$. If $k$ is odd, $k = 2p+1$, then $\lceil (k+1)/2 \rceil = p+1$. So $2 N_+ \ge 2p+2 = k+1$. This means $2 N_+ - k \ge 1$, or $S \ge 1$. If $k$ is even, $k = 2p$, then $\lceil (k+1)/2 \rceil = p+1$. So $2 N_+ \ge 2p+2 = k+2$. This means $2 N_+ - k \ge 2$, or $S \ge 2$. However, the problem statement regarding “at least half the elements are high” simplifies this to “total sum of sign over that interval is positive”. This is a common trick used for median problems. If the sum is positive, it implies that $N_+ > N_-$, and since $N_+ + N_- = k$, this means $N_+ > k/2$, which is exactly what we need for the median to be $\ge M$.

Now, for a specific position $u$ to be the minimum $MN$ for a subarray $a[l, r]$: The subarray $a[l, r]$ must be within $(l_u, r_u)$ (i.e., $l_u < l \le u \le r < r_u$). The sum of signs for $a[l, r]$ must be positive. To maximize the sum of signs for a fixed $u$ (which is $a_u = MN$), we need to find the best $l$ and $r$. The sum of signs for $a[l, r]$ is $sign_u + \sum_{i=l}^{u-1} sign_i + \sum_{i=u+1}^{r} sign_i$. To maximize this, we need to pick $l$ such that $\sum_{i=l}^{u-1} sign_i$ is maximized (this is the maxSuffix sum ending at $u-1$ within the range $(l_u, u-1]$) and $r$ such that $\sum_{i=u+1}^{r} sign_i$ is maximized (this is the maxPrefix sum starting at $u+1$ within the range $[u+1, r_u)$). So, the condition for existence of such a subarray for a given $u$ is: maxSuffix(l_u, u-1) + sign_u + maxPrefix(u+1, r_u) >= 0 (or > 0 depending on strictness of median definition. The provided solution says >=0 for ‘positive’, let’s stick with that for now, assuming it handles edge cases correctly or simplifies. The common interpretation for median sum is usually > 0.) Here, maxSuffix(A, B) means the maximum suffix sum of the sign array in the range $[A, B]$, and maxPrefix(A, B) means the maximum prefix sum of the sign array in the range $[A, B]$. If $A > B$, these sums are $0$.

4. Using a Segment Tree:

To efficiently calculate maxSuffix, maxPrefix, and total sum over arbitrary ranges, a segment tree is used. Each node in the segment tree stores:

• totalSum: The sum of sign values in its range.
• bestPrefix: The maximum prefix sum in its range.
• bestSuffix: The maximum suffix sum in its range.
• ans: The maximum subarray sum (Kadane’s algorithm style) in its range. (Though the solution only mentions ans, bestPrefix, bestSuffix, totalSum, the ans here likely refers to the overall max sum of any subarray within that segment, which might be useful if we needed the general max sum, but for maxSuffix/maxPrefix specific to our problem, the other three are more relevant.)

When merging two children nodes (left child $L$, right child $R$):

• totalSum = L.totalSum + R.totalSum
• bestPrefix = max(L.bestPrefix, L.totalSum + R.bestPrefix)
• bestSuffix = max(R.bestSuffix, R.totalSum + L.bestSuffix) The maxSuffix(l_u, u-1) and maxPrefix(u+1, r_u) queries can be done on this segment tree in $O(\log n)$ time.

5. The Main Algorithm Loop:

The algorithm iterates MN from $1$ to $N$. Inside this loop, it tries to find the largest possible MED.

Initialization:

• Build the segment tree. Initially, assume MED = 1. Since all $a_i \ge 1$, all $a_i \ge MED$, so sign_i = +1 for all $i$. The segment tree is initialized with all sign_i = +1.
• current_MED = 1.
• max_diff = 0.

Outer Loop (iterating MN from 1 to $N$):

For each MN:

1. Consider MN as the minimum: Identify all indices $u$ where $a_u = MN$. For each such $u$, we need to check if we can satisfy the condition maxSuffix(l_u, u-1) + sign_u + maxPrefix(u+1, r_u) >= 0 with the current current_MED. Note that sign_u is always +1 if $a_u \ge current\_MED$, or -1 if $a_u < current\_MED$. Since we are fixing $a_u = MN$, this means $MN \ge current\_MED$ or $MN < current\_MED$.

2. Inner Loop (incrementing current_MED): This is the core greedy part. While the condition maxSuffix(l_u, u-1) + sign_u + maxPrefix(u+1, r_u) >= 0 is satisfied for all indices $u$ where $a_u \ge MN$ (and for which $a_u$ could potentially be the minimum in a subarray where the median is at least current_MED), we increment current_MED by 1. As current_MED increases, some values $a_i$ that were previously $\ge current\_MED$ might now become $< current\_MED$. For these positions, their sign_i changes from $+1$ to $-1$. This requires a point update in the segment tree. Specifically, for every position $i$ such that $a_i = current\_MED - 1$ (i.e., $a_i$ was just barely $\ge current\_MED - 1$ and is now $< current\_MED$), we update sign_i to $-1$. (More precisely, we increment current_MED. Then, all positions $i$ where $a_i = current\_MED - 1$ must be updated from $+1$ to $-1$ in the segment tree.)

3. When the condition fails: When the inequality maxSuffix(l_u, u-1) + sign_u + maxPrefix(u+1, r_u) >= 0 fails for any index $u$ with $a_u = MN$, it means we cannot find a subarray with minimum $MN$ and median $\ge current\_MED$. So, the largest possible median for this $MN$ was current_MED - 1.

4. Record maximum difference: Update max_diff = max(max_diff, (current_MED - 1) - MN).

5. Advance MN: Before moving to the next MN, we need to make sure that elements equal to the current MN cannot be part of a subarray with current_MED as the median, if their sign contributions are critical. The solution implicitly handles this by iterating MN upwards. As MN increases, the elements $a_i = MN$ are now “locked” as potential minimums. Their sign_u will be $-1$ if MN < current_MED and $+1$ if MN >= current_MED.

Refined Inner Loop / Updates:

The description of the inner loop is a bit subtle. Let’s clarify the current_MED and MN interactions.

The $l_u, r_u$ values are based on $a_u$ (the value at index $u$), not on $MN$. They are computed once. The sign array depends on current_MED.

A more precise flow for the $MN$ iteration:

For $MN = 1 \dots N$:

1. Before checking for MN: While current_MED <= N: Iterate through all indices i where a_i == current_MED - 1. For each such i, update sign_i in the segment tree from $+1$ to $-1$. (This step ensures that the sign array always reflects the current_MED.)

   Now, check if there exists any index u where $a_u = MN$ (the current minimum we are considering) such that for the current current_MED, the condition maxSuffix(l_u, u-1) + sign_u + maxPrefix(u+1, r_u) >= 0 is not met. The condition sign_u for the specific element $a_u=MN$ is:

   • If $MN \ge current\_MED$, then $sign_u = +1$.
   • If $MN < current\_MED$, then $sign_u = -1$. So, for each $u$ where $a_u = MN$, we need to evaluate: max_possible_sum_for_u = maxSuffix(l_u, u-1) + (MN >= current_MED ? 1 : -1) + maxPrefix(u+1, r_u)

   If max_possible_sum_for_u < 0 for any $u$ where $a_u=MN$, then we cannot achieve a median of current_MED with $MN$ as the minimum. In this case, we break the inner loop (cannot increase current_MED further for this MN). The best median for this $MN$ is current_MED - 1. Update max_diff = max(max_diff, (current_MED - 1) - MN). Otherwise (if for all $u$ with $a_u=MN$, max_possible_sum_for_u >= 0), then we can potentially achieve a median of current_MED. So, we increment current_MED and continue the inner while loop.

This logic seems more consistent with the “greedy raise med” part. The values that change from +1 to -1 are those that become less than the current med.

Data Structures and Complexity:

• Monotonic Stack: To compute $l_u$ and $r_u$ for all $u$: $O(N)$ time.
• Segment Tree:
  • Initialization: $O(N)$
  • Point updates: $O(\log N)$
  • Range queries (for maxSuffix, maxPrefix): $O(\log N)$
• Main Loop:
  • The outer loop iterates MN from $1$ to $N$.
  • The inner while current_MED loop means current_MED also increments from $1$ to $N$ overall across all MN iterations. Each time current_MED increments, we perform point updates for all elements $a_i = current\_MED - 1$. Since each $a_i$ value appears once, each index $i$ is updated at most once for its sign change from $+1$ to $-1$. This gives $O(N \log N)$ total for current_MED advancements.
  • For each MN, we iterate through all $u$ where $a_u = MN$. Let’s say there are $C_{MN}$ such indices. For each, we do two range queries ($O(\log N)$ each). The sum of $C_{MN}$ over all $MN$ is $N$. So, $O(N \log N)$ for all queries across all $MN$.

Therefore, the total time complexity is $O(N \log N)$. Memory complexity is $O(N)$ for the array, stack, and segment tree.

Why Correctness:

• Greedy MED: For each fixed MN, the inner loop correctly finds the maximal MED that can be achieved. If MED can be $X$, it can also be $X-1$. So we try to push it as high as possible.
• Iterating MN: By iterating MN from $1$ to $N$, we guarantee that every possible minimum value for a subarray is considered.
• Segment Tree for sign sum: The segment tree correctly maintains the necessary information (maxPrefix, maxSuffix) to check the median condition for any potential subarray within the computed $[l_u, r_u)$ bounds. The condition maxSuffix(l_u, u-1) + sign_u + maxPrefix(u+1, r_u) >= 0 finds the best possible sum of signs for any subarray centered at $u$ (where $u$ is the minimum $MN$) that extends as far left as $l_u$ and as far right as $r_u$. If this maximum possible sum is $\ge 0$, then such a subarray exists, satisfying the median property.

Example Walkthrough (Conceptual):

Let $a = [1, 4, 1, 5, 3, 3]$, $n=6$.

1. Precompute $l_u, r_u$: (Roughly, depends on strict inequality vs. equality. Let’s assume strict for $l_u, r_u$ values in the explanation) $l_u$: first index left of $u$ with $a[l_u] < a[u]$ $r_u$: first index right of $u$ with $a[r_u] < a[u]$

   For $a_1=1$: $l_1=0, r_1=7$ (no smaller elements) For $a_2=4$: $l_2=1$ (since $a_1=1<4$), $r_2=7$ (no $a_i<4$ to the right of $a_2$) … this is complicated, let’s just use the strict definition as given “first index to the left that has $value < a[u]+1$” and “first index to the right that has $value < a[u]-1$”. This seems unusual. The standard for range minimum queries is usually “first element smaller than $a_u$”. Let’s assume standard $L_u, R_u$ where $a_u$ is the minimum in $a[L_u \dots R_u]$.

   Let’s use the typical definitions: $L[i]$ is the first index $j < i$ such that $A[j] < A[i]$, and $R[i]$ is the first index $j > i$ such that $A[j] < A[i]$. If no such index exists, we can use 0 and $n+1$. For $a = [1,4,1,5,3,3]$: $L = [0, 1, 0, 3, 3, 3]$ (index 0 is a sentinel) $R = [7, 3, 7, 5, 7, 7]$ (index 7 is a sentinel)

   For $u=1, a_1=1: L_1=0, R_1=7$ For $u=2, a_2=4: L_2=1, R_2=3$ (since $a_3=1<4$) For $u=3, a_3=1: L_3=0, R_3=7$ For $u=4, a_4=5: L_4=3, R_4=5$ (since $a_5=3<5$) For $u=5, a_5=3: L_5=3, R_5=7$ For $u=6, a_6=3: L_6=5, R_6=7$

2. Initialize Segment Tree: current_MED = 1. All $a_i \ge 1$, so sign = [1,1,1,1,1,1].

3. Outer Loop: MN = 1 Indices $u$ where $a_u = 1$: $u=1, u=3$.

   Inner while loop (for current_MED):

   • current_MED = 1:

     • For $u=1, a_1=1$: $L_1=0, R_1=7$. $MN \ge current\_MED$ (1>=1), so $sign_1=+1$. maxSuffix(0,0) (empty) is 0. maxPrefix(2,6): sign array is $[1,1,1,1,1,1]$. Max prefix of $[1,1,1,1,1]$ is $5$. Sum for $u=1$: $0 + 1 + 5 = 6 \ge 0$. OK.
     • For $u=3, a_3=1$: $L_3=0, R_3=7$. $MN \ge current\_MED$ (1>=1), so $sign_3=+1$. maxSuffix(0,2): sign for $[1,4,1]$ is $[1,1,1]$. Max suffix of $[1,1]$ is 2. maxPrefix(4,6): sign for $[5,3,3]$ is $[1,1,1]$. Max prefix of $[1,1,1]$ is 3. Sum for $u=3$: $2 + 1 + 3 = 6 \ge 0$. OK. All OK for MN=1 and current_MED=1. Increment current_MED to 2.

   • current_MED = 2: Update sign for $a_i = 1$ (values equal to current_MED - 1). Indices $i=1,3$ now have $a_i < 2$, so update sign_1=-1, sign_3=-1. sign array is now [-1, 1, -1, 1, 1, 1].

     Check for $u=1, a_1=1$: $L_1=0, R_1=7$. $MN < current\_MED$ (1<2), so $sign_1=-1$. maxSuffix(0,0) is 0. maxPrefix(2,6) in [-1, 1, 1, 1, 1] is max prefix of $a[2 \dots 6]$ ($[4,1,5,3,3]$) or signs $s[2 \dots 6]$ (values $[1,-1,1,1,1]$). Max prefix of $[1,-1,1,1,1]$ is $1$ (for $a_2=4$). Sum for $u=1$: $0 + (-1) + 1 = 0 \ge 0$. OK. Check for $u=3, a_3=1$: $L_3=0, R_3=7$. $MN < current\_MED$ (1<2), so $sign_3=-1$. maxSuffix(0,2) in [-1,1,-1]: Max suffix of [-1,1] is $1$. maxPrefix(4,6) in [1,1,1]: Max prefix of [1,1,1] is $3$. Sum for $u=3$: $1 + (-1) + 3 = 3 \ge 0$. OK. All OK for MN=1 and current_MED=2. Increment current_MED to 3.

   • current_MED = 3: Update sign for $a_i = 2$ (none). sign array is still [-1, 1, -1, 1, 1, 1].

     Check for $u=1, a_1=1$: $L_1=0, R_1=7$. $MN < current\_MED$ (1<3), so $sign_1=-1$. maxSuffix(0,0) is 0. maxPrefix(2,6) in [1,-1,1,1,1] is 1. Sum for $u=1$: $0 + (-1) + 1 = 0 \ge 0$. OK. Check for $u=3, a_3=1$: $L_3=0, R_3=7$. $MN < current\_MED$ (1<3), so $sign_3=-1$. maxSuffix(0,2) in [-1,1,-1] is 1. maxPrefix(4,6) in [1,1,1] is 3. Sum for $u=3$: $1 + (-1) + 3 = 3 \ge 0$. OK. All OK for MN=1 and current_MED=3. Increment current_MED to 4.

   • current_MED = 4: Update sign for $a_i = 3$. Indices $i=5,6$ now have $a_i < 4$, so update sign_5=-1, sign_6=-1. sign array is now [-1, 1, -1, 1, -1, -1].

     Check for $u=1, a_1=1$: $L_1=0, R_1=7$. $MN < current\_MED$ (1<4), so $sign_1=-1$. maxSuffix(0,0) is 0. maxPrefix(2,6) in [1,-1,1,-1,-1]: Max prefix of [1,-1,1,-1,-1] is $1$. Sum for $u=1$: $0 + (-1) + 1 = 0 \ge 0$. OK. Check for $u=3, a_3=1$: $L_3=0, R_3=7$. $MN < current\_MED$ (1<4), so $sign_3=-1$. maxSuffix(0,2) in [-1,1,-1] is 1. maxPrefix(4,6) in [1,-1,-1]: Max prefix of [1,-1,-1] is $1$. Sum for $u=3$: $1 + (-1) + 1 = 1 \ge 0$. OK. All OK for MN=1 and current_MED=4. Increment current_MED to 5.

   • current_MED = 5: Update sign for $a_i = 4$. Index $i=2$ now has $a_2 < 5$, so update sign_2=-1. sign array is now [-1, -1, -1, 1, -1, -1].

     Check for $u=1, a_1=1$: $L_1=0, R_1=7$. $MN < current\_MED$ (1<5), so $sign_1=-1$. maxSuffix(0,0) is 0. maxPrefix(2,6) in [-1,-1,1,-1,-1]: Max prefix of [-1,-1,1,-1,-1] is $1$ (for $a_4=5$). Sum for $u=1$: $0 + (-1) + 1 = 0 \ge 0$. OK. Check for $u=3, a_3=1$: $L_3=0, R_3=7$. $MN < current\_MED$ (1<5), so $sign_3=-1$. maxSuffix(0,2) in [-1,-1,-1] is $-1$. maxPrefix(4,6) in [1,-1,-1] is $1$. Sum for $u=3$: $(-1) + (-1) + 1 = -1 < 0$. Fails! Condition fails for $u=3$. So, for MN=1, the max MED is current_MED - 1 = 4. max_diff = max(0, 4 - 1) = 3.

4. Outer Loop: MN = 2 (no elements are 2 in example)

5. Outer Loop: MN = 3 Indices $u$ where $a_u = 3$: $u=5, u=6$.

   The current_MED should continue from where it left off, which is $5$. sign array is [-1, -1, -1, 1, -1, -1].

   Check for $u=5, a_5=3$: $L_5=3, R_5=7$. $MN < current\_MED$ (3<5), so $sign_5=-1$. maxSuffix(3,4) in [1,-1] is 1. (From $a_4=5, a_5=3$. Signs: $s_4=1, s_5=-1$. Suffix of $s_3=1, s_4=-1$ for range $a_3 \dots a_4$ is $s_4=1$ if $a_4 \ge MED$, $s_4=-1$ if $a_4 < MED$. For $a_4=5$, $s_4=1$ at current $MED=5$. For $a_3=1$, $s_3=-1$. So [-1,1]. Max suffix sum is 1.) maxPrefix(6,6) in [-1] is -1. Sum for $u=5$: $1 + (-1) + (-1) = -1 < 0$. Fails! Condition fails for $u=5$. So for MN=3, max MED is current_MED - 1 = 4. max_diff = max(3, 4 - 3) = 3.

…and so on. The logic seems to hold. The example subarray $a[2,5]=[4,1,5,3]$ with $med=4, min=1$ gives $4-1=3$. Our algorithm found $MED=4$ for $MN=1$, giving difference $3$.

The solution is clever in how it uses the segment tree and sign array to check the median condition efficiently. The sweep of MN and the greedy increment of MED ensures all optimal solutions are considered.