Szczupak waży X i może zjeść szprotkę u, ale nie może v, u < X < v.

u,v to są kolejne szprotki.

Szczupak zjada od u w lewo tyle, żeby być w stanie zjeść v. Załóżmy, że wystarczyło mu zjedzenie tylko u. Teraz waży X+u i przeniesie się w kolejne najbliższe (na prawo) miejsce, gdzie będzie szprotka w > X+u (albo na koniec). Szczupak będzie znowu zjadał tyle, żeby zjeść w, czyli po kolejnym kroku będzie mógł ważyć > 2*(X+u) -> ważył X+u przed kolejnym krokiem, a po kolejnym kroku może zjeść w > X+u.

Co masz na myśli przez "zabrać się za kolejną"? Jeśli najmniejszą większą od obecnej, to czemu masa szczupaka miała by się zwiększać dwukrotnie? np. szczupak ma masę X >> 10^2, a szprotki:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, X+10^2
? Dobrze rozumiem, że taki krok będzie tylko jeden?

Nie, za każdym razem zwiększa się waga szczupaka co najmniej dwukrtotnie.

Edit: Całe rozwiązanie. Oflline - wczytuję queries i biorę wszystkie dodane szprotki - te z wejścia i te, które będą dodawane (usuwanie pomijam). Sortuję je po wagach i wyznaczam pozycję w drzewie przedziałowym. Im większa waga, tym bardziej na prawo wyląduje szprotka.

2 struktury: drzewo przedziałowe i set. Set trzyma pary, waga szprotki i pozycja w drzewie. Drzewo przedziałowe umożliwia zmianę konkretnej pozycji (dodanie i usunięcie szprotki), wyznaczenie końca lewego przedziału, potrzebnego do zjedzenia odpowiedniej sumy wag, a także zablokowanie/odblokowanie całego przeddziału - co następuje w momencie zjedzenia podczas ataku i cofnięciu tego zjedzenia, po zakończeniu symulacji. Operacje blokowania nie kolidują z modyfikacją pozycji, w dodatku zawsze będą występowały w taki sposób, że raz zablokowany przedział, będzie blokowany kolejny raz w przedziale zawierającym go całkowicie (ponieważ kolejne szprotki będę musiał zjadać coraz bardziej w lewo). Dlatego też nie jest wymagane lazy propagation, a zwykłe zablokowanie przedziału i wyzerowanie sumy oraz ilości szprotek.

Operacje: dodawanie -> wstaw parę do seta i zmień pozycję w drzewie przedziałowym. Usuwanie - usuń ostatnią szprotkę o danej wadze z drzewa oraz z seta.

Atak:
Znajdź największą szprotkę, jaką może zjeść szczupak (set). Wyznacz ile musi zjeść, żeby być w stanie zabrać się za kolejną -> wyznacz ten przedział operacją get left opisaną powyżej. Po drodze zobacz, czy jedząc nie osiągnie swojej docelowej wagi. Zjedz wszystko, co powinieneś i z seta wyznacz kolejną szprotkę do zjedzenia. W tym momencie waga szczupaka zwiększyła się min dwukrotnie. Więc powtarzamy te kroki, aż dojedziemy do ostatniej szprotki lub osiągniemy żądaną wagę. Tych kroków będzie log n i każdy krok zajmuje log n, czyli całość operacji to O(log^2n). Zjedzenie przedziału na lewo, to po prostu zablokowanie go z operacji powyżej i odłożenie go na stos. Po zakończeniu symulacji ściągam kolejno przedziały ze stosu i je odblokowuję. Wartości w drzewie przywracam, gdy ściągnę ostatni przedział, który zablokował dany węzeł.

Nie jest za wolno szukanie szprotki po szprotce?

Ja miałem drzewo przedziałowe do zjadania od aktualnej szprotki w lewo (szprotki w drzewie są wkładane po niemalejących wagach, z ewentualnymi dziurami, gdzie waga = 0) i set dla wygody, żeby szukać kolejnej większej szprotki.

Potwierdzam

No dobra, zapamiętam, w takim razie, jaka była optymalna?

Grammar nazi.

Nie ma bardziej i mniej optymalnych, są optymalne lub nie. :-P

PS. polecam zapamiętać, bo to chyba ulubiona doczepka promotorów. (-:

Jaka struktura była tu najbardziej optymalna?

Potwierdzam :>

potwierdzmam tez

Potwierdzam

Potwierdzam wszystkie

Zgadza się

Ok