Witam, mam problem z zadaniem, w którym trzeba wykorzystać drzewo przedziałowe. Wiem, że mam je stworzyć, wiem, że mam przechowywać w nim długość najdłuższej przerwy, ale nie wiem, jak je aktualizować po dodaniu lekcji lub usunięciu jej. Czy moglibyście dać mi jakieś wskazówki? Byłabym bardzo wdzięczna
W pewnej hipotetycznej szkole dzień został podzielony na n jednostek czasu. W każdej z tych jednostek może odbywać się lekcja lub nie. Czas pomiędzy lekcjami nazywamy przerwą. Plan zajęć zmienia się bardzo dynamicznie. Dany jest ciąg operacji (1) dodania lekcji oraz (2) usunięcia lekcji. Po każdej takiej operacji określ, jaka jest najdłuższa przerwa w ciągu dnia. Jeżeli właśnie wykonana operacja zmieniła długość najdłuższej przerwy w ciągu dnia, wypisz nowy czas trwania najdłuższej przerwy. Na początku plan lekcji nie zawiera żadnej lekcji.
Wejście
W pierwszej linii wejścia dana jest liczba n (1 ≤ n ≤ 106) oznaczająca liczbę jednostek czasu w ciągu dnia. W następnych liniach dany jest ciąg operacji zakończony zerem. Operacje opisywane są przez dwie liczby w k (w = 1 lub 2, 1 ≤ k ≤ n). Jeżeli w = 1, w k-tej jednostce czasu została dodana lekcja (wiemy na pewno, że wcześniej była tam przerwa). Jeżeli w = 2, w k-tej jednostce czasu zlikwidowno lekcje (która na pewno tam była).
Wyjście
Po każdej operacji, która zmieniła długość najdłuższej przerwy w ciągu dnia, wypisz nową długość.
Przykład
Dla danych wejściowych
15
1 2
1 13
1 4
1 10
1 1
1 6
1 5
2 4
2 5
1 5
1 8
2 2
1 2
2 8
2 5
1 14
2 6
2 2
1 8
2 1
0
poprawną odpowiedzią jest
13
10
8
5
3
2
3
2
3
7
8
6
7