Answer these queries

23.02.2010 - Tomasz Górzny
TrudnośćTrudnośćTrudnośćTrudność

Rozpisujemy wszystko

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.

Z dodawaniem będziemy sobie radzić podobnie:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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ż $ O(\log N) $, wykonanie odwlekanych operacji wliczamy w koszt bieżącego zadania.

Praca domowa

  1. Pokaż w jaki sposób można usunąć z drzewa pole add.
    Snippet icon

    Aby sprawdzić poprawność rozwiązania, napisz procedurę wylicz_add(v), która wyliczy brakujące pole

  2. Pokaż w jaki sposób sobie radzić bez zerowania pola add.
    Snippet icon

    Napisz procedurę zapytanie(v, p, k), która nie zmodyfikuje v i wyliczy warość zapytania na przedziale [p,k].

  3. Zmodyfikuj procedurę dodaj, aby można było określić oba końce przedziału.
    Snippet icon

    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.

  4. 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.
    4.5
    Twoja ocena: Brak Ocena: 4.5 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com