Zacznijmy od tego, że jeżeli zmienna add jest ustawiona na 0, to na zapytanie
możemy odpowiadać jak w poprzednim zadaniu. Jeżeli nie jest, to przypominamy
sobie, że zapisaliśmy w niej, ile należy dodać do poddrzew. Pozbywamy się
problemu dodając tę wartość do poddrzew i zerując zmienną add.
dodaj( v, begin, val ) // dodaj val zaczynając od begin
if v.a = begin // wprowadzamy leniwość
v.add = v.add + val
v.min = v.min + val
v.max = v.max + val
return
if v.add != 0 // przenosimy leniwość o poziom w dół
dodaj( v.lewy, v.a, v.add )
dodaj( v.prawy, v.c+1, v.add )
v.add = 0
if begin >= v.c+1
dodaj( v.prawy, begin, val )
else
dodaj( v.lewy, begin, val )
dodaj( v.prawy, v.c+1, val )
v.min = min( v.lewy.min, v.prawy.min )
v.max = max( v.lewy.max, v.prawy.max )
v.val = max( v.prawy.max-v.lewy.min, v.lewy.val, c.prawy.val )
Czas działania
Policzmy czas działania - zapytanie bez zmian, modyfikacja też ,
wykonanie odwlekanych operacji wliczamy w koszt bieżącego zadania.
Praca domowa
Pokaż w jaki sposób można usunąć z drzewa pole add.
Aby sprawdzić poprawność rozwiązania, napisz procedurę
wylicz_add(v), która wyliczy brakujące pole
Pokaż w jaki sposób sobie radzić bez zerowania pola add.
Napisz procedurę zapytanie(v, p, k), która nie zmodyfikuje v
i wyliczy warość zapytania na przedziale [p,k].
Zmodyfikuj procedurę dodaj, aby można było określić oba końce przedziału.
Napisz procedurę dodaj(v, val, p, k), która wykona dodanie
wartości val do przedziału [p,k]. Możesz założyć, że wszystkie pola add są równe
0. W zamian założę, że użyjesz add wszędzie gdzie to możliwe.
Zaimplementuj opisany algorytm :) i wyślij rozwiązanie formularzem na dole strony.
Opis zadania: Wejście:
Pierwsza linia wejścia zawiera liczbę N (1 <= N <= 50000) - liczbę elemetnów ciągu A.
Druga linia zawiera N liczb - ciąg A ( -10^5 <= A[i] <= 10^5).
Trzecia linia zawiera Q (1 <= Q <= 10^5) - liczbę operacji.
Każda z kolejnych Q linii zawiera jedną operację opisaną trójką liczb - t, a, b. Pierwsza liczba określa typ operacji:
t=1 oznacza zapytanie - a, b 1<=a<=b<=N
t=0 oznacza modyfikację - 1<=a<=N, -10^5 <= b <= 10^5 - nową wartością A[a] jest b
Wyjście:
Dla każdego zapytania a, b wypisz maksimum w momencie wystąpienia pytania z A[x]+..A[y], gdzie a <= x <= y <= b. Przykład:
Wejście:
4
2 -1 4 -8
3
1 2 4
1 4 4
1 1 3
0 4 8
1 2 4
1 4 4
Wyjście:
4
0
5
12
8
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.