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:
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
| // 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. | |
| } | |
| } | |
| } | |
| } |