Actualizaciones de Intervalos y Arreglos de Diferencias

En problemas donde se requiere modificar intervalos de valores y consultar puntos específicos, el uso de arreglos de diferencias es una técnica fundamental. Supongamos un terreno representado por puntos con alturas específicas. La temperatura en cada punto depende de la diferencia de altura con el punto anterior: descender aumenta la temperatura en $T$ grados por unidad, mientras que ascender la disminuye en $S$ grados.

Al aplicar modificaciones por intervalos a las alturas, recalcular la temperatura desde cero sería ineficiente. En su lugar, mantenemos un arreglo de diferencias de alturas. Además, registramos el total de unidades ascendidas y descendidas. Cuando un intervalo $[L, R]$ se modifica en $X$, solo cambian las diferencias en los límites $L$ y $R+1$. Actualizamos los totales de ascenso y descenso en tiempo $O(1)$, permitiendo calcular la temperatura final en el punto $N$ mediante la fórmula $D \times T - U \times S$.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n, q, temp_drop, temp_rise;
    if (!(cin >> n >> q >> temp_drop >> temp_rise)) return 0;

    vector<ll> heights(n + 2, 0);
    vector<ll> diff(n + 2, 0);
    ll total_up = 0, total_down = 0;

    for (int i = 1; i <= n; ++i) {
        cin >> heights[i];
        diff[i] = heights[i] - heights[i - 1];
        if (diff[i] > 0) total_up += diff[i];
        else total_down -= diff[i];
    }

    while (q--) {
        ll l, r, x;
        cin >> l >> r >> x;

        ll old_diff_l = diff[l];
        ll new_diff_l = old_diff_l + x;
        if (old_diff_l > 0) total_up -= old_diff_l;
        else total_down += old_diff_l;
        if (new_diff_l > 0) total_up += new_diff_l;
        else total_down -= new_diff_l;
        diff[l] = new_diff_l;

        if (r + 1 <= n) {
            ll old_diff_r = diff[r + 1];
            ll new_diff_r = old_diff_r - x;
            if (old_diff_r > 0) total_up -= old_diff_r;
            else total_down += old_diff_r;
            if (new_diff_r > 0) total_up += new_diff_r;
            else total_down -= new_diff_r;
            diff[r + 1] = new_diff_r;
        }

        cout << total_down * temp_rise - total_up * temp_drop << "\n";
    }
    return 0;
}

Maximización de Estaciones mediante Estrategia Voraz

En escenarios de transporte donde se debe optimizar el número de paradas dentro de un límite de tiempo, un enfoque de programación dinámica puede ser tentador pero innecesariamente complejo. Una estrategia voraz (greedy) resulta óptima.

Considere una línea con estaciones rápidas predefinidas. Se permite añadir un número limitado de estaciones semirápidas. El objetivo es maximizar las estaciones alcanzables dado un tiempo total de viaje. Entre cada par de estaciones rápidas consecutivas, calculamos cuántas estaciones adicionales podemos alcanzar si usamos el tiempo restante.

Almacenamos estas ganancias potenciales en un arreglo, lo ordenamos de mayor a menor, y seleccionamos las mejores $K$ opciones, donde $K$ es el número de estaciones semirápidas permitidas. La respuesta final es la suma de las estaciones rápidas alcanzables más las ganancias de las estaciones semirápidas seleccionadas.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n, m, k, slow_dist, fast_dist, slow_time, total_time;
    if (!(cin >> n >> m >> k >> slow_dist >> fast_dist >> slow_time >> total_time)) return 0;

    vector<ll> fast_stations(m + 1);
    ll base_reachable = 0;

    for (int i = 1; i <= m; ++i) {
        cin >> fast_stations[i];
        if ((fast_stations[i] - 1) * fast_dist <= total_time) {
            base_reachable++;
        }
    }

    ll extra_allowed = k - m;
    vector<ll> extra_gains;

    for (int i = 1; i < m; ++i) {
        ll left_station = fast_stations[i];
        ll right_station = fast_stations[i + 1];
        ll remaining_time = total_time - (left_station - 1) * fast_dist;

        if (remaining_time < 0) continue;

        ll current_pos = left_station;
        ll local_gains = 0;

        while (current_pos < right_station && remaining_time > 0) {
            ll max_steps = remaining_time / slow_time;
            ll next_pos = min(right_station, current_pos + max_steps + 1);

            if (current_pos != left_station) {
                extra_gains.push_back(next_pos - current_pos);
            } else {
                local_gains += next_pos - current_pos - 1;
            }

            remaining_time -= (max_steps + 1) * slow_time;
            current_pos = next_pos;
        }
        if (local_gains > 0) extra_gains.push_back(local_gains);
    }

    sort(extra_gains.rbegin(), extra_gains.rend());

    ll total_extra = 0;
    for (int i = 0; i < min((ll)extra_gains.size(), extra_allowed); ++i) {
        total_extra += extra_gains[i];
    }

    cout << base_reachable + total_extra - 1 << "\n";
    return 0;
}

Sustitución de Rutas en Grafos con Dijkstra

Para problemas de rutas más cortas que involucran la sustitución de un segmento del camino por una ruta alternativa específica, ejecutar el algoritmo de Dijkstra desde múltiples nodos clave es la técnica estándar.

Dado un grafo no dirigido con pesos, un nodo de inicio $S$, un nodo de destino $T$, y un par de nodos $U$ y $V$ que definen un "pase" o ruta alternativa, debemos encontrar la ruta más corta de $S$ a $T$ que pueda utilizar el tramo entre $U$ y $V$.

La solución implica calcular las distancias más cortas desde $S$, $T$, $U$ y $V$ hacia todos los demás nodos utilizando Dijkstra. Luego, iteramos sobre los nodos ordenados por su distancia a $T$. Para cada nodo en la ruta óptima de $S$ a $T$, evaluamos si desviar a través de $U$ o $V$ reduce el costo total, actualizando dinámicamente las distancias mínimas alternativas.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
using ll = long long;
const ll INF = 1e18;

struct Edge {
    int to;
    ll weight;
};

struct Node {
    int id;
    ll dist;
    bool operator>(const Node& other) const {
        return dist > other.dist;
    }
};

int n, m, S, T, U, V;
vector<vector<Edge>> graph;
vector<ll> dist_S, dist_T, dist_U, dist_V;

void dijkstra(int start, vector<ll>& dist) {
    dist.assign(n + 1, INF);
    dist[start] = 0;
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push({start, 0});

    while (!pq.empty()) {
        auto [u, d] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;

        for (const auto& edge : graph[u]) {
            int v = edge.to;
            ll w = edge.weight;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({v, dist[v]});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n >> m >> S >> T >> U >> V)) return 0;

    graph.resize(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

    dist_S.resize(n + 1);
    dist_T.resize(n + 1);
    dist_U.resize(n + 1);
    dist_V.resize(n + 1);

    dijkstra(S, dist_S);
    dijkstra(T, dist_T);
    dijkstra(U, dist_U);
    dijkstra(V, dist_V);

    vector<pair<ll, int>> sorted_nodes(n);
    for (int i = 1; i <= n; ++i) {
        sorted_nodes[i - 1] = {dist_T[i], i};
    }
    sort(sorted_nodes.begin(), sorted_nodes.end());

    vector<ll> min_alt_U(n + 1, INF);
    vector<ll> min_alt_V(n + 1, INF);

    for (int i = 1; i <= n; ++i) {
        min_alt_U[i] = dist_U[i];
        min_alt_V[i] = dist_V[i];
    }

    ll ans = INF;

    for (const auto& [d, u] : sorted_nodes) {
        ans = min(ans, min(min_alt_U[u] + dist_V[u], min_alt_V[u] + dist_U[u]));

        for (const auto& edge : graph[u]) {
            int v = edge.to;
            ll w = edge.weight;
            if (dist_T[u] + w + dist_S[v] == dist_S[T]) {
                min_alt_U[v] = min(min_alt_U[v], min_alt_U[u]);
                min_alt_V[v] = min(min_alt_V[v], min_alt_V[u]);
            }
        }
    }

    cout << ans << "\n";
    return 0;
}