Solução Informática Avançado - Semana 70

Solução por Samyra Almeida

Conhecimentos prévios necessários:

Dividiremos o vetor em \sqrt{N} blocos de tamanho \sqrt{N}. Com isso chamaremos de qtd[i] é o igual a quantidade de pulos do buraco i até a primeira posição fora do bloco de i, ultimo[i] é a ultima posição, do mesmo bloco de i, que a bola pula se fosse jogada na posição i, prox[i] é a próxima posição que a bola pula se for jogada na posição i e o vetor v[] guarda o poder de cada buraco.

Antes de lermos os queries, iremos montar os vetores. Para o i-ésimo buraco iremos fazer:

Vamos percorrer todos os buracos j que estão entre i e o inicio de seu bloco, a partir dai iremos anualizar três possíveis casos:

Para evitar possíveis duvidas, v[j] = poder do buraco j e j é o buraco que eu estou, logo v[j] + j a posição que eu irei após cair no j-ésimo buraco. Com isso, vamos analisar os casos =D!

  1. Caso v[j] + j > n: Nesse caso a bola irá sair do vetor. Portanto:
    • qtd[j] = 1
    • ultimo[j] = j
    • prox[j] = v[j] + j
  2. Caso v[j] + j < fim, sendo fim = final do bloco de j + 1: Nesse caso a bola irá sair do vetor. Portanto:
    • qtd[j] = qtd[v[j] + j] + 1, a quantidade de pulos que v[j] + j leva até o final do bloco mais 1, ou seja, meu pulo até v[j] + j.
    • ultimo[j] = ultimo[v[j] + j], ultima posição que j pula dentro do bloco é a mesma de v[j] + j
    • prox[j] = v[j] + j, a próxima posição é v[j] + j
  3. Caso v[j] + j está entre fim e n: Nesse caso o próximo pulo será para fora do bloco de j, então faremos:
    • qtd[j] = 1
    • ultimo[j] = j
    • prox[j] = v[j] + j

Bem, após tudo isso, iremos ler e processar as queries:

Para as queries do tipo 0 a b, perceba que só precisamos atualizar o bloco em a pertence pois como nós só calculamos a quantidade de pulos necessários para sair de um buraco até o final de seu bloco a alteração na potencia do a-ésimo buraco só interfere no seu próprio bloco. Para isso, iremos fazer as mesmas operações que fizemos para construir os vetores, qtd[], ultimo[] e prox[], porem, somente para os buracos de a até o inicio de seu bloco.

E para as queries do tipo 1 a iremos criar duas variáveis, pulos, que no inicio é0, e x, que no inicio é a, e faremos um while(true) onde para cada iteração faremos:

  • pulos += qtd[x], somamos a quantidade de pulos ate sair do bloco que x está.
  • x = ultimo[x], atualizamos a ultima posição.
  • Checamos se prox[x] > n, ou seja, se o próximo pulo sai do vetor, se sim, paramos o loop, se não, fazemos pulamos para a próxima posição.

Ao final do loop, basta imprimir x e pulos.

Segue o código solução para maior compressão:


// NOIC - Problemas da Semana 69 - Intermediário
// Solução por Samyra Almeida
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10, root = 340; // declaro maxn e root como constantes,
// observe que coloquei o root como 340 pq por alguma razao fica um pouquinho mais rapido quando n e no maximo 10^5
// nos testamos em alguns juizes e ficou mais rapido, mas se quiser usar como 320 fique a vontade.
int n, m;
int v[maxn], qtd[maxn], ultimo[maxn], prox[maxn]; // declaro as variaveis e vetores que irei precisar
void build()
{
for(int i = n ; i > 0 ; --i) // passo por todas as posiçoes do vetor, ou seja, por todos os buracos
{
int ini, fim;
ini = i/root;
fim = ini + 1;
ini *= root, fim *= root; // calculo a primeira e a ultima posicao do bloco que i pertence
// OBS: pode ficar um pouco confuso mas tente observar que na verdade a variavel fim guarda
// a primeira posicao do proximo bloco, ou seja, o bloco de i abrange as posiçoes de ini ate fim - 1.
for(int j = i ; j >= max(ini, 1) ; --j) // percorro da posiçao i ate o inicio do bloco de i
{
if(v[j] + j > n) // se o proximo pulo sai do vetor
{
qtd[j] = 1; // a quantidade de pulos para sair do vetor e 1
ultimo[j] = j; // a ultima posiçao que eu pulei dentro do meu bloco foi a posiçao j
}
else if(v[j] + j < fim) // se o proximo pulo e dentro o meu bloco, seria a mesma coisa de testar v[j] + j <= fim - 1
{
qtd[j] = qtd[j + v[j]] + 1; // a quantidade de pulos ate o final do bloco e igual a quantidade de pulos que o meu proximo cara deu ate o final do bloco mais 1 (meu pulo ate v[j] + j)
ultimo[j] = ultimo[j + v[j]]; // o ultimo de j e o mesmo que o de v[j] + j
}
else // se o meu proximo pulo for em alguma outra posiçao, ainda dentro do vetor mas fora do meu bloco
{
qtd[j] = 1; // a quantidade de pulos para sair do vetor e 1
ultimo[j] = j; // a ultima posiçao que eu pulei dentro do meu bloco foi a posiçao j
}
prox[j] = j + v[j]; // atualizo a posiçao do proximo pulo de j
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
for(int i = 1 ; i <= n ; ++i) cin >> v[i];
build(); // monto os vetores qtd, ultimo e prox.
for(int i = 0 ; i < m ; ++i) // processo todas as queries
{
int type, a;
cin >> type >> a;
if(type) // se for do tipo 1
{
int pulos = 0, x = a; // no inicio nao dei nenhum pulo e estou na posiçao a
while(true) // enquanto eu preciso pular de bloco
{
pulos += qtd[x]; // somo a pulos a quantidade de pulos para sair da posicao x ate a ultima posiçao que eu vou pular em meu bloco
x = ultimo[x]; // pulo ate a ultima posiçao que eu consigo em meu bloco
if(prox[x] > n) break; // se o proximo pulo for sair do vetor, paro o loop
x = prox[x]; // caso contrario, pulo para a proxima posicao
}
cout << x << " " << pulos << "\n"; // imprimo a resposta
}
else // se a query for do tipo 0
{
int b;
cin >> b;
v[a] = b; // atualizo a potencia do buraco a
int ini, fim;
ini = a/root;
fim = ini + 1;
ini *= root, fim *= root; // calculo a primeira e a ultima posicao do bloco que a pertence
// OBS: pode ficar um pouco confuso mas tente observar que na verdade a variavel fim guarda
//a primeira posicao do proximo bloco, ou seja, o bloco de a abrange as posiçoes de ini ate fim - 1.
for(int j = a ; j >= max(ini, 1) ; --j) // percorro o bloco da posiçao a ate o inicio do bloco
{
if(v[j] + j > n) // se o proximo pulo sai do vetor
{
qtd[j] = 1; // a quantidade de pulos para sair do vetor e 1
ultimo[j] = j; // a ultima posiçao que eu pulei dentro do meu bloco foi a posiçao j
}
else if(v[j] + j < fim) // se o proximo pulo e dentro o meu bloco, seria a mesma coisa de testar v[j] + j <= fim - 1
{
qtd[j] = qtd[j + v[j]] + 1; // a quantidade de pulos ate o final do bloco e igual a quantidade de pulos que o meu proximo cara deu ate o final do bloco mais 1 (meu pulo ate v[j] + j)
ultimo[j] = ultimo[j + v[j]]; // o ultimo de j e o mesmo que o de v[j] + j
}
else // se o meu proximo pulo for em alguma outra posiçao, ainda dentro do vetor mas fora do meu bloco
{
qtd[j] = 1; // a quantidade de pulos para sair do vetor e 1
ultimo[j] = j; // a ultima posiçao que eu pulei dentro do meu bloco foi a posiçao j
}
prox[j] = j + v[j]; // atualizo o proximo cara que eu irei pular.
}
}
}
}