Análise de Subsequências e Expansão de Intervalos

Para resolver problemas que envolvem encontrar o valor máximo baseado em elementos mínimos de um intervalo, uma técnica eficiente é processar os elementos em ordem decrescente e gerenciar a união de intervalos adjacentes. Ao fixar um valor como o mínimo, o objetivo é estender o intervalo o máximo possível para ambos os lados.

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

using namespace std;

typedef long long ll;

struct Elemento {
    int valor, pos;
};

bool compararDecrescente(const Elemento& a, const Elemento& b) {
    return a.valor > b.valor;
}

const int MAX = 2000005;
int link_esq[MAX], link_dir[MAX], data[MAX];
Elemento itens[MAX];
int ordem[MAX];

int main() {
    int n;
    if (scanf("%d", &n) == EOF) return 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &itens[i].valor);
        data[i] = itens[i].valor;
        itens[i].pos = i;
    }
    sort(itens + 1, itens + n + 1, compararDecrescente);
    for (int i = 1; i <= n; i++) ordem[i] = itens[i].pos;

    ll resultado_maximo = 0;
    for (int i = 1; i <= n; i++) {
        int p = ordem[i];
        int tamanho = 1;
        if (link_esq[p - 1]) tamanho += (p - link_esq[p - 1]);
        if (link_dir[p + 1]) tamanho += (link_dir[p + 1] - p);
        
        resultado_maximo = max(resultado_maximo, (ll)tamanho * data[p]);
        
        if (link_esq[p - 1] && link_dir[p + 1]) {
            int e = link_esq[p - 1], d = link_dir[p + 1];
            link_dir[e] = d; link_esq[d] = e;
        } else if (link_esq[p - 1]) {
            int e = link_esq[p - 1];
            link_esq[p] = e; link_dir[e] = p;
        } else if (link_dir[p + 1]) {
            int d = link_dir[p + 1];
            link_dir[p] = d; link_esq[d] = p;
        } else {
            link_esq[p] = link_dir[p] = p;
        }
    }
    printf("%lld\n", resultado_maximo);
    return 0;
}

Programação Dinâmica com Restrições de Paridade

Em problemas de seleção de elementos onde não se pode escolher itens adjacentes e deve-se selecionar exatamente metade do conjunto, a paridade do tamanho da sequência altera significativamente a estratégia. Para sequências ímpares, existe a flexibilidade de "pular" um espaço extra uma única vez.

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

using namespace std;

const long long INF_NEG = -1e17;

int main() {
    int total;
    scanf("%d", &total);
    vector<int> seq(total + 1);
    for (int i = 1; i <= total; i++) scanf("%d", &seq[i]);

    if (total % 2 == 0) {
        vector<vector<long long>> dp(total / 2 + 1, vector<long long>(2, INF_NEG));
        dp[1][0] = seq[1]; dp[1][1] = seq[2];
        for (int i = 2; i <= total / 2; i++) {
            dp[i][0] = dp[i-1][0] + seq[2 * i - 1];
            dp[i][1] = max(dp[i-1][0], dp[i-1][1]) + seq[2 * i];
        }
        printf("%lld\n", max(dp[total / 2][0], dp[total / 2][1]));
    } else {
        int blocos = total / 2;
        static long long f[100005][2][2];
        for(int i=0; i<=blocos; i++) 
            f[i][0][0] = f[i][0][1] = f[i][1][0] = f[i][1][1] = INF_NEG;

        f[1][0][0] = seq[1]; f[1][0][1] = seq[2];
        f[1][1][0] = max(seq[1], seq[2]); f[1][1][1] = seq[3];

        for (int i = 2; i <= blocos; i++) {
            f[i][0][0] = f[i-1][0][0] + seq[2*i - 1];
            f[i][0][1] = max(f[i-1][0][0], f[i-1][0][1]) + seq[2*i];
            f[i][1][0] = max({f[i-1][1][0] + seq[2*i], f[i-1][0][0] + max(seq[2*i-1], seq[2*i]), f[i-1][0][1] + seq[2*i]});
            f[i][1][1] = max({f[i-1][1][0], f[i-1][1][1], f[i-1][0][0], f[i-1][0][1]}) + seq[2*i + 1];
        }
        printf("%lld\n", max(f[blocos][1][0], f[blocos][1][1]));
    }
    return 0;
}

Busca Binária em Funções Monotônicas

Quando uma propriedade matemática apresenta monotonicidade, como a diferença entre um número e a soma de seus dígitos, a busca binária torna-se a ferramenta ideal para encontrar limites de validade.

#include <iostream>

using namespace std;

long long calcular_diferenca(long long x) {
    long long original = x, soma_digitos = 0;
    while (x > 0) {
        soma_digitos += x % 10;
        x /= 10;
    }
    return original - soma_digitos;
}

int main() {
    long long n, limite_s;
    if (scanf("%lld %lld", &n, &limite_s) != 2) return 0;
    long long inicio = 1, fim = n, alvo = n + 1;
    
    while (inicio <= fim) {
        long long meio = inicio + (fim - inicio) / 2;
        if (calcular_diferenca(meio) >= limite_s) {
            alvo = meio;
            fim = meio - 1;
        } else {
            inicio = meio + 1;
        }
    }
    printf("%lld\n", (alvo > n) ? 0LL : n - alvo + 1);
    return 0;
}

Maximizar XOR em Árvores com 01-Trie

Para encontrar o caminho em uma árvore cujo XOR das arestas seja máximo, utilizamos a propriedade $dist(u, v) = dist(root, u) \oplus dist(root, v)$. Armazenamos os prefixso XOR em uma estrutura de dados Trie binária para realizar consultas gulosas em tempo logarítmico.

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

using namespace std;

const int MAX_NODES = 100005;
struct Edge { int to, weight; };
vector<Edge> adj[MAX_NODES];
int xor_path[MAX_NODES];

struct BinaryTrie {
    int tree[MAX_NODES * 32][2], nodes_count = 0;
    void add(int val) {
        int curr = 0;
        for (int i = 30; i >= 0; i--) {
            int bit = (val >> i) & 1;
            if (!tree[curr][bit]) tree[curr][bit] = ++nodes_count;
            curr = tree[curr][bit];
        }
    }
    int query_max(int val) {
        int curr = 0, res = 0;
        for (int i = 30; i >= 0; i--) {
            int bit = (val >> i) & 1;
            if (tree[curr][!bit]) {
                res |= (1 << i);
                curr = tree[curr][!bit];
            } else {
                curr = tree[curr][bit];
            }
        }
        return res;
    }
} trie;

void dfs(int u, int p, int current_xor) {
    xor_path[u] = current_xor;
    trie.add(current_xor);
    for (auto& edge : adj[u]) {
        if (edge.to != p) dfs(edge.to, u, current_xor ^ edge.weight);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dfs(1, 0, 0);
    int max_xor = 0;
    for (int i = 1; i <= n; i++) max_xor = max(max_xor, trie.query_max(xor_path[i]));
    printf("%d\n", max_xor);
    return 0;
}

Otimização de Problemas Combinatórios: Números de Catalan e Inclusão-Exclusão

Muitos problemas de contagem podem ser modelados como caminhos em uma grade. O uso de fatoração prima para calcular coeficientes binomiais sob módulos não-primos é uma técnica essencial para evittar inversos modulares inexistentes.

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
int min_prime[2000005], primes[2000005], p_idx = 0;
int exponent[2000005];

void sieve(int limit) {
    for (int i = 2; i <= limit; i++) {
        if (!min_prime[i]) {
            min_prime[i] = i;
            primes[++p_idx] = i;
        }
        for (int j = 1; j <= p_idx && primes[j] * i <= limit; j++) {
            min_prime[primes[j] * i] = primes[j];
            if (i % primes[j] == 0) break;
        }
    }
}

ll power(ll base, int exp, int mod) {
    ll res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

int main() {
    int n, mod;
    scanf("%d %d", &n, &mod);
    sieve(2 * n);
    for (int i = 2; i <= n; i++) exponent[i]--;
    for (int i = n + 2; i <= 2 * n; i++) exponent[i]++;
    
    for (int i = 2 * n; i >= 2; i--) {
        if (min_prime[i] < i) {
            exponent[min_prime[i]] += exponent[i];
            exponent[i / min_prime[i]] += exponent[i];
            exponent[i] = 0;
        }
    }
    
    ll ans = 1;
    for (int i = 1; i <= p_idx; i++) {
        if (exponent[primes[i]]) {
            ans = (ans * power(primes[i], exponent[primes[i]], mod)) % mod;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

Mesclagem de Árvores de Segmentos (Segment Tree Merging)

Em problemas que exigem processar informações de subárvores e responder a consultas sobre a frequência ou o máximo de valores, a mesclagem dinâmica de árvores de segmentos é uma abordagem robusta. Essa técnica é frequentemente combinada com o algoritmo de união-busca (DSU) ou processamento de caminhos em árvores.

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 100005;
struct Node {
    int l_child, r_child, count, position;
} tree[MAXN * 50];

int nodes_cnt = 0, roots[MAXN], result[MAXN];

void push_up(int k) {
    if (tree[tree[k].l_child].count >= tree[tree[k].r_child].count) {
        tree[k].count = tree[tree[k].l_child].count;
        tree[k].position = tree[tree[k].l_child].position;
    } else {
        tree[k].count = tree[tree[k].r_child].count;
        tree[k].position = tree[tree[k].r_child].position;
    }
}

int update(int &k, int l, int r, int val, int delta) {
    if (!k) k = ++nodes_cnt;
    if (l == r) {
        tree[k].count += delta;
        tree[k].position = l;
        return k;
    }
    int mid = (l + r) >> 1;
    if (val <= mid) update(tree[k].l_child, l, mid, val, delta);
    else update(tree[k].r_child, mid + 1, r, val, delta);
    push_up(k);
    return k;
}

int merge(int u, int v, int l, int r) {
    if (!u || !v) return u | v;
    if (l == r) {
        tree[u].count += tree[v].count;
        return u;
    }
    int mid = (l + r) >> 1;
    tree[u].l_child = merge(tree[u].l_child, tree[v].l_child, l, mid);
    tree[u].r_child = merge(tree[u].r_child, tree[v].r_child, mid + 1, r);
    push_up(u);
    return u;
}