Problem Author: | Anton Trygub |
Prepared by: | Andriy Stolitniy, Konstantin Denisov |
Analysis written by: | Konstantin Lutsenko |
10pt
Block 1
Ans = R - L + 1 - (L%2==0) - (R%2==0) + ((L==R)&&(L%2==0))
Block 2
You can iterate through all 2^n subsequences and check if they are good by calculating all prefix and suffix sums. You can calculate the answer for each of the \frac{n(n+1)}{2} possible queries by iterating through all its subsequences. The complexity is \mathcal{O}(2^n\cdot n).
Block 3
Let \sum [L, R] denote the sum over the subinterval . We say that \sum[L, R] \stackrel{def}{=} 0 when L > R (an empty interval).
Let \sum[1, n] = S.
The definition of a good array can be rewritten as \sum[1, a] \geqslant 0, \sum[a, n] \geqslant 0. But \sum[a, n] = \sum[1, n] - \sum[1, a-1]. Therefore, the definition of a good array can be expressed as
\sum[1, a] \in [0, S]
Thus, we can calculate dp[position][current sum][maximum prefix sum encountered], where the dynamic value is the maximum number of elements (or -INF if the state is unreachable). The complexity is \mathcal{O}(q n^3).
We also note that the optimal answer is obtained from the given interval by removing some number of minus ones. Our goal is to determine how many minus ones we need to remove.
Block *
Claim. An array is good if and only if all sums of its subintervals are not greater than the sum of the entire array.
Proof.
: By contradiction, assume all intervals have a sum less than , but the array is not good. Since the array is not good, there exists either a prefix or a suffix with a negative sum. Without loss of generality, let this be a prefix, meaning there exists such that \sum[1, R] < 0. But then \sum[R+1, n] = S - \sum[1, R] > S, which means the interval has a sum greater than the sum of the entire array.
: By contradiction, assume the array is good, but there exists \sum[L, R] > \sum[1, n]. Then \sum[1, n] - \sum[L, R] = \sum[1, L-1] + \sum[R+1, n] < 0, so at least one of the numbers \sum[1, L-1] or \sum[R+1, n] is negative, because their sum is negative. Thus, the array is not good.
Returning to the problem — we need to determine the minimum number of «-1» that need to be removed so that the sums over all subintervals do not exceed the sum over the entire array.
Let \sum[1, n] = S_0. Let be the subinterval with the maximum sum (if there are several, any of them). Let \sum[L, R] = M_0. We want to make S = M, but initially, we have M_0 \geqslant S_0.
With one removal of a minus one, increases by 1, and does not decrease. Thus, the difference M - S decreases by at most 1. Therefore, we need to remove at least M_0 - S_0 elements.
We will prove that removing M_0 - S_0 elements is always sufficient. Let \sum[1, L-1] = -P and \sum[R+1, n] = -Q. Notice that M_0 - S_0 = \sum[L, R] - \sum[1, n] = -(\sum[1, L-1] + \sum[R+1, n]) = P + Q. We also note that P, Q \leqslant 0 (i.e., \sum[1, L-1] \leqslant 0 and \sum[R+1, n] \leqslant 0), otherwise could be extended with an increase in sum.
Let \sum'[L, R] be the sum over the subinterval after our removal. We want to ensure that now all sums \sum'[1, a] and \sum'[a, n] are non-negative by removing P + Q minus ones.
To do this, we will remove some minus ones from the prefix [1, L-1], and some minus ones from the suffix [R+1, n]. Which ones exactly — we will determine later. Then \sum'[1, L-1] = \sum[1, L-1] + P = -P + P = 0, and similarly \sum'[R+1, n] = 0.
Notice that \sum[a+1, L-1] \leqslant 0, otherwise \sum[a+1, R] = \sum[L, R] + \sum[a+1, L-1] > \sum[L, R], and we designated as the interval with the largest sum.
Notice that \sum[L, a] \geqslant 0, otherwise \sum[a+1, R] = \sum[L, R] - \sum[L, a] > \sum[L, R], and we designated as the interval with the largest sum.
We will define what additional conditions are necessary for the resulting array to be good:
a < L:
This introduces the condition \sum'[1, a] \geqslant 0.
L \leqslant a \leqslant R:
\sum'[1, a] = \sum'[1, L] + \sum'[L, a] = 0 + \sum'[L, a] \geqslant 0,
which holds automatically.
a > R:
\sum'[1, a] = \sum'[1, L-1] + \sum'[L, R] + \sum'[R+1, a] =
= 0 + M_0 + \sum'[R+1, a] = M_0 + \sum'[R+1, n] - \sum'[a+1, n] =
= M_0 + 0 - \sum'[a+1, n],
which introduces the condition \sum'[a+1, n] \leqslant M_0.
Thus, it is necessary and sufficient that for all a < L, \sum[1, a] \in [0, M_0] holds, as well as a similar condition on the suffixes, i.e., \sum[a, n] \in [0, M_0] for all a > R. This, for example, can be achieved by greedily removing «-1»: we go through increasing from to L-1, and if the prefix sum becomes negative, we remove the current minus one. Then all prefix sums will become non-negative. Suppose that when removing a one at position , it turns out that \sum'[1, b] becomes greater than M_0 + 1 for some b < L. Notice that at this moment only the prefix sums to the right of have changed, meaning b \geqslant a. But \sum'[1, a] at this moment has become equal to . Therefore, \sum'[a+1, b] = \sum'[1, b] - \sum'[1, a] = M_0 + 1. However, we did not change anything on this segment, thus
\sum'[a+1, b] = \sum[a, b] = M_0 + 1 > M_0 = \sum[L, R].
But we chose M_0 as the maximum sum over the subinterval. Therefore, this cannot happen, which means all prefix sums lie within the required bounds. We do the same for the suffixes.
It is also worth noting that we indeed removed exactly minus ones, meaning that the sum over the entire prefix has become equal to zero. Indeed, if when removing a minus one from position , it turned out that \sum'[1, L-1] > 0, then \sum[a+1, L-1] = \sum'[a+1, L-1] = \sum'[1, L-1] - \sum'[1, a] = \sum'[1, L-1] - 0 > 0, and we proved that sums over segments of the form [a, L-1] are always non-negative.
Thus, we have reduced the problem to finding M_0, S_0 and outputting the value R - L + 1 - (M_0 - S_0).
Block 4
In the analysis of this and the following blocks, it is described how to find M = \max\limits_{l\leqslant L \leqslant R \leqslant r}\sum[L, R]. As shown above, this will solve the problem.
We will iterate through . We need to choose such that \sum[L, R] is maximum, i.e., \sum[1, L-1] is minimum. We can maintain this simultaneously with the iteration through .
Complexity:
Blocks 5-6
Let node[L, R] be a quadruple of values:
— the sum over this interval;
— the maximum prefix sum of this interval;
— the maximum suffix sum of this interval;
— the maximum sum of some subinterval of this interval.
Then we can calculate node[L, R] through node[L, a] and node[a+1, R] for some : let
(S_1, A_1, B_1, M_1) + (S_2, A_2, B_2, M_2) = (S, A, M, B),
then:
S = S_1 + S_2;
A = \max(A_1, S_1 + A_2);
B = \max(B_2, S_2 + B_1);
M = \max(M_1, M_2, B_1 + A_2).
If you really want to submit these blocks but not the next one, you can use sqrt-decomposition in \mathcal{O}(q\sqrt{n}). To do this, you should divide the array into blocks of length (where C \sim \sqrt{n}) and calculate node[kC, (k+1)C-1]. Then for each query to find the answer, you can perform of the described merges, and for update queries, you need to recalculate the sum for the modified block in .
Block 7
The merging described in the previous block can be calculated in a segment tree, where the vertices will store the numbers S, A, B, M for the corresponding intervals. The get query will also use this merge and return a quadruple of numbers, from which we will take and and output R - L + 1 - (M - S).