Tópicos Diversos

• DP com transição linear entre estados

Inicialização

• Inicializar todos os estágios conforme o contexto do problema

DP sobre Subconjuntos

• Iteração sobre submáscaras para DP em conjuntos

DP de Dígitos

• Dependência com dígitos anteriores
• Independência entre dígitos

DP Matricial

• Definição da matriz base, matriz de transição e matriz identidade

Teoria dos Grafos

Graus

• Remover arestas duplicadas ao calcular in-degree e out-degree

Ordenação Topológica

• Remoção iterativa de vértices durante a ordenação

Fluxo em Rede

• Aumento por múltiplos caminhos
• Otimização do arco atual
• Eliminação de nós saturados
• Tratamento de fluxo nulo

Algoritmos Fundamentais

Dois Ponteiros

• Busca pelo k-ésimo par mais distente

Tabela Sparse (ST)

Manutenção

• Suporte a operações idempotentes (min, max, gcd)
• Passos em potências de dois

Técnicas

• Uso de exponenciação rápida para processar ST (risco de MLE)

Diferenças

• Diferenças de segunda ordem

Somas Prefixadas

• Prefixos e sufixos de intervalos

Operações Bit a Bit

• Decomposição de inteiros via bits
• Código de Gray para resolver Torres de Hanói

Multiplicação Binária (Binary Lifting)

• Expansão logarítmica com doubling
• Operações idempotentes: gcd, max, OR, AND — mantidas via ST

Gulosos

• Guloso com arrependimento (reverse greedy)

Método da Linha de Varredura

• Aplicação em matrizes densas
• Aplicação em matrizes esparsas

Estruturas de Dados

Árvore de Segmentos

Pilha de Prioridade para Lazy Propagation

// Hipótese para propagação de marcadores lazy:
// Se a operação A tem prioridade maior que B,
// antes de sobrescrever o lazy de A, aplica-se A sobre o lazy de B.
// Isso garante a ordem correta de precedência.
// Modela-se como uma pilha estruturada por prioridade.
// Ao descer o lazy para o nó filho, percorre-se a pilha
// aplicando cada operação no campo soma do nó.

// Estrutura genérica
struct Marcador {
    int operacao;
    long long valor;
};

struct NoSeg {
    long long soma;
    stack<Marcador> lazyStack;
};

Variantes

• Árvore de segmentos por valor (indexada por peso)
• Fusão de árvores de segmentos
• Árvore de segmentos no tempo (segment tree divide & conquer)

Heaps

• heaps opostos para k-ésimo maior elemento

Union-Find (DSU)

• Union-Find com valor por intevralo
• Union-Find como lista encadeada

// Resolve problemas do tipo:
// Dado um array inicial todo preenchido com 1,
// e q consultas com índice alvo:
// Encontrar o maior r tal que r <= alvo e vet[r] == 1
// Em seguida, marcar vet[r] = 0

struct DSU {
    vector<int> pai;
    DSU(int n) : pai(n + 1) {
        iota(pai.begin(), pai.end(), 0);
    }
    int encontrar(int x) {
        return (pai[x] == x) ? x : pai[x] = encontrar(pai[x]);
    }
    void desativar(int x) {
        pai[x] = encontrar(x - 1);
    }
};

• Union-Find com rollback

Pilha

• pilhas opostas

Fila

• Deque simulado com duas pilhas

Árvore de Fenwick (BIT)

• Busca binária sobre a árvore de Fenwick

Utilitários Diversos

• Policy-Based Data Structures (pbds)
• Funções intrínsecas do compilador (__builtin)

Avisos e Boas Práticas

Recomendações para evitar erros comuns:

- Limpe sempre os arrays entre casos de teste; resíduos causam resultados incorretos.
- Libere toda memória alocada dinamicamente; vazamentos provocam lentidão.
- Em estruturas aninhadas, garanta que destrutores sejam chamados corretamente.
- Em união-find, sempre faça compressão de caminho; sem isso, o degrada.
- Em KMP, valide os saltos da tabela de falhas para não romper o casamento.
- Em árvores de segmentos, não esqueça de propagar os marcadores lazy.
- Em ordenação topológica, verifique a existência de ciclos.
- Evite usar cin/cout sem sincronização em volumes massivos de dados.
- Cuidado com colisões em tabelas hash; use duplo hash quando necessário.
- Em compressão de coordenadas, ordene e remova duplicatas com atenção.
- Em busca binária, garanta convergência para evitar laços infinitos.
- Em estratégias gulosas, prove a correção; casos contra-exemplo são comuns.
- Em DP, confira a transição de estados; um erro invalida toda a solução.
- Em operações bit a bit, respeite a precedência; parênteses evitam surpresas.
- Em aritmética modular, normalize valores negativos após subtrações.
- Evite divisão por zero; verifique denominadores antes de operar.
- Redirecione arquivos de entrada e saída quando exigido pelo problema.
- Calcule o consumo de memória com antecedência para evitar MLE.
- Atenção ao redimensionamento de containers STL durante iteração.
- Remova instruções de depuração antes da submissão final.
- Verifique limites dos arrays; acesso fora do intervalo gera RE.
- Em algoritmos recursivos, defina claramente o caso base.
- Em problemas com múltiplos casos de teste, reinicialize todas as estruturas.