Method 1 (Offline)

Consider the greedy strategy: iterate from left to right and change Ts to satisfy the increasing condition, then do the same from right to left.

We can solve this problem offline by simulating this process.

https://oj.uz/submission/61836

Method 2 (Online)

A simpler case

Consider the case where we only care about counting votes from left to right.

Let a C vote count as $-1$ and a T vote count as $+1$ in an array $V$.

The answer to a query on the range $[l, r]$ is simply the maximum prefix sum in that range. (i.e. The largest $V_l + V_{l + 1} + \dots + V_k$)

If we count votes from right to left though, the answer is the maximum suffix sum instead.

We can use a segment tree to answer both of these types of queries efficiently.

Combining values

It would be really convenient if we could just calculate the maximum prefix and suffix sums and add them. However, we would count some nullified votes twice if we do this.

In each node of the segment tree that stores information about the range $[l, r]$ we store the following information:

• The maximum prefix sum in the range $[l, r]$. (Let this be $L$)
• The maximum suffix sum in the range $[l, r]$. (Let this be $R$)
• The total sum of the range. (Let this be $S$)
• The answer to a query on the range $[l, r]$. (Let this be $A$)

When we combine two nodes $u$ (left child) and $v$ (right child) to make node $w$,

• $w.L = \max(u.L, u.S + v.L)$
• $w.R = \max(u.R + v.S, v.R)$
• $w.S = u.S + v.S$

Finding $w.A$ is a bit more tricky though. We will show that it is equal to

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)$

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.

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.

Therefore, this is a lower bound and it can be attained.

The final complexity of this algorithm is $\mathcal{O}((N + Q) \log N)$.

Implementation

Copy
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Node {
	int l_max, r_max, tot, ans;

	Node operator+(Node b) {
		Node ret;