Problem link
I have read the editorial here, but I am confused about the section Combining Values in Method 2 (link).

The editorial states that w.A = max(max(u.A + v.S, u.S + v.A), u.L + v.R).
Then, the editorial says:

Claim 1: This is a lower bound on the answer.
We can say that the increasing condition must hold for the first i votes and the decreasing condition must hold for the rest of the votes in the range.

What increasing conditon?

Why does this mean that w.A = max(max(u.A + v.S, u.S + v.A), u.L + v.R) is a lower bound on the answer?

increasing condition = âCap is happy if at every point in time during the vote counting he is NOT losing to Tonyâ when going in increasing order of the fanâs indices

If you split the sequence into two parts, then the answer for the sequence is at least the number of modifications necessary to make the first part satisfy the increasing condition and the second part satisfy the decreasing condition

Claim 2: This lower bound can be attained.
Consider the greedy strategy mentioned in method 1. Then equality holds when we set i equal to one less than the position of the leftmost T removed when doing the right to left iteration.

I donât see how. Can someone justify the justification for Claim 2? (Illustrations might be a good idea if you wanna do that)

When moving from left to right, the greedy strategy only nullifies the j-th T in order to make the number of Cs in the prefix of length j equal to the number of Ts in the prefix of length j. Similar reasoning holds from right to left.

Finding w.A is a bit more tricky though. We will show that it is equal to w.A=maxâĄ(maxâĄ(u.A+v.S,u.S+v.A),u.L+v.R)
For a range of length L, this calculates \max_i\left(\max(\text{first }i\text{ prefix sums})+\max(\text{last }L-i\text{ suffix sums})\right)

The editorial says \max(\text{last }L-i\text{ suffix sums}) instead of \text{the }(L-i)^{\text{th}}\text{ suffix sum}. What am I missing here?

It turns out that \max(\text{last }L-i\text{ suffix sums}) = (L-i)-th suffix sum for the i in question.

(Also, if the code instead computed \max_i\left(\max(\text{first }i\text{ prefix sums})+(L-i\text{-th suffix sum})\right) it would end up with the same answer.)

does that also imply that \max_i(\max(\text{first }i\text{ prefix sums}) + \max(\text{last } L-i\text{ suffix sums}))=\max_i([i^{\text{th}}\text{ prefix sum}]+[(L-i)^{\text{th}}\text{suffix sum}])?

(Iâm assuming that the suffix array is indexed backwards. For example, the 1st suffix sum is the sum of 1 element, and the Lth suffix sum is the sum of all the L elements)

Let p be the position of the leftmost T removed when doing the right to left iteration (instead of using i).
I now understand that \max_{1\leq j <p}(\text{pre}[j])+\text{suf}[p]=\max_{1\leq j <p}(\text{pre}[j])+\max_{p\leq j\leq n}(\text{suf}[j])
where \text{pre}[i]=V_1+V_2+...+V_i and \text{suf}[i]=V_i+V_{i+1}+V_{i+2}+...+V_n.

But, I still cannot prove why \max_{1\leq j <p}(\text{pre}[j])+\max_{p\leq j\leq n}(\text{suf}[j])=\max_{1<i\leq n}(\max_{1\leq j<i}(\text{pre}[j])+\max_{i\leq j\leq n}(\text{suf}[j])).

The answer is at most the number of votes that the greedy strategy nullifies, right? And the number of votes that the greedy strategy nullifies is precisely the RHS of that inequality.