Par con mínima diferencia absoluta después de resolver cada consulta

Dadas las consultas Q y una lista vacía. 
Las consultas pueden ser de dos tipos: 
 

1. addToList(x) : Agrega x a tu lista.
2. removeFromList(x) : Elimina x de tu lista.

La tarea es, después de cada consulta, imprimir el valor mínimo de abs(lista[i]-lista[j]) donde, 0<=i<=n, 0<=j<=n y i ≠ j y n es el número total de elementos presentes en la lista. 
Ejemplos : 
 

Entrada : Q = 4 
addToList(1), inserte 1 en nuestro conjunto 
addToList(5), inserte 5 en nuestro conjunto 
addToList(3), inserte 3 en nuestro conjunto 
removeFromList(3), elimine 3 en nuestro conjunto 
Salida : 
0, como solo tenemos un elemento {1} en nuestro conjunto. 
4, como tenemos {1, 5} la diferencia mínima entre todos los pares posibles es 4 (5-1) 
2, como tenemos {1, 3, 5} la diferencia mínima entre todos los pares posibles es 2 (3-1) 
4, como tenemos {1, 5} la diferencia mínima entre todos los pares posibles es 4 (5-1) 
 

Método 1: la idea es utilizar C++ configurado para almacenar todos los elementos de modo que la inserción o eliminación se pueda realizar en O(log(n)) manteniendo los elementos ordenados. Ahora, para encontrar la diferencia mínima, tenemos que iterar sobre todo el conjunto y encontrar la diferencia solo entre los elementos adyacentes, ya que los elementos están ordenados, es decir, la diferencia mínima siempre la aportarán los elementos adyacentes. Esto se puede hacer en una complejidad de tiempo O(n). Entonces, la complejidad temporal general de este enfoque será (q*log(n)+q*n). 
Método 2: 
Podemos usar multiset para almacenar y mantener todos los elementos y map para almacenar la diferencia entre los elementos adyacentes en orden ordenado, donde la clave del mapa representa la diferencia entre los elementos adyacentes y el valor del mapa correspondiente representa la frecuencia de ocurrencia de esta diferencia. 
A continuación se muestra el algoritmo completo: 
Primero, inserte dos valores centinela en el conjunto múltiple. Digamos (-10^9+7 y 10^9+7) e inicialicemos el mapa con la diferencia de este valor centinela, es decir, 2*10^7+7, y fijemos su frecuencia en 1. 
Ahora tenemos dos tipos de consultas: 
 

1. Consulta de inserción: para una consulta de inserción, primero inserte el valor insertado. Después de insertar el elemento, tendremos que actualizar también las diferencias de los elementos adyacentes en el mapa. Para hacer esto, busque los valores izquierdo y derecho del elemento recién insertado en el conjunto. Anteriormente, cuando este nuevo valor no se insertó en el conjunto, abs (derecha-izquierda) contribuye a los diferentes términos en el mapa. Para actualizar el mapa después de insertar el nuevo elemento, primero elimine la diferencia anterior abs (derecha-izquierda) ya que se inserta un nuevo valor entre los elementos izquierdo y derecho y agregue dos diferencias al mapa. es decir, abs(derecha-x) y abs(x-izquierda).
2. Consulta de Eliminación: En caso de eliminación de un valor del conjunto. Primero, busque los elementos izquierdo y derecho de los elementos que deben eliminarse, digamos x. Luego, de acuerdo con el algoritmo anterior, reduzca la frecuencia de abs (derecha-x) y abs (izquierda-x) e incremente la frecuencia de abs (derecha-izquierda).

Por lo tanto, cada consulta se puede resolver en complejidad de tiempo log(n). Por lo tanto, la complejidad global será O(q*log(n)).
 

// C++ implementation of above approach
#include <bits/stdc++.h>
#define ll long long int
const ll MOD = 1e9 + 7;
using namespace std;
 
// Function to add an element into the list
void addToList(int x, multiset<ll>& s, map<ll, ll>& mp)
{
    // firstly insert value in set
    s.insert(x);
 
    // find left and right value of inserted value.
    ll left, right;
 
    // now here is logic explained below
    left = *(--s.find(x));
    right = *(++s.find(x));
    mp[abs(left - x)]++;
    mp[abs(right - x)]++;
    mp[abs(left - right)]--;
    if (mp[abs(left - right)] == 0)
        mp.erase(abs(left - right));
}
 
// Function to remove an element from the list
void removeFromList(int x, multiset<ll>& s, map<ll, ll>& mp)
{
    ll left, right;
 
    // Find left element of number that we want to delete.
    left = *(--s.find(x));
 
    // Find right element of number that we want to delete.
    right = *(++s.find(x));
 
    // remove x from set
    s.erase(s.find(x));
 
    // Again this will explain below in article.
    mp[abs(left - x)]--;
    if (mp[abs(left - x)] == 0)
        mp.erase(abs(left - x));
    mp[abs(right - x)]--;
    if (mp[abs(right - x)] == 0)
        mp.erase(abs(right - x));
 
    mp[abs(left - right)]++;
}
 
// Driver code
int main()
{
 
    int q = 4;
 
    // define set to store all values.
    multiset<ll> s;
 
    // define map to store difference in sorted
    map<ll, ll> mp;
 
    // initialize set with sentinel values
    s.insert(-MOD);
    s.insert(MOD);
 
    // maintain freq of difference in map so, here initially
    // difference b/w sentinel value and its freq is one.
    mp[2 * MOD] = 1;
 
    // 1st query 1 1 i.e, include 1 in our set
    addToList(1, s, mp);
 
    // As now we have only one element {-10^9+7, 1, 10^9+7}
    // (except two are sentinel values)
    // so minimum among all pair is zero
    cout << 0 << endl;
 
    // 2nd query 1 5 i.e, include 5 in our set.
    addToList(5, s, mp);
 
    // find smallest difference possible
    // as it should be in beginning of map
    cout << mp.begin()->first << endl;
 
    // 3rd query 1 3 i.e, include 3 in our set.
    addToList(3, s, mp);
 
    // find smallest difference possible
    // as it should be in beginning of map
    cout << mp.begin()->first << endl;
 
    // 4th query 2 3 i.e, remove 3 from our list
    removeFromList(3, s, mp);
 
    cout << mp.begin()->first << endl;
 
 return 0;
}

0
4
2
4

Explicación de cada consulta: 
 

1. addToList(1): Como ahora solo tenemos un elemento {-10^9+7, 1, 10^9+7} (excepto que dos son valores centinela), por lo que el mínimo entre todos los pares es cero.
2. addToList(5): después de insertar 1 y 5 en el conjunto, el conjunto se convierte en {-10^9+7, 1, 5, 10^9+7} y mapa: mp[5-1]=1 donde la clave representa la diferencia y su valor representa la frecuencia.
3. addToList(3): Como aquí estamos insertando 3. Entonces, primero, encontramos el elemento izquierdo y derecho de 3 en el conjunto después de la inserción, es decir, izquierda = 1, derecha = 5. Como 3 vino entre 1 y 5, entonces quitar mapa[5-1]–. (como 3 quedó entre 1 y 5, entonces 5-1 ya no será mínimo) E incluimos estas diferencias map[3-1]++ y map[5-3]++ (porque 3 quedó entre 1 y 5, entonces mínimo posible tener dos casos).
4. removeFromList(3): Similar a la consulta anterior, aquí estamos eliminando el elemento. Entonces, primero, encuentre los elementos izquierdo y derecho para 3, es decir, izquierda = 1, derecha = 5. Como vamos a eliminar 3, que está entre 1 y 5, la diferencia mínima se verá afectada solo por 3 y 5,

before deleting ==>{1, 3, 5}, 
after deleting ==> {1, 5}. 
So, map[3-1]--, map[5-3]-- and add map[5-1]++.

Complejidad de tiempo: O(qlogN), donde ‘q’ es el número total de consultas.
Espacio Auxiliar: O(q).