Solução por Anita Ramos
Esse é um típico problema em que é necessário ter uma ideia sólida antes de programar e iniciar os testes. Essa ideia é bem simples, mas pode gerar uma certa confusão para conseguir “cobrir” todas as possibilidades.
A ideia consiste em já determinar o número de intervalos de cada número existentes na faixa logo na leitura inicial desta e, posteriormente, a cada pergunta em que $$num=1$$ atualizamos o número de intervalos de cada valor. O primeiro processo citado é simples, bastando comparar o valor da casinha lido com o valor da casinha anterior. O segundo é o que pode gerar uma certa confusão e uma dificuldade em esclarecer as possibilidades e, por isso, irei dividir em 4 opções, sendo que a escolha de uma opção não impede a escolha de outra, ou seja, mais de uma opção pode ser verdadeira, sendo assim, as duas serão executadas em ordem:
- Se os dois vizinhos da casinha $$X$$ forem iguais à $$C$$, subtrai-se 1 na quantidade de intervalos de valor igual a $$C$$, pois teremos a união de dois intervalos distintos -> a direita de $$X$$ e a esquerda de $$X$$ (não consideramos o valor da casinha $$X$$, pois ele será analisado depois);
- Se os dois vizinhos da casinha $$X$$ forem diferentes de $$C$$, soma-se 1 na quantidade de intervalos de valor igual a $$C$$, pois teremos a criação de um novo intervalo de um número “isolado” (diferente dos vizinhos);
- Se os dois vizinhos da casinha $$X$$ têm valores iguais ao valor ATUAL (sem alteração ainda) da casinha $$X$$, soma-se 1 na quantidade de intervalos de valor igual ao valor ATUAL da casinha $$X$$, pois teremos a separação de 1 intervalo em dois intervalos (desconsiderando o novo valor $$C$$ da casinha $$X$$);
- Se os dois vizinhos da casinha $$X$$ têm valores diferentes do valor ATUAL (sem alteração ainda) da casinha $$X$$, subtrai-se 1 na quantidade de intervalos de valor igual ao valor ATUAL da casinha $$X$$, pois teremos que o intervalo desse número isolado da casinha $$X$$ sumirá ao trocarmos seu valor.
Assim, o truque está em considerar o que ocorrerá inicialmente (casos 1 e 2 acima) independente do valor ATUAL da casinha $$X$$, pois basta considerar ambos os casos posteriormente (casos 3 e 4). Depois de uma pergunta com $$num=1$$, não podemos esquecer de, ao final, atualizar o valor da casinha $$X$$ ($$v[X] = C$$).
O terceiro e último processo é se $$num=2$$, em que imprimimos o valor de $$marc[C]$$ (número de intervalos da cor/número $$C$$).
Segue o código comentado para melhor compreensão da solução:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> //biblioteca utilizada | |
| using namespace std; | |
| const int MAXN=10000000; //define MAXN como 10000000 | |
| int marc[MAXN]; //declaro um vetor de marcação de tamanho 'MAXN' | |
| int main() | |
| { | |
| int N,Q,X,C,num; //declaração de variáveis | |
| scanf("%d %d", &N, &Q); //leitura da 1º linha de entrada | |
| int v[N+1]; //declaro um vetor de tamanho 'N'+1 | |
| for(int i=1; i<=N; i++) //loop para ler toda a fita | |
| { | |
| scanf("%d", &v[i]); //leitura dos valores da fita | |
| if(v[i-1]!=v[i])marc[v[i]]++; //se o valor casinha da fita atual é diferente do valor da anterior, soma-se 1 ao vetor de marcação dessa cor (valor da casinha) | |
| } | |
| for(int i=1; i<=Q; i++) //loop para ler todas as "perguntas" | |
| { | |
| scanf("%d", &num); //lê o 1º número da pergunta (1 ou 2) | |
| if(num==1) //se for 1 | |
| { | |
| scanf("%d %d", &X, &C); //lê 'X' e 'C' | |
| if(v[X+1]==C && v[X-1]==C)marc[C]–; //se os dois vizinhos da casinha 'X' são iguais a 'C', subtrai 1 na qntd de intervalos de 'C' (união de dois intervalos distintos) | |
| if(v[X+1]!=C && v[X-1]!=C)marc[C]++; //se os dois vizinhos da casinha 'X' são diferentes de 'C', soma 1 na qntd de intervalos de 'C' (número isolado = novo intervalo) | |
| if(v[X+1]==v[X] && v[X-1]==v[X])marc[v[X]]++; //se os dois vizinhos da casinha 'X' são iguais à casinha 'X', soma 1 na qntd de intervalos do valor da casinha 'X' (separação de um intervalo contínuo = 2 intervalos separados) | |
| else if(v[X+1]!=v[X] && v[X-1]!=v[X])marc[v[X]]–; //se os dois vizinhos da casinha 'X' são diferentes da casinha 'X', subtrai 1 na qntd de intervalos do valor da casinha 'X' (intervalo de um número isolado = intervalo some) | |
| v[X]=C; //casinha 'X' assume o valor de 'C' | |
| } | |
| else if(num==2) //se for 2 | |
| { | |
| scanf("%d", &C); //lê o 'C' | |
| printf("%d\n", marc[C]); //imprime a resposta para essa cor/número | |
| } | |
| } | |
| return 0; //retorna a 0 | |
| } |