Segredo do Cofre

cofre.cpp

// Segredo do Cofre - F1P1 - OBI 2017
// Rogério Júnior
// O(N+M)

#include <cstdio> // scanf e printf
#include <algorithm> // min e max

using namespace std;

#define MAXN 100100 // defino o valor de MAXN

// declaro, respectivamente, N, M, e vetor que representa a barra
// e o vetor de frequência das posições
int n, m, v[MAXN], f[MAXN];

// declaro o vaetor que guardará a frequência final de cada dígito
long long dig[10];

// função upd 
void upd(int l, int r, int d){
  
  f[l]+=d;
  f[r+1]-=d;
}

int main(){
  
  //leio os valores de N e M
  scanf("%d %d", &n, &m);
  
  // leio os valores em cada posição da barra
  for(int i=1;i<=n;i++) scanf("%d", &v[i]);
  
  // declaro last, que começa com valor 1
  int last=1;
  
  // adiciono 1 à frequência da primeira posição
  upd(1,1,1);
  
  // em cada operação
  for(int i=1;i<=m;i++){
    
    // leio a posição para onde o controle deve ir
    int next;
    scanf("%d", &next);
    
    // defino os valores de L e R
    int l=min(last,next), r=max(last,next);
    
    // uso upd para adicionar 1 à frequência de todas as posições entre L e R
    upd(l,r,1);
    
    // e depois retiro uma unidade da frequência da posição last
    upd(last,last,-1);
    
    // atualizo o novo valor de last para a próxima operação
    last=next;
  }
  
  // para cada posição da barra
  for(int i=1;i<=n;i++){
    
    // descubro sua frequência adicionando a ela a soma
    // das frequêncas de todas as casas anteriores
    // ela ordem das operações, f[i-1] já guarda essa soma,
    // logo basta adicionar seu valor a f[i], que agora 
    // também guardará toda a soma do prefixo que acaba nele
    // e será usada para definir essa soma para i+1
    f[i]+=f[i-1];
    
    // e adiciono a frequência da posição no dígito que ela guarda
    dig[v[i]]+=f[i];
  }
  
  // por fim, basta imprimir a frequência de cada dígito
  for(int i=0;i<10;i++) printf("%d ", dig[i]);
  
  printf("\n");
  
  return 0;
}