Solução Informática - Nível Intermediário - Semana 20

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:

	#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
	}

view raw

Light Experiments.cpp

hosted with ❤ by GitHub