Problema

Se proporcionan \(n\) intervalos. Se puede seleccionar arbitrariamente cualquier subconjunto de estos intervalos (incluyendo el conjunto vacío). Luego, se deben realizar las siguientes operaciones:

• Para los intervalos seleccionados, se realiza una operación de adición global, es decir, si se selecciona \([l_i, r_i]\, entonces todos los elementos \(a_j\) donde \(j \in [l_i, r_i]\\) se incrementan en 1. Para los intervalos no seleccionados, no se realiza ninguna operación.
• Después de completar todas las operaciones, se debe maximizar el valor de \(max_a - min_a\).

Solución Greedy

Para este problema, existen dos enfoques principales. Primero, discutiremos el enfoque greedy.

Al analizar las propiedades del problema, podemos determinar que fijando primero las posiciones del valor máximo y mínimo del array, la operación de adición de intervalos resultará en tres casos:

• El intervalo no contiene la posición del valor máximo: se descarta.
• El intervalo contiene la posición del valor máximo pero no la del valor mínimo: se incluye.
• El intervalo contiene tanto la posición del valor máximo como la del valor mínimo: puede incluirse o no.

Esto significa que solo necesitamos seleccionar intervalos que contengan únicamente la posición del valor máximo. Dada esta propiedad, si establecemos el valor mínimo \(x\) en el centro del array, los intervalos que contienen esta posición central no pueden ser seleccionados. Por lo tanto, los intervalos deben estar completamente a la izquierda o derecha del valor mínimo.

Supongamos que el valor máximo final está en el lado izquierdo, lo que significa que todos los intervalos a la derecha del valor mínimo deben descartarse. En este caso, si desplazamos \(x\) hacia la derecha, el resultado aumentará o permanecerá igual. El mismo razonamiento aplica si el valor máximo está en el lado derecho.

En cualquier caso, colocar \(x\) en el centro es claramente menos óptimo que colocarlo en los extremos. Por lo tanto, solo necesitamos fijar los extremos como posiciones del valor mínimo y simular ambos casos para determinar cuál produce el resultado mayor.

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;

void resolver() {
    int n, m; cin >> n >> m;

    vector<int> puntos;
    vector<pair<int, int>> intervalos(n + 1);
    for(int i = 1; i <= n; i++){
        int l, r; cin >> l >> r;
        puntos.push_back(l), puntos.push_back(r);
        intervalos[i] = {l, r};
    }
    
    sort(puntos.begin(), puntos.end());
    puntos.erase(unique(puntos.begin(), puntos.end()), puntos.end());

    map<int, int> mapeo;
    int total = 0;
    for(auto x : puntos) mapeo[x] = ++total;

    vector<int> contador1(total + 2), contador2(total + 2);
    for(int i = 1; i <= n; i++){
        auto [l, r] = intervalos[i];
        if(l != 1) contador1[mapeo[l]]++, contador1[mapeo[r] + 1]--;
        if(r != m) contador2[mapeo[l]]++, contador2[mapeo[r] + 1]--;
    }

    int resultado = 0, max1 = LLONG_MIN, max2 = LLONG_MIN;
    for(int i = 1; i <= total; i++){
        contador1[i] += contador1[i - 1], contador2[i] += contador2[i - 1];
        max1 = max(max1, contador1[i]), max2 = max(max2, contador2[i]);
        resultado = max(resultado, max(max1, max2));
    }

    cout << resultado << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t; t = 1; while(t--) resolver();
}

Enfoque por Enumeración con Árbol de Segmantos

El segundo enfoque consiste en enumerar todos los puntos como posibles valores máximos. Al igual que en el primer método, se requiere discretización. Luego, agregamos los intervalos en orden creciente. Dado el análisis anterior, incluir intervalos útiles nunca es subóptimo. Por lo tanto, incluimos todos los intervalos útiles y eliminamos los innecesarios.

Para esto, ordenamos los intervalos por su extremo izquierdo y mantenemos una cola de prioridad basada en el extremo derecho. Esto garantiza que no se incluyan intervalos duplicados. Para consultar el valor mínimo, podemos resolver el problema de RMQ dinámico utilizando un árbol de segmentos o un árbol de Fenwick.

#include <bits/stdc++.h>
#define int long long
#define izq u << 1
#define der u << 1 | 1
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;

struct Intervalo{
    int l, r;
    bool operator<(const Intervalo &otro) const{
        return r > otro.r;
    }
};

struct ArbolSegmento{
    struct Nodo{
        int l, r, maximo, minimo, adicionar;
    };
    
    int n;
    vector<Nodo> nodos;
    ArbolSegmento(int n_) : n(n_), nodos(n_ << 3) {}
    
    void actualizar(int u, int x){
        nodos[u].maximo += x;
        nodos[u].minimo += x;
        nodos[u].adicionar += x;
    }   

    Nodo combinar(Nodo izq, Nodo der){
        Nodo res;
        res.l = izq.l;
        res.r = der.r;
        res.maximo = max(izq.maximo, der.maximo);
        res.minimo = min(izq.minimo, der.minimo);
        return res;
    }

    void propagar(int u){
        if(nodos[u].adicionar){
            actualizar(izq, nodos[u].adicionar);
            actualizar(der, nodos[u].adicionar);
            nodos[u].adicionar = 0;
        }
    }

    void subir(int u){
        nodos[u].maximo = max(nodos[izq].maximo, nodos[der].maximo);
        nodos[u].minimo = min(nodos[izq].minimo, nodos[der].minimo);
    }

    void construir(int u, int l, int r){
        if(l == r){
            nodos[u] = {l, r, 0, 0, 0};
            return;
        }
        nodos[u] = {l, r, 0, 0, 0};
        int mid = l + r >> 1;
        construir(izq, l, mid);
        construir(der, mid + 1, r);
        subir(u);
    }

    void agregar(int u, int l, int r, int x){
        if(nodos[u].l >= l && nodos[u].r <= r){
            actualizar(u, x);
            return;
        }
        propagar(u);
        int mid = nodos[u].l + nodos[u].r >> 1;
        if(l <= mid) agregar(izq, l, r, x);
        if(r > mid) agregar(der, l, r, x);
        subir(u);
    }

    Nodo consultar(int u, int l, int r){
        if(nodos[u].l >= l && nodos[u].r <= r){
            return nodos[u];
        }
        propagar(u);
        int mid = nodos[u].l + nodos[u].r >> 1;
        Nodo res = {0, 0, 0, 0, 0};
        if(l <= mid) res = consultar(izq, l, r);
        if(r > mid) res = combinar(res, consultar(der, l, r));
        return res;
    }

};

void resolver() {
    int n, m; cin >> n >> m;

    vector<int> puntos;
    vector<Intervalo> intervalos(n + 1);
    for(int i = 1; i <= n; i++){
        int l, r; cin >> l >> r;
        puntos.push_back(l), puntos.push_back(r);
        intervalos[i] = {l, r};
    }
    puntos.push_back(1), puntos.push_back(m);
    
    sort(puntos.begin(), puntos.end());
    puntos.erase(unique(puntos.begin(), puntos.end()), puntos.end());

    map<int, int> mapeo;
    int total = puntos.size();
    for(int i = 1; i <= total; i++) mapeo[puntos[i - 1]] = i;

    vector<int> c(total + 2);
    for(int i = 1; i <= n; i++){
        auto &[l, r] = intervalos[i];
        l = mapeo[l], r = mapeo[r];
        c[l]++, c[r + 1]--;
    }

    sort(intervalos.begin() + 1, intervalos.end(), [](Intervalo a, Intervalo b){
        return a.l < b.l;
    });

    priority_queue<Intervalo> cola;
    ArbolSegmento Arbol(total);
    Arbol.construir(1, 1, total);

    int actual = 1, res = LLONG_MIN;
    for(int i = 1; i <= total; i++){
        c[i] += c[i - 1];
        while(actual <= n && intervalos[actual].l <= i){
            Arbol.agregar(1, intervalos[actual].l, intervalos[actual].r, 1);
            cola.push(intervalos[actual++]);
        }
        while(!cola.empty() && cola.top().r < i){
            Arbol.agregar(1, cola.top().l, cola.top().r, -1);
            cola.pop();
        }
        res = max(res, c[i] - Arbol.nodos[1].minimo);
    }   
    
    cout << res << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t; cin >> t; while(t--) resolver();
}