Análise do Problema de Mineração (Mine)

Este problema exige calcular o número de maneiras válidas para preencher uma sequência linear onde cada posição indica informações sobre bombas adjacentes. A abordagem utiliza Programação Dinâmica (DP). Definimos o estado como dp[indices][valor_atual][valor_previo], representando até qual posição da sequência chegamos, qual é o estado atual da célula e qual foi o estado da célula imediatamente anterior.

Os valores das células variam de 0 a 3, indicando quantas bombas vizinhas existem, ou são classificados como bomba. É necessário realizar uma verificação rigorosa das transições para garantir que as restrições de vizinhença sejam respeitadas. O algoritmo deve lidar com entradas genéricas onde certos caracteres representam dígitos fixos ou placeholders incertos.

#include <bits/stdc++.h>
using namespace std;

const int TAM_MAX = 1000005;
const long long MODULO = 1e9 + 7;
char entrada[TAM_MAX];
int configuracao[TAM_MAX];
long long memo[TAM_MAX][5][5]; 
int tamanho_str;

// Normaliza o valor módulo MODULO
inline void ajustar_modulo(long long &val) {
    if(val >= MODULO) val -= MODULO;
}

bool eh_bomba(int idx) {
    return (configuracao[idx] == 3 || configuracao[idx] == 4);
}

// Validação inicial da string para consistência básica
bool verificar_validade() {
    for (int i = 1; i <= tamanho_str; ++i) {
        if (configuracao[i] == 4) continue; // Pulo se for '?'
        
        // Regras de lógica para minas baseadas nas pistas numéricas
        if (configuracao[i] == 1) {
            bool esquerda = (i > 1 && eh_bomba(i-1));
            bool direita = (i < tamanho_str && eh_bomba(i+1));
            if (!(esquerda ^ direita)) return false; // Deve ter exatamente uma vizinha bomba
        } else if (configuracao[i] == 2) {
             if (!eh_bomba(i-1) || !eh_bomba(i+1)) return false;
        }
    }
    return true;
}

int main() {
    scanf("%s", entrada + 1);
    tamanho_str = strlen(entrada + 1);

    // Conversão de caracteres para valores inteiros
    for (int i = 1; i <= tamanho_str; ++i) {
        if (entrada[i] == '0') configuracao[i] = 0;
        else if (entrada[i] == '1') configuracao[i] = 1;
        else if (entrada[i] == '2') configuracao[i] = 2;
        else if (entrada[i] == '*') configuracao[i] = 3;
        else if (entrada[i] == '?') configuracao[i] = 4;
    }

    if (tamanho_str == 1) {
        if (configuracao[1] == 0 || configuracao[1] == 3) cout << 1 << endl;
        else cout << 0 << endl;
        return 0;
    }

    if (!verificar_validade()) {
        cout << 0 << endl;
        return 0;
    }

    // Inicialização do DP para a primeira posição
    memset(memo, 0, sizeof(memo));
    if (configuracao[1] != 4) {
        if (configuracao[1] == 0) memo[1][0][0] = 1;
        else if (configuracao[1] == 1) memo[1][1][0] = 1;
        else if (configuracao[1] == 3) memo[1][3][0] = 1;
    } else {
        memo[1][0][0] = memo[1][1][0] = memo[1][3][0] = 1;
    }

    // Transições de estado DP
    for (int i = 2; i <= tamanho_str; ++i) {
        for (int curr = 0; curr <= 3; ++curr) {
            if (configuracao[i] != 4 && configuracao[i] != curr) continue;

            for (int prev = 0; prev <= 3; ++prev) {
                // Lógica de transição baseada na compatibilidade entre células adjacentes
                // Exemplo simplificado de combinação de estados anteriores e atuais
                if (curr == 0) {
                     if (prev == 0 || prev == 1) // Dependendo da configuração exata
                         ajuste...
                }
                // ... (A lógica completa envolve múltiplas condições de vizinhança)
                // Adicione transições apropriadas aqui mantendo a complexidade O(N)
            }
        }
    }
    
    // Soma final das configurações válidas
    // Este bloco seria expandido para cobrir todas as combinações finais possíveis
    // Baseado no código original, a soma considera as restrições do último elemento
    
    return 0;
}

Lógica de Fluxo de Água (Water)

Para determinar o nível de água em cada bloco de uma grade retangular, precisamos encontrar o caminho de saída com o menor "custo máximo". O custo de um caminho é definido pela altura máxima encontrada nele. O nível final é igual à altura inicial mais a profundidade da água acumulada. Isso se traduz em um problema de caminho mínimo onde a função de ponderação não é aditiva, mas sim baseada no máximo (max(dist, peso_aresta)).

Construímos um grafo onde cada célula é um nó conectado aos seus quatro vizinhos. Nós adicionais conectam todos os blocos da borda a um nó fonte virtual. Executamos o algoritmo de Dijkstra a partir dese nó fonte para calcular o limite mínimo de saída para cada coordenada.

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include >algorithm>
using namespace std;

const int MAX_N = 305;
const int INF = 0x3f3f3f3f;

struct Aresta {
    int destino;
    int peso;
};

int n_linhas, m_colunas;
int alturas[MAX_N][MAX_N];
int nivel_minimo[MAX_N][MAX_N];
bool visitado[MAX_N][MAX_N];
int deltas_x[] = {0, 1, 0, -1};
int deltas_y[] = {1, 0, -1, 0};
int fonte_virtual_id = MAX_N * MAX_N;

// Estrutura para a fila de prioridade do Dijkstra
struct Estado {
    int custo;
    int id_no;
    
    bool operator>(const Estado& outro) const {
        return custo > outro.custo;
    }
};

void executar_dijkstra() {
    memset(nivel_minimo, 0x3f, sizeof(nivel_minimo));
    priority_queue<Estado> pq;
    
    // Conectar fonte virtual às bordas
    for(int i=1; i<=n_linhas; ++i){
        for(int j=1; j<=m_colunas; ++j){
            if(i==1 || i==n_linhas || j==1 || j==m_colunas){
                // Custo é o máximo entre a altura atual e a do vizinho (ou zero)
                int custo = alturas[i][j]; 
                if(nivel_minimo[i][j] > custo){
                    nivel_minimo[i][j] = custo;
                    pq.push({-nivel_minimo[i][j], i*m_colunas+j}); // Negativo para min-heap
                }
            }
        }
    }

    while(!pq.empty()){
        Estado atual = pq.top();
        pq.pop();
        
        int id = atual.id_no;
        int x = (id-1)/m_colunas + 1;
        int y = (id-1)%m_colunas + 1;
        
        if(visitado[x][y]) continue;
        visitado[x][y] = true;

        for(int k=0; k<4; ++k){
            int nx = x + deltas_x[k];
            int ny = y + deltas_y[k];

            if(nx > 0 && nx <= n_linhas && ny > 0 && ny <= m_colunas){
                // Peso da aresta é o máximo das alturas dos dois blocos
                int nova_altura = max(alturas[x][y], alturas[nx][ny]);
                if(nivel_minimo[nx][ny] > nova_altura){ // Lógica modificada para minimax
                    // Revisão: A distância aqui representa o pico máximo no caminho
                    // Corrigindo a lógica de relaxamento padrão para minimax path
                    // O código original usa dist[y] > max(dist[x], len[i])
                    // Aqui adaptando para a estrutura de matriz
                }
            }
        }
    }
}
// A implementação completa requer cuidadosa adaptação da lógica de maximização dentro do relaxamento

Contagem de Divisores Comuns (GCD)

O desafio consiste em manter dinamicamente o número de pares de elementos seleiconados cujo Máximo Divisor Comum (MDC) seja exatamente 1. Para resolver isso eficientemente durante as operações de atualização, aplicamos a Inversão de Möbius. Precisamos monitorar três métricas principais:

• S: Quantidade de números selecionados que são múltiplos de i.
• G: Pares selecionados onde ambos são múltiplos de i (calculado como C(S[i], 2)).
• F: Pares com MDC exatamente igual a i.

A relação fundamental é G[i] = Σ F[d] para todos d múltiplos de i. Usando a função de Möbius, podemos expressar F[1] (que desejamos maximizar) somando as contribuições de todos os múltiplos ponderadas por μ(d/i). Ao adicionar ou remover um número, iteramos sobre seus divisores para atualizar as contagens S e recalculamos a resposta global.

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

const int LIMITE_VALOR = 500005;
int mu[LIMITE_VALOR];
bool primo[LIMITE_VALOR];
vector<int> numeros_primos;
int contador_multiplos[LIMITE_VALOR];
bool ativo[LIMITE_VALOR];
int lista_valores[200005];
int quantidade_n, quantidade_operacoes;
long long resposta_atual = 0;

void precomputation_muepsilon() {
    mu[1] = 1;
    for (int i = 2; i < LIMITE_VALOR; i++) {
        if (!primo[i]) {
            numeros_primos.push_back(i);
            mu[i] = -1;
        }
        for (int p : numeros_primos) {
            if (i * p >= LIMITE_VALOR) break;
            primo[i * p] = true;
            if (i % p == 0) {
                mu[i * p] = 0;
                break;
            } else {
                mu[i * p] = -mu[i];
            }
        }
    }
}

void atualizar_resposta(int valor_idx, int operacao) {
    int valor = lista_valores[valor_idx];
    // Iterar sobre todos os fatores próprios de 'valor'
    for (int f = 1; f * f <= valor; f++) {
        if (valor % f == 0) {
            int fator1 = f;
            int fator2 = valor / f;
            
            // Atualizar contribuição para o primeiro fator
            if (ativo[valor_idx]) {
                 // Removendo do conjunto: subtrai impacto anterior
                 // Nota: Lógica simplificada para demonstração
                 resposta_atual -= 1LL * (contador_multiplos[fator1] - 1) * mu[fator1];
            } else {
                 // Adicionando ao conjunto: soma novo impacto
                 resposta_atual += 1LL * contador_multiplos[fator1] * mu[fator1];
            }
            contador_multiplos[fator1] += (ativo[valor_idx] ? -1 : 1);

            if (fator1 != fator2) {
                // Repetir para o segundo fator
                if (ativo[valor_idx]) {
                     resposta_atual -= 1LL * (contador_multiplos[fator2] - 1) * mu[fator2];
                } else {
                     resposta_atual += 1LL * contador_multiplos[fator2] * mu[fator2];
                }
                contador_multiplos[fator2] += (ativo[valor_idx] ? -1 : 1);
            }
        }
    }
    ativo[valor_idx] = !ativo[valor_idx];
}

int main() {
    scanf("%d %d", &quantidade_n, &quantidade_operacoes);
    precomputation_muepsilon();

    for (int i = 1; i <= quantidade_n; i++) {
        scanf("%d", &lista_valores[i]);
    }

    while (quantidade_operacoes--) {
        int op_idx;
        scanf("%d", &op_idx);
        atualizar_resposta(op_idx);
        printf("%lld\n", resposta_atual);
    }
    return 0;
}