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:
https://gist.github.com/samyravitoria/8e6297afdbbc941de1cee7d5daea8e76