Szczegółowe omówienie zadania Brylanty z kosmosu:
Link do powyższego omówienia zadania Brylanty z kosmosu:
https://youtu.be/0ri7j0X_Oqo?t=1649
Link do treści zadania Brylanty z kosmosu oraz możliwości umieszczania rozwiązań:
https://szkopul.edu.pl/problemset/problem/bzk/site/
–
Zadanie Brylanty z kosmosu jest szkoleniowym zadaniem pokazującym drzewa przedział-przedział:
https://youtu.be/hHNjFBxNO54?t=2197
Drzewa przedziałowe to sumy prefiksowe z mała obserwacją:
https://youtu.be/hHNjFBxNO54?t=2159
Wszystko jesteśmy w stanie udoskonalić:
https://youtu.be/hHNjFBxNO54?t=29
–
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625
–
Kod C++ programu Brylanty z kosmosu, który jest omówiony w powyższym filmie i który otrzymuje 100%
–
#include <iostream>
#include <vector>
std::vector<int> suma_na_przedziale;
std::vector<int> nie_zaktualizowane_wartosci_synow;
int ZnajdzNajblizszaWiekszaPotegeDwojki (int liczba) {
int najblizsza_potega_dwojki;
najblizsza_potega_dwojki = 1;
while (najblizsza_potega_dwojki < liczba)
najblizsza_potega_dwojki <<= 1;
return najblizsza_potega_dwojki;
}
void PrzekazNiezaktualizowaneWartosciSynom (int wierzcholek) {
int syn_lewy, syn_prawy;
syn_lewy = 2*wierzcholek;
syn_prawy = 2*wierzcholek + 1;
suma_na_przedziale[syn_lewy] += nie_zaktualizowane_wartosci_synow[wierzcholek];
suma_na_przedziale[syn_prawy] += nie_zaktualizowane_wartosci_synow[wierzcholek];
nie_zaktualizowane_wartosci_synow[syn_lewy] += nie_zaktualizowane_wartosci_synow[wierzcholek]/2;
nie_zaktualizowane_wartosci_synow[syn_prawy] += nie_zaktualizowane_wartosci_synow[wierzcholek]/2;
nie_zaktualizowane_wartosci_synow[wierzcholek] = 0;
}
void DodajWartoscNaPrzedzialeWDrzewie (int wartosc, int poczatek_podanego_przedzialu, int koniec_podanego_przedzialu,
int wierzcholek, int poczatek_zakresu_wierzcholka, int koniec_zakresu_wierzcholka) {
int srodek, suma;
//jesli mamy doda cos na przedziale za ktry nasz wierzchoek NIE odpowiada - chocby czciowo - wychodzimy
if ( koniec_podanego_przedzialu < poczatek_zakresu_wierzcholka)
return;
if ( poczatek_podanego_przedzialu > koniec_zakresu_wierzcholka)
return;
//jesli mamy doda cos na takim przedziale, w ktrym zakres naszego wierzchoka mieci si w caoci
//to aktulizujemy sum za ktra odpowiada nasz wierzchoek
//nie aktulizujemy naszych dzieci - zrobimy to w przyzoci gdy bdzie trzeba na podstawie
//tablicy nie_zaktualizowane_wartosci_synow
if ( (poczatek_zakresu_wierzcholka >= poczatek_podanego_przedzialu) &&
(koniec_zakresu_wierzcholka <= koniec_podanego_przedzialu) ) {
suma = wartosc * (koniec_zakresu_wierzcholka - poczatek_zakresu_wierzcholka + 1);
suma_na_przedziale[wierzcholek] += suma;
nie_zaktualizowane_wartosci_synow[wierzcholek] += suma/2;
return;
}
//jesli nasz przedzia zawiera fagment czsciowo zakres na ktrym dodajemy
//ale te przedzia spoza aktulizowanego zakresu
//to aktualizujemy synw z wczeniejszych pytan (nie_zaktualizowane_wartosci_synow)
//oraz przekazujemy im aktualny rozkaz
//nastepnie aktulizujemy nasz sum
PrzekazNiezaktualizowaneWartosciSynom (wierzcholek);
srodek = (poczatek_zakresu_wierzcholka + koniec_zakresu_wierzcholka) / 2;
DodajWartoscNaPrzedzialeWDrzewie (wartosc, poczatek_podanego_przedzialu, koniec_podanego_przedzialu,
2*wierzcholek, poczatek_zakresu_wierzcholka, srodek);
DodajWartoscNaPrzedzialeWDrzewie (wartosc, poczatek_podanego_przedzialu, koniec_podanego_przedzialu,
2*wierzcholek+1, srodek+1, koniec_zakresu_wierzcholka);
suma_na_przedziale[wierzcholek] = suma_na_przedziale[2*wierzcholek] + suma_na_przedziale[2*wierzcholek+1];
}
int ObliczSumePrzedzialuWDrzewie (int poczatek_podanego_przedzialu, int koniec_podanego_przedzialu,
int wierzcholek, int poczatek_zakresu_wierzcholka, int koniec_zakresu_wierzcholka) {
int suma_przedzialu_syna_lewego, suma_przedzialu_syna_prawego;
int srodek;
//jeli pytanie spoza zakresu wierzchoka to zwracamy 0 - suma ktr dokada ten wierzchoek do wyniku jest 0
if ( koniec_podanego_przedzialu < poczatek_zakresu_wierzcholka )
return 0;
if ( poczatek_podanego_przedzialu > koniec_zakresu_wierzcholka )
return 0;
//jeli nasz wierzchoek w caoci zawiera si w pytanym zakresie to nasz wierzchoek dokada si do sumy w caoci
//zwracamy sum ktr przechowuje nasz wierzchoek
if ( (poczatek_zakresu_wierzcholka >= poczatek_podanego_przedzialu) &&
(koniec_zakresu_wierzcholka <= koniec_podanego_przedzialu) ) {
return suma_na_przedziale[wierzcholek];
}
//jeli nasz wierzchoek zawiera co z pytanego zakresu ale te co spoza pytanego zakresu to nie moemy od razu odpowiedzie
//pytamy synw i zwracamy sum ich odpowiedzi
//ale najpierw aktualizujemy ich wartoci wczeniejszymi zapytaniami na ktre nie musieli odpowiada
PrzekazNiezaktualizowaneWartosciSynom (wierzcholek);
srodek = (poczatek_zakresu_wierzcholka + koniec_zakresu_wierzcholka) / 2;
suma_przedzialu_syna_lewego = ObliczSumePrzedzialuWDrzewie (poczatek_podanego_przedzialu, koniec_podanego_przedzialu,
2*wierzcholek, poczatek_zakresu_wierzcholka, srodek);
suma_przedzialu_syna_prawego = ObliczSumePrzedzialuWDrzewie (poczatek_podanego_przedzialu, koniec_podanego_przedzialu,
2*wierzcholek+1, srodek+1, koniec_zakresu_wierzcholka);
return suma_przedzialu_syna_lewego + suma_przedzialu_syna_prawego;
}
int main (){
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
int ile_pracownikow, ile_operacji;
char operacja;
int liczba_przechowywanych_elementow, rozmiar_drzewa;
int poczatek, koniec, wartosc;
int i;
std::cin >> ile_pracownikow >> ile_operacji;
//drzewo musi przechowywa elementy bdce potg dwjki
//rozmiar drzewa jest dwa razy wikszy od iloci przechowywanych elementw
liczba_przechowywanych_elementow = ZnajdzNajblizszaWiekszaPotegeDwojki (ile_pracownikow);
rozmiar_drzewa = 2 * liczba_przechowywanych_elementow;
suma_na_przedziale.resize(rozmiar_drzewa, 0);
nie_zaktualizowane_wartosci_synow.resize(rozmiar_drzewa, 0);
for (i=1; i<=ile_operacji; ++i) {
std::cin >> operacja >> poczatek >> koniec;
if ( operacja == 'P') {
std::cout << ObliczSumePrzedzialuWDrzewie (poczatek-1, koniec-1, 1, 0, liczba_przechowywanych_elementow-1) << "\n";
continue;
}
std::cin >> wartosc;
DodajWartoscNaPrzedzialeWDrzewie (wartosc, poczatek-1, koniec-1, 1, 0, liczba_przechowywanych_elementow-1);
}
return 0;
}