Election

Método 1 (offline)

Consideremos la estrategia voraz: iterar de izquierda a derecha y cambiar Ts para satisfacer la condición creciente, y luego hacer lo mismo de derecha a izquierda.

Podemos resolver este problema offline simulando este proceso.

https://oj.uz/submission/61836 

Método 2 (online)

Un caso más simple

Consideremos el caso en el que solo nos importa contar votos de izquierda a derecha.

Hagamos que un voto C cuente como $-1$ y un voto T como $+1$ en un arreglo $V$.

La respuesta a una consulta sobre el rango $[l, r]$ es simplemente la suma de prefijos máxima en ese rango. (es decir, el mayor $V_l + V_{l + 1} + \dots + V_k$)

Si en cambio contamos votos de derecha a izquierda, la respuesta es la suma de sufijos máxima.

Podemos usar un árbol de segmentos para responder ambos tipos de consultas de forma eficiente.

Combinar valores

Sería muy conveniente si pudiéramos simplemente calcular las sumas de prefijos y sufijos máximas y sumarlas. Sin embargo, contaríamos algunos votos anulados dos veces si hacemos esto.

En cada nodo del árbol de segmentos que guarda información sobre el rango $[l, r]$ guardamos la siguiente información:

• La suma de prefijos máxima en el rango $[l, r]$. (Sea $L$ este valor)
• La suma de sufijos máxima en el rango $[l, r]$. (Sea $R$ este valor)
• La suma total del rango. (Sea $S$ este valor)
• La respuesta a una consulta sobre el rango $[l, r]$. (Sea $A$ este valor)

Cuando combinamos dos nodos $u$ (hijo izquierdo) y $v$ (hijo derecho) para formar el nodo $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$

Hallar $w.A$ es un poco más complicado. Mostraremos que es igual a

Para un rango de longitud $L$, esto calcula

Afirmación 1: Esto es una cota inferior de la respuesta.

Podemos decir que la condición creciente debe valer para los primeros $i$ votos y la condición decreciente debe valer para el resto de los votos del rango.

Afirmación 2: Esta cota inferior se puede alcanzar.

Consideremos la estrategia voraz mencionada en el método 1. Entonces la igualdad vale cuando tomamos $i$ igual a una posición menos que la del T más a la izquierda eliminado al hacer la iteración de derecha a izquierda.

Por lo tanto, esto es una cota inferior y se puede alcanzar.

La complejidad final de este algoritmo es $\mathcal{O}((N + Q) \log N)$.

Implementación

#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;
		ret.l_max = max(l_max, b.l_max + tot);
		ret.r_max = max(r_max + b.tot, b.r_max);
		ret.tot = tot + b.tot;
		ret.ans = max(max(ans + b.tot, b.ans + tot), l_max + b.r_max);
		return ret;
	}
};
 
Node segtree[2000001];
char s[500001];
int n;
 
void build(int node = 1, int l = 1, int r = n) {
	if (l == r) {
		if (s[l] == 'T') segtree[node] = {1, 1, 1, 1};
		else segtree[node] = {0, 0, -1, 0};
	} else {
		int mid = (l + r) / 2;
		build(node * 2, l, mid);
		build(node * 2 + 1, mid + 1, r);
		segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
	}
}
 
Node query(int a, int b, int node = 1, int l = 1, int r = n) {
	if (l > b || r < a) return {0, 0, 0, 0};
	if (l >= a && r <= b) return segtree[node];
	int mid = (l + r) / 2;
	return query(a, b, node * 2, l, mid) + query(a, b, node * 2 + 1, mid + 1, r);
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	FOR(i, 1, n + 1) cin >> s[i];
	build();
	int q;
	cin >> q;
	while (q--) {
		int a, b;
		cin >> a >> b;
		cout << query(a, b).ans << '\n';
	}
	return 0;
}