I. Diferenças e Soma de Prefixos

P2184 – Terra Gulosa

Enunciado: Dado um comprimento de defesa n e m operações, cada operação semeia uma mina em um intervalo [l, r]. Consulte o número de tipos de minas em um intervalo.

Análise: Representar o intervalo de minas como segmentos. O número de tipos em [a, b] pode ser obtido como: quantidade de inícios de segmentos em [1, b] menos a quantidade de fins em [1, a].

P1438 – Sequência Chata

Enunciado: Operações de adicionar uma progressão aritmética em um intervalo e consultas em intervalos.

Análise: Converter a sequência original em um array de diferenças transforma as operações de adição em intervalo em operações simples no array de diferenças.

Resumo: Adicionar uma progressão aritmética com primeiro termo k e razão d no intervalo [l, r] equivale a: adicionar k na posição l do array de diferenças, adicionar d no intervalo [l+1, r] e subtrair k + d*(r-l) na posição r+1.

II. Algoritmos Gulosos

P1607 – Fair Shuttle

Enunciado: De 1 a n existem k grupos de vacas que querem viajar de s para e. O ônibus tem capacidade c e só anda em uma direção. Determine o número máximo de vacas que podem ser transportadas (grupos podem enviar apenas parte de seus membros).

Análise: Simular o processo de embarque usando uma árvore de segmentos. Classificar os grupos por ponto final crescente. Usar a árvore para manter o número máximo de ocupantes durante a simulação.

P1937 – Alocação de Celeiros

Enunciado: n pontos, cada um com capacidade c_i. m operações: adicionar 1 a todos os elementos em [l, r]. Pergunte o número máximo de operações que podem ser realizadas sem ultrapassar as capacidades.

Aálise: Similar ao problema anterior. Manter o valor mínimo em cada intervalo da árvore de segmentos. Se o mínimo for ≥ 1, subtrair 1 de todo o intervalo e incrementar a resposta.

IV. Soma Máxima de Subsequência Contínua

P4513 / GSS3 – Queries de Soma Máxima de Subsequência

Enunciado: 1. Consultar a soma máxima de subsequência contínua em um intervalo. 2. Atualizar um único elemento.

Análise: Modelo padrão. Ao combinar nós filhos ls e rs no pai u, a subsequência máxima pode estar totalmente dentro de ls, totalmente dentro de rs, ou cruzando o ponto médio.

Cada nó armazena: soma, prefixo (máximo começando pela esquerda), sufixo (máximo terminando pela direita), e ms (soma máxima de subsequência contínua).

Combinação:

• soma[u] = soma[ls] + soma[rs]
• prefixo[u] = max(prefixo[ls], soma[ls] + prefixo[rs])
• sufixo[u] = max(sufixo[rs], soma[rs] + sufixo[ls])
• ms[u] = max(ms[ls], ms[rs], sufixo[ls] + prefixo[rs])

Observação na consulta: A consulta deve combinar nós de maneira semelhante à combinação no pushup.

Info consulta(int no, int l, int r) {
    if (tr[no].l >= l && tr[no].r <= r) {
        return tr[no];
    }
    if (r <= tr[no].mid()) return consulta(no*2, l, r);
    if (l > tr[no].mid()) return consulta(no*2+1, l, r);
    Info T, L = consulta(no*2, l, r), R = consulta(no*2+1, l, r);
    T.soma = L.soma + R.soma;
    T.prefixo = max(L.prefixo, L.soma + R.prefixo);
    T.sufixo = max(R.sufixo, R.soma + L.sufixo);
    T.ms = max(max(L.ms, R.ms), L.sufixo + R.prefixo);
    return T;
}

P2572 – Operações em Sequência

Enunciado: Sequência de 0s e 1s. Operações: zerar intervalo, tornar todos 1, inverter intervalo, contar 1s em intervalo, encontrar maior subsequência contínua de 1s em intervalo.

Análise: Similar à soma máxima de subsequência contínua, mas agora para ambos os valores 0 e 1. Cada nó mantém informações para zeros e uns: soma0, prefixo0, sufixo0, ms0 (análogo para 1s). A operação de inversão troca as informações de 0s e 1s.

Observação: Atualização de prefixos e sufixos deve considerar o valor atual após lazy propagation.

V. Construção Otimizada de Grafos

Enunciado: Geralmente relacionado a caminhos mínimos. Construir uma árvore in e uma árvore out. A árvore in conecta de cima para baixo, depois conecta à árvore out, que conecta de baixo para cima. Assim, para conectar um vértice a um intervalo [a, b], basta conectar ao nó correspondente na árvore.

Complexidade: O(n) reduzido para O(log n).

CF786B – Legacy

Enunciado: Três tipos de arestas: 1) de u para v com peso w; 2) de u para todos os vértices em [l, r] com peso w; 3) de todos os vértices em [l, r] para u com peso w. Encontrar caminhos mínimos do vértice s a todos os outros.

Solução: Otimização por árvore de segmentos + Dijkstra.

void add(int u, int v, long long w) {
    // adicionar aresta u -> v com peso w
}

void build(int no, int l, int r) {
    if (l == r) {
        idx[l] = no; // mapear folha
        return;
    }
    int esq = no*2, dir = no*2+1;
    add(no, esq, 0); add(no, dir, 0); // in-tree
    add(esq + OFFSET, no + OFFSET, 0); add(dir + OFFSET, no + OFFSET, 0); // out-tree
    build(esq, l, (l+r)/2);
    build(dir, (l+r)/2+1, r);
}

void connect(int no, int l, int r, int ql, int qr, int from, long long w, bool toInterval) {
    if (ql <= l && r <= qr) {
        if (toInterval) add(from, no, w); // de um ponto para intervalo
        else add(no + OFFSET, from, w); // de intervalo para um ponto
        return;
    }
    int mid = (l+r)/2;
    if (ql <= mid) connect(no*2, l, mid, ql, qr, from, w, toInterval);
    if (qr > mid) connect(no*2+1, mid+1, r, ql, qr, from, w, toInterval);
}

int main() {
    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        add(idx[i], idx[i] + OFFSET, 0); // conectar folha in e out
        add(idx[i] + OFFSET, idx[i], 0);
    }
    // ... processar arestas e rodar Dijkstra a partir de s
}

VI. Busca Binária

Uma árvore de segmentos de valores (ordem estatística) pode ser usada para busca binária. Aplicação: pares inversos.

P2824 – Ordenação

Enunciado: Uma permutação de 1..n, m operações de ordenar um intervalo em ordem crescente ou decrescente. Consultar o valor na posição p após todas as operações.

Análise: Busca binária na resposta. Para um valor candidato k, transformar a sequência: 1 se o valor ≥ k, 0 caso contrário. Simular as operações de ordenação usando uma árvore de segmentos que mantém a contagem de 1s. Se a ordenação for crescente, mover todos os 1s para o final do intervalo; se decrescente, mover para o início. A resposta é o menor k tal que a posição p tenha valor 1 após a simulação.

struct Node {
    int l, r, sum, lazy; // lazy: -1 sem atribuição, 0 ou 1
};

void pushDown(int no) {
    if (tr[no].lazy != -1) {
        int val = tr[no].lazy;
        tr[no*2].lazy = tr[no*2+1].lazy = val;
        tr[no*2].sum = val * (tr[no*2].r - tr[no*2].l + 1);
        tr[no*2+1].sum = val * (tr[no*2+1].r - tr[no*2+1].l + 1);
        tr[no].lazy = -1;
    }
}

void build(int no, int l, int r, int k) {
    tr[no] = {l, r, 0, -1};
    if (l == r) {
        tr[no].sum = (arr[l] >= k) ? 1 : 0;
        return;
    }
    int mid = (l+r)/2;
    build(no*2, l, mid, k);
    build(no*2+1, mid+1, r, k);
    tr[no].sum = tr[no*2].sum + tr[no*2+1].sum;
}

void assign(int no, int l, int r, int val) {
    if (tr[no].l >= l && tr[no].r <= r) {
        tr[no].sum = val * (tr[no].r - tr[no].l + 1);
        tr[no].lazy = val;
        return;
    }
    pushDown(no);
    if (l <= tr[no].mid()) assign(no*2, l, r, val);
    if (r > tr[no].mid()) assign(no*2+1, l, r, val);
    tr[no].sum = tr[no*2].sum + tr[no*2+1].sum;
}

int query(int no, int l, int r) {
    if (tr[no].l >= l && tr[no].r <= r) return tr[no].sum;
    pushDown(no);
    int res = 0;
    if (l <= tr[no].mid()) res += query(no*2, l, r);
    if (r > tr[no].mid()) res += query(no*2+1, l, r);
    return res;
}

bool check(int k) {
    build(1, 1, n, k);
    for (int i = 1; i <= m; i++) {
        int cnt = query(1, queries[i].l, queries[i].r);
        if (queries[i].type == 0) { // crescente
            assign(1, queries[i].r - cnt + 1, queries[i].r, 1);
            assign(1, queries[i].l, queries[i].r - cnt, 0);
        } else { // decrescente
            assign(1, queries[i].l, queries[i].l + cnt - 1, 1);
            assign(1, queries[i].l + cnt, queries[i].r, 0);
        }
    }
    return query(1, p, p) == 1;
}

int main() {
    // ... leitura ...
    int lo = 1, hi = n, ans = n;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (check(mid)) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    printf("%d\n", ans);
}

P4344 – Terapia Cerebral

Enunciado: Sequência binária de comprimento n, inicialmente todos 1. Três operações: 1) cobrir intervalo com 0; 2) copiar intervalo [l0, r0] para [l1, r1] (cortando ou preenchendo com 0 conforme necessário) e zerar a origem; 3) encontrar a maior subsequência contínua de 0s em um intervalo.

Análise: A operação 3 é similar à soma máxima de subsequência contínua, mas para zeros. Para a operação 2, note que o número de zeros copiados é monotônico em relação ao intervalo destino. Usar busca binária para encontrar o menor intervalo destino que acomode todos os zeros da origem.

void copiar(int l0, int r0, int l1, int r1) {
    int zeros = consultaZeros(1, l0, r0); // número de zeros em [l0,r0]
    if (zeros == 0) return;
    cobrirZeros(1, l0, r0); // zerar [l0,r0]
    int lo = l1, hi = r1, alvo = l1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (consultaZeros(1, l1, mid) >= zeros) {
            alvo = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    // preencher [l1, alvo] com 1s? Na verdade, a operação copia os valores originais.
    // Implementação simplificada: percorrer e copiar individualmente ou usar outra lazy propagation.
}

VII. Dois Ponteiros

P1712 – Intervalos

Enunciado: Dados n intervalos, escolehr m deles que tenham interseção não vazia. Minimizar a diferença entre o comprimento do maior e do menor intervalo escolhido.

Análise: Classificar os intervalos por comprimento. Usar dois ponteiros i e j para manter uma janela de intervalos. Adicionar o intervalo j, atualizando a cobertura dos pontos (usando uma árvore de segmentos que mantém o máximo de cobertura). Quando a cobertura máxima atingir m, mover i para reduzir a janela. A resposta é a menor diferença len[j] - len[i] encontrada.

int main() {
    // ... leitura e discretização dos pontos dos intervalos ...
    sort(intervals, intervals + n, [](const Interval& a, const Interval& b) { return a.comprimento < b.comprimento; });
    build(1, 1, numPontos); // árvore de segmentos para máximo de cobertura
    int ans = INF, i = 0, j = 0;
    while (j < n) {
        while (tr[1].max < m && j < n) {
            update(1, intervals[j].l, intervals[j].r, 1);
            j++;
        }
        if (tr[1].max < m) break;
        while (tr[1].max >= m && i < j) {
            update(1, intervals[i].l, intervals[i].r, -1);
            i++;
        }
        ans = min(ans, intervals[j-1].comprimento - intervals[i-1].comprimento);
    }
    printf("%d\n", ans == INF ? -1 : ans);
}