Omówienie zadania Rozliczenia (II etap XXVI OI)

W zadaniu mamy stworzyć bibliotekę, która umożliwi nam wykonywanie następujących operacji na ciągu liczb:

• dodaj(\(k\)) – dodanie liczby \(k\) na końcu ciągu,

• koryguj(\(i\), \(k\)) – dodanie wartości \(k\) do \(i\)-tego elementu od końca ciągu (przy czym \(i\leq m\)),

• suma(\(i\)) – zsumowanie \(i\) ostatnich elementów ciągu (przy czym \(i\leq m\)).

Może być aż \(n \leq 10^7\) operacji na ciągu, ale musimy pamiętać co najwyżej \(m \leq 10^6\) ostatnich liczb, bo tylko na nich będą wykonywane operacje. Kluczowe jest ograniczenie pamięciowe w tym zadaniu, bo mamy dostępne jedynie 10 MB.

Podzadanie 1

Ponieważ \(m \leq 50\), możemy trzymać liczby w wektorze, a gdy jego rozmiar przekroczy \(m\), to każda operacja dodania będzie poprzedzona operacją usunięcia pierwszego elementu wektora. Tak więc operacje dodaj i suma będą działały w czasie \(O(m)\), więc cały algorytm w czasie \(O(nm)\).

Zużycie pamięci będzie niewielkie, pamiętamy bowiem jedynie 50 liczb.

Podzadanie 4

Robimy cykliczną tablicę rozmiaru \(m\), w której trzymamy \(m\) ostatnio dodanych liczb. Jeśli ostatnią liczbę dodaliśmy na pozycji \(i\), to kolejną liczbę dodamy na pozycji \((i+1) \bmod m\), potencjalnie zamazując liczbę, która tam była (a która nie będzie już nam potrzebna).

Operacja suma będzie wymagała zsumowania dwóch przedziałów z tej tablicy.

Aby operacje wykonywać szybko, nad tą tablicą implementujemy drzewo przedziałowe, które umożliwia zmianę elementu oraz odpytanie o sumę przedziału w czasie \(O(\log m)\).

Czas działania rozwiązania będzie zatem \(O(n \log m)\).

Drzewo przedziałowe oprócz \(m\) komórek na liście drzewa, będzie potrzebować jeszcze \(m\) dodatkowych komórek na węzły wewnętrzne. W każdym węźle będziemy trzymać 64-bitową zmienną typu long long (czyli zajmującą 8 B). Tak więc dla \(m \leq 2^{19}\) zużyjemy \(2m \cdot 8\ \textrm{B} = 8\ \textrm{MB}\).

Podzadanie 5

Drzewo przedziałowe można zaimplementować jako drzewo potęgowe lub drzewo Fenwicka. Będzie wtedy potrzebować jedynie \(m\) komórek, co dla \(m \leq 2^{20}\) również umożliwi zmieszczenie się w 8 MB pamięci.

Implementacje tych drzew opisane są w książce Przygody Bajtazara.