2
Struktura danych dla aktualizacji interwałów i zapytań o liczbę zer
Szukam struktury danych, która utrzymywałaby tablicę liczb całkowitych o rozmiarze , i pozwalała na następujące operacje w czasie .tttnnnO(logn)O(logn)O(\log n) increase(a,b)increase(a,b)\text{increase}(a,b) , który zwiększa .t[a],t[a+1],…,t[b]t[a],t[a+1],…,t[b]t[a],t[a+1],\ldots,t[b] decrease(a,b)decrease(a,b)\text{decrease}(a,b) , co zmniejsza .t[a],t[a+1],…,t[b]t[a],t[a+1],…,t[b]t[a],t[a+1],\ldots,t[b] support()support()\text{support}() , która zwraca liczbę indeksów takich, że .iiit[i]≠0t[i]≠0t[i]\neq 0 Obiecujesz, że każde połączenie do zmniejszenia można dopasować do poprzedniego …