Notas de Implementação e Armadilhas em C++

Ao trabalhar com estruturas de dados dinâmicas como o std::vector, é crucial evitar loops que dependam do tamanho atual do container enquanto ele é modificado. Por exemplo, a instrução for (int i = 0; i < (int)v.size(); i++) v.push_back(1); resultará em um loop infinito, pois o limite superior aumenta a cada iteração. Além disso, o sombreamento de variáveis em macros ou loops aninhados (como utilizar o mesmo nome de iterador i em níveis diferentes) pode causar comportamentos indefinidos e bugs de difícil detecção. ### Resolução do Problema MEX em Intervalos (Algoritmo de Mo)

O problema de encontrar o menor valor ausente (MEX - Minimum Excluded value) em diversos intervalos de um array pode ser resolvido eficientemente utilizando o **Algoritmo de Mo com Rollback**. A observação principal é que a operação de remoção para o MEX é simples: ao remover um elemento, se a contagem desse valor chegar a zero, ele se torna um candidato para o novo MEX (basta comparar o valor removido com o MEX atual e pegar o mínimo). No entanto, a operação de inserção não possui essa propriedade de atualização direta. Por isso, utilizamos uma abordagem de Mo que prioriza deleções ou o estado de "rollback" para manter a complexidade sob controle. ```

#include #include #include #include

using namespace std;

struct Consulta { int esq, dir, id; };

const int MAXN = 200005; int dados[MAXN], freq[MAXN], resultado[MAXN]; int tamanho_bloco;

bool compararConsultas(const Consulta& a, const Consulta& b) { int bloco_a = a.esq / tamanho_bloco; int bloco_b = b.esq / tamanho_bloco; if (bloco_a != bloco_b) return bloco_a < bloco_b; return a.dir > b.dir; }

int calcularMexBruto(int l, int r) { vector temp_freq(MAXN, 0); for (int i = l; i <= r; i++) { if (dados[i] < MAXN) temp_freq[dados[i]]++; } for (int i = 0; ; i++) { if (temp_freq[i] == 0) return i; } }

int main() { ios::sync_with_stdio(false); cin.tie(nullptr);

int n, m;
cin >> n >> m;
tamanho_bloco = sqrt(n);

for (int i = 1; i <= n; i++) cin >> dados[i];

vector<Consulta> consultas(m);
for (int i = 0; i < m; i++) {
    cin >> consultas[i].esq >> consultas[i].dir;
    consultas[i].id = i;
}

sort(consultas.begin(), consultas.end(), compararConsultas);

// Lógica simplificada de processamento por blocos
// Em uma implementação de produção, utilizaria-se ponteiros de Mo
// para ajustar os intervalos [L, R] minimizando o movimento.

// ... (processamento do Algoritmo de Mo)

return 0;

}

### Sequências de Potências e Padrões Binários

Muitas vezes, sequências complexas podem ser reduzidas a representações binárias. Considere um problema onde uma sequência é formada pela combinação de potências de base $k$. Observando a formação dos índices: $\\{0\\}$, $\\{1\\}$, $\\{0, 1\\}$, $\\{2\\}$, $\\{0, 2\\}$, $\\{1, 2\\}$, $\\{0, 1, 2\\} \\dots$, percebe-se que os expoentes presentes no $p$-ésimo termo correspondem às posições dos bits definidos (1) na representação binária de $p$. Para clacular o $p$-ésimo termo da sequência para uma base $k$, podemos iterar sobre os bits de $p$ e somar $k^i$ para cada bit $i$ ativo. Como o resultado pode exceder o limite de 64 bits, o uso de `__int128` é recomendado. ```

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

typedef __int128 int128;

void imprimir128(int128 n) {
    if (n == 0) { cout << "0"; return; }
    string s = "";
    while (n > 0) {
        s += (char)((n % 10) + '0');
        n /= 10;
    }
    reverse(s.begin(), s.end());
    cout << s;
}

int128 potencia(int base, int exp) {
    int128 res = 1;
    for (int i = 0; i < exp; i++) res *= base;
    return res;
}

int main() {
    long long k, p;
    cin >> k >> p;

    int128 total = 0;
    for (int i = 0; i < 60; i++) {
        if ((p >> i) & 1) {
            total += potencia(k, i);
        }
    }
    
    imprimir128(total);
    cout << endl;
    return 0;
}

Expansão Decimal de Frações

O cálculo de dígitos específicos em uma expansão decimal (como a fração $10/89$) pode ser realizado simulando o algoritmo de divisão manual. Para encontrar os dígitos entre as posições $M$ e $N$, aplicamos o operador de resto para saltar as primeiras $M$ posições e, em seguida, extraímos os quocientes sucessivos. ```

#include

int main() { int m, n; if (!(std::cin >> m >> n)) return 0;

int numerador = 10;
int denominador = 89;

// Ignorar casas decimais anteriores à posição M
for (int i = 1; i < m; i++) {
    numerador %= denominador;
    numerador *= 10;
}

// Extrair e imprimir dígitos de M até N
for (int i = m; i <= n; i++) {
    numerador %= denominador;
    numerador *= 10;
    std::cout << (numerador / denominador);
}
std::cout << std::endl;

return 0;

}