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!
- 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$$
- 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$$
- 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. | |
| } | |
| } | |
| } | |
| } |
