Considerando un árbol de segmentos clásico para una sola dimensión, si se intenta aplicar iterativamente fila por fila, la eficiencia es inferior a lo deseable. A pesar de las optimizaciones teóricas, en casos prácticos esto frecuentemente resulta en exceder el límite de tiempo asignado. Además, estructuras menos convencionales como el árbol de segmentos bidimensional presentan una complejidad de implementación elevada y un uso intensivo de memoria.

Por lo tanto, para esta tarea específica, la solución óptima reside en adaptar una tabla sparse bidimensional, modificada específicamente para manejar geometrías triangulares.

Análisis de Entrada y Formato

A través del examen de datos de ejemplo, es evidente que el formato de entrada sigue una estructura piramidal o triangular en lugar de una matriz rectangular estándar. La entrada se lee de manera concéntrica:

   1  
  2 3 
 4 5 6
7 8 9 0

Esto implica que tanto los datos almacenados como las consultas subsiguientes operan sobre un triángulo isósceles rectángulo. Definimos el estado de nuestra tabla dinámica así:

$memo[i][j][k]$ representa el valor máximo dentro de una región triangular cuya base superior es el punto $(i, j)$ y cuyo tamaño de lado corresponde a $2^k$. Las dimensiones laterales de este triángulo abarcan desde $i$ hasta $i + 2^k - 1$ y desde $j$ hasta $j + 2^k - 1$ respectivamente.

Mientras que una tabla sparse bidimensional convencional descompone eficazmente cuadrados en cuatro regiones cuadradas más pequeñas (como se muestra visualmente abajo), la geometría triangular introduce dificultades adicionales al intentar dividir recursivamente:

En el caso de triángulos, tres triángulos hijos de tamaño $2^{k-1}$ no son suficientes para cubrir totalmente el triángulo padre de tamaño $2^k$, dejando huecos sin cubrir en la zona central:

Para resolver esto sin crear zonas sin cubrir, se debe ajustar la estrategia de agregación. Si colocamos un triángulo adicional en el centro de la base inferior del triángulo grande, utilizamos una coordenada intermedia derivada de la posición anterior. Específicamente, un triángulo auxiliar ubicado en el medio de la base corresponde a una subconsulta calculada previamente.

La estrategia definitiva implica posicionar hasta seis triángulos hijos más pequeños para asegurar una cobertura total del área requerida durante la precomputación y las consultas. Aunque la teoría sugiere que cualquier tamaño $n$ puede ser cubierto por tamaños menores, nuestro enfoque aprovecha que todos los rangos de consulta tendrán la misma altura máxima $h$. Esto permite fijar el exponente máximo $k$ y optimizar el espacio de almacenamiento.

Dado que la altura de consulta es constante, el valor de $k$ también lo será. Se pueden reducir las dimensiones de la tercera escala de la tabla a un tamaño cíclico de 2 (array rodante), manteniendo solo los estados par y impar del nivel actual y previo, lo que minimiza la ocupación de memoria.

Algoritmo de Precomputación

Primero, leemos las dimensiones y procesamos el nivel base ($k=0$). Luego, iteramos sobre los niveles exponenciales. Usamos índices temporales para acceder a la capa actual y la anterior, evitando bucles innecesarios fuera del rango válido permitido por la altura de consulta.

int n, h;
cin >> n >> h;

// Inicialización del nivel 0
for (int r = 1; r <= n; ++r) {
    for (int c = 1; c <= r; ++c) {
        memo[r][c][0] = leer_dato(r, c);
    }
}

// Determinar el logaritmo máximo necesario basado en la altura de consulta
int max_log = 0;
while ((1 << (max_log + 1)) <= h) {
    max_log++;
}

// Recorrido sobre niveles de potencia
for (int d = 1; d <= max_log; ++d) {
    int current = d & 1;      // Nivel par/impar actual
    int prev = current ^ 1;   // Nivel anterior
    
    // Rango válido para evitar límites inferiores
    for (int r = 1; r <= n - (1 << d) + 1; ++r) {
        for (int c = 1; c <= r; ++c) {
            // Toma el máximo de los componentes básicos triangulares
            memo[r][c][current] = max(
                memo[r][c][prev], 
                max(memo[r + (1 << (d - 1))][c][prev], 
                    memo[r + (1 << (d - 1))][c + (1 << (d - 1))][prev])
            );
            
            // Añadir los componentes auxiliares necesarios para cubrir huecos geométricos
            if (d >= 2) {
                memo[r][c][current] = max(memo[r][c][current],
                    max(memo[r + (1 << (d - 1))][c + (1 << (d - 2))][prev],
                    max(memo[r + (1 << (d - 2))][c][prev], 
                         memo[r + (1 << (d - 2))][c + (1 << (d - 2))][prev])));
            }
        }
    }
}

Lógica de Consulta

Al realizar una consulta para un rango triangular definido por el vértice superior $(x, y)$ y la altura $h$, no podemos asumir que $h$ es exactamente una potancia de 2. Por ello, calculamos el nivel base más cercano inferior y ajustamos los desplazamientos para incluir las regioens triangulares suplementarias necesarias.

Si la distancia vertical restante entre la altura consultada $h$ y la potencia de 2 mayor $2^k$ es $rem$, necesitamos desplazar los índices centrales en $rem / 2$ unidades hacia adentro de los lados rectos para cubrir el centro exacto de la base solicitada.

El código de consulta siguiente refleja esta lógica matemática:

int query_tri(int x, int y, int h) {
    int k = max_log;
    
    // Calcular bordes extremos del triángulo base más grande
    int bot_row = x + h - 1; 
    int bot_col = y + h - 1;
    
    int idx = k & 1;
    int ans = max(memo[x][y][idx],
                  max(memo[bot_row - (1 << k) + 1][y][idx],
                      memo[bot_row - (1 << k) + 1][bot_col - (1 << k) + 1][idx]));

    // Si la potencia base es pequeña, ya hay cobertura suficiente
    if (k <= 1) return ans;

    // Calcula el desplazamiento requerido para los triángulos centrais
    int offset = (h - (1 << k)) >> 1;

    // Incorpora las zonas triangulares intermedias
    ans = max(ans, max(
                memo[bot_row - (1 << k) + 1][y + offset][idx],
                max(memo[x + offset][y][idx],
                    memo[x + offset][y + offset][idx])));
    
    return ans;
}

Este enfoque garantiza que todas las regiones triangulares sean evaluadas eficientemente dentro de los límites de tiempo y memoria permitidos por la restricción de consultar siempre sobre la misma altura máxima.