Nesta publicação, analisamos quatro problemas de programação competitiva que envolvem estruturas de dados avançadas e técnicas algorítmicas. Cada solução aborda desafios específicos, como consultas em intervalos, atualizações dinâmicas e manipulação de árvores.

Problema A: Contagem com Persistência

O primeiro problema explora o uso de árvores de segmento persistnetes para responder consultas eficientes em intervalos. O código implementa uma estrutura que permite contar elementos dentro de um intervalo específico, aproveitando a persistência para manter versões anteriores da árvore.

// Exemplo de estrutura persistente
#include <bits/stdc++.h>
using namespace std;
#define itn int
constexpr int TAM = 3000006;
int n, m, tipo;
int resp, total, topo;
int esq[TAM], dir[TAM], ant[TAM], nums[TAM], pilha[TAM], raiz[TAM];
struct Segmento{ int esq, dir, soma; } seg[TAM*30];
struct Aresta{ int v, prox; } arestas[TAM];
int cabeca[TAM], contArestas;

void inserir(int x, int& y, int l, int r, int pos){
    if (!y || y == x) y = ++total, seg[y].soma = seg[x].soma;
    seg[y].soma++;
    if (l == r) return;
    int mid = (l+r)>>1;
    if (pos <= mid)
        inserir(seg[x].esq, seg[y].esq, l, mid, pos);
    else
        inserir(seg[x].dir, seg[y].dir, mid+1, r, pos);
}

int consultar(int x, int y, int l, int r, int a, int b){
    if (a <= l && r <= b) return seg[y].soma - seg[x].soma;
    int mid = (l+r)>>1;
    if (b <= mid) return consultar(seg[x].esq, seg[y].esq, l, mid, a, b);
    if (a > mid) return consultar(seg[x].dir, seg[y].dir, mid+1, r, a, b);
    return consultar(seg[x].esq, seg[y].esq, l, mid, a, b) + consultar(seg[x].dir, seg[y].dir, mid+1, r, a, b);
}

int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m >> tipo;
    // Leitura e processamento...
    return 0;
}

Problema B: Soma Absoluta em Árvores

Este problema utiliza a decomposição de árvores (heavy-light decomposition) combinada com duas árvores de segmento para gerenciar valores positivos e negativos separadamente. A ideia central é que ao adicionar um valor positivo, os números negativos só mudam de sinal uma vez, permitindo atualizações pontuais eficientes.

// Estruturas para soma e máximo
struct ArvoreSoma{
    int tree[TAM*4], lazy[TAM*4], tamanho[TAM*4];
    void construir(int x, int l, int r){
        if(l == r){
            tree[x] = novo[l] >= 0 ? novo[l] : 0;
            tamanho[x] = novo[l] >= 0 ? 1 : 0;
            return;
        }
        int mid = (l+r)>>1;
        construir(x<<1, l, mid);
        construir(x<<1|1, mid+1, r);
        atualizar(x);
    }
    void atualizar(int x){
        tree[x] = tree[x<<1] + tree[x<<1|1];
        tamanho[x] = tamanho[x<<1] + tamanho[x<<1|1];
    }
    // Métodos para adicionar lazy e consultar...
};

struct ArvoreMax{
    struct Par{ int valor, indice; };
    Par maximo[TAM*4];
    int tree[TAM*4], lazy[TAM*4], tamanho[TAM*4];
    // Implementação similar com busca de máximos negativos...
};

Problema C: Computação em Blocos

A solução utiliza divisão em blocos com estrutura de árvore BIT (Fenwick) para consultas em intervalo. Um aspecto crucial é a tabela f[i][j] que armazena o número de nós do caminho da raiz até i que pertencem ao bloco j, permitindo atualizações rápidas.

int f[TAM][320], bloco[TAM], valor[TAM];
void dfs(int x, int pai){
    for(int i=1; i<=numBlocos; i++) f[x][i] = f[pai][i];
    f[x][bloco[x]]++;
    esq[x] = ++tempo;
    peso[x] = valor[x];
    for(int v : adj[x]){
        if(v == pai) continue;
        dfs(v, x);
        peso[x] += peso[v];
    }
    dir[x] = tempo;
}

Problema D: Caminhos Mínimos e Dijkstra

Este problema apresenta uma variação do algoritmo de Dijkstra onde, além de encontrar distâncias mínimas, ordenam-se os vértices por distância. A abordagem utiliza múltiplas execuções do algoritmo combinadas com estruturas de dados para enumerar arestas e vértices intermediários.

Revisão de Estruturas

Durante a preparação para a prova inicial, foram revisados conceitos fundamentais:

• BIT (Fenwick Tree) para consultas de prefixo
• Árvores de Segmento com lazy propagation
• Árvores Persistentes (Chairman Tree)
• Union-Find com variações (compressão de caminho, união por peso, reversão)

Estes problemas demonstram a importância de dominar estruturas de dados avançadas e técnicas de otimização para competições de programação.