Zadanie Zdjęcia OIG. Zamiatanie oraz sqrt decomposition/drzewa przedział - przedział

Question

Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/G9Fs1g7hoS5uG9eeV84d0Axr/site/?key=statement

Gdzieś wyczytałem, że można to zrobić jakimś drzewem przedziałowym, ale mam problem, bo nie wiem jak napisać drzewo przedziałowe 2D. Umiem zwykłe drzewa przedziałowe 1D, ale 2D, to sobie trochę nie wyobrażam jak to zrobić. Ma ktoś pomysł?

A i umiem zrobić to zadanie na przedziale 1D,w sensie mam os liczbową, i drzewo przedział punkt, z dodaniem na przedziale i odczytem w punkcie, bo x_i oraz y_i są w przedziale [-200000,200000], więc starczy mi pamięci.

Z góry dziękuję za pomoc i poświęcony czas!

Answer 1

Drzewo przedziałowe 2D to trochę overkill. Z tego co wiem na OI nie mają prawa pojawić się przepływy, więc tym bardziej nie będzie takich skomplikowanych struktury danych jak drzewo przedziałowe 2D, sufiksowe itd.

Ale jak chcesz się z nimi zapoznać to zapytanie na drzewie o d wymiarach działa w O(log^dn). Tutaj opis jak działają

Samo zadanie można zrobić prościej. Słowa kluczowe: zamiatanie + drzewo przedziałowe 1D

Comments

Jedyne zadanie na zamiatanie które pamiętam to Zamek

---

@Whistleroosh, 

Dzięki za tak obszerne komentarze! Widzę, że fajne rzeczy masz na githubie, więc napewno się przyjrzę! Jeszcze raz dzięki za zadanka. 

A co do sum prefiksowych to włączenia i wyłączenia. S[i][j] = A[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1].

Dochodzę do siebie, bo tym zamiataniu xD, ta technika jest super. Pamiętam jak jakiś rok temu patrzyłem na to zadanie, i myślałem że to jakiś kosmos dla geniuszy oświeconych xD

---

@Whistleroosh, 

A propos sqrt, to wydaje mi się, że często nawet jak n<=10^6, to często wchodzi na np. 70pkt, a jak N <= 5*10^5, to też często wchodzi, nie mówiąc już jak N <= 10^5 lub N <= 2*10^5. Czy nawet trochę więcej. 

---

Jeszcze wracając do tego pierwiastka to warto żebyś nauczył się o tym algorytmie Mo. On też działa w O(nsqrt(n)), ale wyobraźmy sobie taki problem, że mamy tablicę n liczb i q zapytań. Każde zapytanie pyta ile jest różnych liczb w tablicy na pozycjach a...b Tą metodą z której skorzystaliśmy w tym zadaniu nie da się tego szybko zrobić, ale algorytm Mo jak najbardziej zrobi to w chyba O((n+q)sqrt(n))

---

tak apropo, to jeszcze fajne zadanie na zamiatanie to kopalnia złota z finału OI.