Primeramente, este parámetro (2L) resulta incómodo, por lo que definiremos L en su lugar.
Analicemos el problema en profundidad. Si h_i \le h_{i-1}, para satisfacer las condiciones del problema, debe cumplirse al menos una de las siguientes:
- L - h_i > h_{i-1}
- h_i > L - h_{i-1}
En esencia, esto significa que o bien L < h_i + h_{i-1} o bien L > h_i + h_{i-1}. Además, podemos observar que si para el índice i se selecciona una de estas opciones, entonces para i+1 (siempre que h_{i+1} \le h_i), únicamente puede cumplirse la otra opción.
Este comportamiento nos permite modelar el problema como una secuencia binaria. Surge entonces una pregunta natural: ¿podemos combinar las respuestas de dos intervalos knowing únicamente el estado binario de sus extremos? La respuesta es afirmativa.
Estructura con árbol de segmentos
Para cada nodo del árbol de segmentos, necesitamos mantener información sobre el intervalo correspondiente [l, r]. Específicamente, debemos conocer:
- Qué valor se selecciona en el extremo derecho: a_r o L - a_r
- Qué valor se selecciona en el extremo izquierdo: a_{l-1} o L - a_{l-1}
- El rango de valores válidos para L que satisface a'_r > a'_{l-1}
Matemáticamente, esto se representa mediante una estructura lres[0/1][0/1] y rres[0/1][0/1], donde el primer índice indica el estado del extremo izquierdo y el segundo el estado del extremo derecho.
Cálculo en nodos hoja
Para un nodo hoja que corresponde al índice x, simplemente examinamos manualmente cada uno de los cuatro estados binarios posibles para determinar el rango válido de L.
Operación de fusión entre hijos
La combinación de los resultados de los hijos izquierdo y derecho es más elegante de lo que parece. Primero, enumeramos los estados binarios i, j de los extremos izquierdo y derecho del nodo actual. Luego, considerando el estado del punto medio mid, observamos que el estado del hijo derecho debe ser consistente con el estado del hijo izquierdo en su límite. La transición se implementa mediante la siguiente función:
struct Nodo
{
Par<ll ll=""> res[2][2];
Nodo operator+(const Nodo& otro) const
{
Nodo resultado;
resultado.res[0][0] = union_(interseccion(res[0][0], otro.res[0][0]),
interseccion(res[0][1], otro.res[1][0]));
resultado.res[0][1] = union_(interseccion(res[0][0], otro.res[0][1]),
interseccion(res[0][1], otro.res[1][1]));
resultado.res[1][0] = union_(interseccion(res[1][0], otro.res[0][0]),
interseccion(res[1][1], otro.res[1][0]));
resultado.res[1][1] = union_(interseccion(res[1][0], otro.res[0][1]),
interseccion(res[1][1], otro.res[1][1]));
return resultado;
}
};
</ll>
La función union_ calcula la unión de intervalos, mientras que interseccion calcula la intersección. Esta estructura es precisamente la razón por la cual tomamos l-1 como referencia: nos permite mantener la consistencia entre nodos adyacentes.
Nota importante: La construcción del árbol debe realizarse desde build(2, n) para manejar correctamente los índices.
Consulta de validación
Una vez construido el árbol, podemos determinar si un intervalo arbitrario es válido consultando el nodo correspondiente. Si el rango resultante constituye un intervalo válido (es decir, el límite inferior no excede el límite superior), entonces existe un valor de L que satisface todas las condiciones.
Estrategia de búsqueda
Una primera aproximación consiste en enumerar el valor v y realizar una búsqueda binaria sobre u \in [1, i-1], verificando la validez en cada paso. La monotonicidad del problema garantzia la corrección de este enfoque, con una complejidad de \mathcal{O}(n \log^2 n). En implementaciones optimizadas para entornos de competição, questa aproximación puede alcanzar 80 puntos.
Optimización: búsqueda binaria en el árbol
Para mejorar el rendimiento, podemos integrar la búsqueda binaria directamente en la estructura del árbol de segmentos. El procedimiento es:
- Extraer los nodos del árbol que corresponden al intervalo [2, i]
- Combinar estos nodos en orden descendente según su extremo derecho
- Durante la combinación, si suddenly detectamos que el resultado deja de ser válido, realizamos una búsqueda binaria en el subárbol correspondiente para encontrar el punto exacto donde la validez se rompe
Esta optimización reduce la complejidad a \mathcal{O}(n \log n): extracción de intervalos en \mathcal{O}(n \log n) y búsqueda binaria en árbol donde cada paso solo requiere verificar si la fusión con el hijo derecho permanece válida.
Consideración crítica
La operación de fusión no es conmutativa. Es imprescindibile mantener el orden correcto: siempre debe fusionarse el hijo izqueirdo con el derecho en la secuencia establecida.
Conclusión técnica
Este problema ilustra una técnica avanzada: cuando necesitamos calcular el valor de un intervalo sujetos a ciertos estados binarios válidos, una aproximación con programación dinámica secuencial ofrece complejidad \mathcal{O}(r-l+1). Para optimizar aún más, aunque la matriz de exponenciación rápida no resulta apropiada en este caso, la fusión de intervalos mediante un árbol de segmentos discutiendo los casos de los extremos resulta extraordinariamente efectiva.
Implementación en C++
#include <bits>
using namespace std;
const int MAXN = 500005;
const long long INFINITO = 1e18;
int n;
long long altura[MAXN];
struct Intervalo
{
long long inferior, superior;
Intervalo(long long inf = 0, long long sup = INFINITO)
: inferior(inf), superior(sup) {}
};
Intervalo interseccionar(const Intervalo& a, const Intervalo& b)
{
return Intervalo(max(a.inferior, b.inferior), min(a.superior, b.superior));
}
Intervalo@unir(const Intervalo& a, const Intervalo& b)
{
return Intervalo(min(a.inferior, b.inferior), max(a.superior, b.superior));
}
struct Vertice
{
Intervalo estado[2][2];
Vertice operator+(const Vertice& otro) const
{
Vertice resultado;
resultado.estado[0][0] = @unir(
interseccionar(estado[0][0], otro.estado[0][0]),
interseccionar(estado[0][1], otro.estado[1][0])
);
resultado.estado[0][1] = @unir(
interseccionar(estado[0][0], otro.estado[0][1]),
interseccionar(estado[0][1], outro.estado[1][1])
);
resultado.estado[1][0] = @unir(
interseccionar(estado[1][0], otro.estado[0][0]),
interseccionar(estado[1][1], outro.estado[1][0])
);
resultado.estado[1][1] = @unir(
interseccionar(estado[1][0], outro.estado[0][1]),
interseccionar(estado[1][1], outro.estado[1][1])
);
return resultado;
}
};
Vertice segmento[MAXN << 2];
void construir(int posicion, int izquierda, int derecha)
{
if (izquierda == derecha)
{
long long suma = altura[izquierda] + altura[izquierda - 1];
// Casos: elección en índice izquierdo vs derecho
if (altura[izquierda] < altura[izquierda - 1])
{
segmento[posicion].estado[0][0] = Intervalo(INFINITO, 0);
segmento[posicion].estado[1][1] = Intervalo(0, INFINITO);
}
else if (altura[izquierda] == altura[izquierda - 1])
{
segmento[posicion].estado[0][0] = Intervalo(INFINITO, 0);
segmento[posicion].estado[1][1] = Intervalo(INFINITO, 0);
}
else
{
segmento[posicion].estado[0][0] = Intervalo(0, INFINITO);
segmento[posicion].estado[1][1] = Intervalo(INFINITO, 0);
}
segmento[posicion].estado[0][1] = Intervalo(suma, INFINITO);
segmento[posicion].estado[1][0] = Intervalo(0, suma);
return;
}
int medio = (izquierda + derecha) >> 1;
construir(posicion << 1, izquierda, medio);
construir(posicion << 1 | 1, medio + 1, derecha);
segmento[posicion] = segmento[posicion << 1] + segmento[posicion << 1 | 1];
}
vector<int> nodosSolicitados;
vector<pair int="">> rangosSolicitados;
void obtenerConsulta(int posicion, int izq, int der, int L, int R)
{
if (izq > R || der < L) return;
if (L <= izq && R >= der)
{
nodosSolicitados.push_back(posicion);
rangosSolicitados.emplace_back(L, R);
return;
}
int medio = (L + R) >> 1;
obtenerConsulta(posicion << 1, izq, der, L, medio);
obtenerConsulta(posicion << 1 | 1, izq, der, medio + 1, R);
}
bool esValido(const Vertice& v)
{
return v.estado[0][0].inferior >= v.estado[0][0].superior &&
v.estado[0][1].inferior >= v.estado[0][1].superior &&
v.estado[1][0].inferior >= v.estado[1][0].superior &&
v.estado[1][1].inferior >= v.estado[1][1].superior;
}
int buscarEnArbol(int posicion, int L, int R, const Vertice& actual, const Vertice& acumulador)
{
if (L == R) return L;
int medio = (L + R) >> 1;
Vertice fusion = segmento[posicion << 1 | 1] + acumulador;
if (esValido(fusion))
return buscarEnArbol(posicion << 1 | 1, medio + 1, R, actual, acumulador);
else
return buscarEnArbol(posicion << 1, L, medio, fusion, actual);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> altura[i];
construir(1, 2, n);
long long respuesta = 0;
for (int i = 2; i <= n; ++i)
{
nodosSolicitados.clear();
rangosSolicitados.clear();
obtenerConsulta(1, 2, i, 2, n);
Vertice actual;
actual.estado[0][0] = actual.estado[0][1] = Intervalo(0, INFINITO);
actual.estado[1][0] = actual.estado[1][1] = Intervalo(0, INFINITO);
int puntoRespuesta = 1;
for (int j = (int)nodosSolicitados.size() - 1; j >= 0; --j)
{
Vertice estadoPrevio = actual;
actual = segmento[nodosSolicitados[j]] + actual;
if (esValido(actual))
{
puntoRespuesta = buscarEnArbol(
nodosSolicitados[j],
rangosSolicitados[j].first,
rangosSolicitados[j].second,
estadoPrevio,
actual
);
break;
}
}
respuesta += i - puntoRespuesta;
}
cout << respuesta << '\n';
return 0;
}
</pair></int></bits>