Dado dois conjuntos de intervalos, A e B, onde A contém N intervalos e B contém M intervalos, o objetivo é calcular o comprimento total da diferença A - B. Isso equivale a encontrar a medida total da região coberta por pelo menos um intervalo de A, mas que não é coberta por nenhum intervalo de B.

Por exemplo, se A = {[2, 5], [4, 10], [14, 18]} e B = {[1, 3], [8, 15]}, a diferença A - B resulta nos intervalos (3, 8) e (15, 18]. O comprimento total é (8 - 3) + (18 - 15) = 5 + 3 = 8.

Abordagem: Algoritmo de Linha de Varredura

Uma solução ingênua exigiria a comparação de todos os pares de intervalos, o que seria ineficiente. Em vez disso, podemos utilizar o Algoritmo de Linha de Varredura (Sweep-line). A ideia central é projetar os intervalos em um eixo unidimensional e processar seus pontos de início e fim como eventos ordenados.

Cada intervalo é decomposto em dois eventos: um para o início (que incrementa a contagem de cobertura) e um para o fim (que decrementa a contagem). Ao ordenar todos os eventos de A e B por suas coordenadas, percorremos o eixo da esquerda para a direita. Durante a varredura, mantemos o estado de quantos intervalos de A e B estão ativos no momento.

Se, em um determinado segmento entre dois eventos consecutivos, houver pelo menos um intervalo de A ativo e nenhum intervalo de B ativo, a distância entre as coordenadas desses eventos é somada ao comprimento total da diferença.

Formato de Entrada e Saída

Entrada:

• A primeira linha contém dois inteiros N e M (1 ≤ N, M ≤ 100.000).
• A segunda linha contém 2N inteiros representando os limites dos intervalos do conjunto A.
• A terceira linha contém 2M inteiros representando os limites dos intervalos do conjunto B.

Saída:

Um único inteiro representando o comprimento de A - B.

Exemplo

Entrada:

3 2
2 5 4 10 14 18
1 3 8 15

Saída:

8

Implementação em C++

Abaixo está a implementação otimizada utilizando a abordaegm de eventos com deltas (incrementos e decrementos), o que simplifica a lógica de transição de estados e elimina a necessidade de múltiplas verificações condicionais complexas:

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

using namespace std;

struct SweepEvent {
    long long coordinate;
    int delta_a;
    int delta_b;
};

bool eventComparator(const SweepEvent& a, const SweepEvent& b) {
    return a.coordinate < b.coordinate;
}

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

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<SweepEvent> events;
    events.reserve(2 * n + 2 * m);

    for (int i = 0; i < n; ++i) {
        long long l, r;
        cin >> l >> r;
        events.push_back({l, 1, 0});
        events.push_back({r, -1, 0});
    }

    for (int i = 0; i < m; ++i) {
        long long l, r;
        cin >> l >> r;
        events.push_back({l, 0, 1});
        events.push_back({r, 0, -1});
    }

    sort(events.begin(), events.end(), eventComparator);

    long long total_difference_length = 0;
    int active_a = 0;
    int active_b = 0;
    long long previous_coordinate = 0;

    for (const auto& evt : events) {
        if (active_a > 0 && active_b == 0) {
            total_difference_length += evt.coordinate - previous_coordinate;
        }
        
        active_a += evt.delta_a;
        active_b += evt.delta_b;
        previous_coordinate = evt.coordinate;
    }

    cout << total_difference_length << "\n";

    return 0;
}