Created
December 1, 2021 23:46
-
-
Save PedroRacchetti/f699e65e3fc9c6a46ce93e806a3c3fed to your computer and use it in GitHub Desktop.
This file contains 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
// Os parametros da função unlazy são: | |
// O nó atual, tl e tr, o intervalo que o nó atual abrange, | |
void unlazy(int node, int tl, int tr){ | |
// Se não houver valor a ser propagado, não precisamos propagar | |
if(lz[node] == 0) return; | |
// Primeiro, atualizamos a árvore com o novo valor | |
tree[node] = lz[node]; | |
// Se houver filhos, propagamos o vaor para eles | |
if(tl != tr){ | |
lz[2*node+1] = lz[node]; | |
lz[2*node+2] = lz[node]; | |
} | |
// Indicamos que não há mais valores a serem propagados em node | |
lz[node] = 0; | |
} | |
// Os parametros da função Update são: | |
// O nó atual, tl e tr, o intervalo que o nó atual abrange, l e r, o intervalo que está sendo atualizado | |
// e x, o o valor a ser atualizado. | |
void update(int node, int tl, int tr, int l, int r, int v){ | |
//LEMBRE-SE: Sempre chame a unlazy quando entrar numa função de update | |
unlazy(node, tl, tr) | |
// Se o intervalo abrangido pelo nó atual estiver completamente fora do intervalo a ser atualizado, | |
// não temos que atualizá-lo. | |
if(tl > r || tr < l) return; | |
// Se o intervalo abrangido pelo nó estiver inteiramente contido no intervalo atualizado, | |
// atualizaremos o nó. | |
if(tl >= l && tr <= r){ | |
lz[node] = x; | |
unlazy(node, tl, tr); | |
return; | |
} | |
// Caso contrário, declararemos mid como o índice que divide o nó atual em duas metades. | |
int mid = (tl+tr)/2; | |
//Agora, atualizaremos os filhos. | |
update(2*node+1,tl,mid,l, r ,v); | |
update(2*node+2,mid+1,tr,l,r,v); | |
// Após termos atualizado os dois filhos, atualizaremos o valor do nó atual. | |
tree[node] = max(tree[2*node + 1], tree[2*node + 2]); | |
} | |
// Os parametros da função Query são: | |
// O nó atual, tl e tr, o intervalo que o nó atual abrange, l e r, o intervalo que queremos calcular. | |
int query(int node, int tl, int tr, int l, int r){ | |
//LEMBRE-SE: Sempre chame a unlazy quando entrar numa função de query | |
unlazy(node, tl, tr) | |
// Se o intervalo que o nó atual abrange estiver totalmente fora do intervalo de l até r, retornaremos 0. | |
// Então, ou o início do intervalo do nó atual é maior que o fim dp intervalo que queremos calcular, ou | |
// o fim do intervalo do nó atual é menor que o início do intervalo que queremos calcular. | |
if(r<tl or l>tr) return 0; | |
// Se o intervalo que o nó atual representa estiver totalmente dentro do intervalo de l até r, então | |
// retornaremos o valor do nó atual. | |
if(l<=tl and r>=tr) return tree[node]; | |
// Caso contrário, declararemos mid como o índice que divide o nó atual em duas metades. | |
int mid = (tl+tr)>>1; | |
// Retornamos como resposta o máximo da resposta dos filhos do nó atual. | |
return max(query(2*node+1, tl, mid, l, r),query(2*node+2, mid+1, tr, l, r)); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment