Zadanie Holes, CodeForces

Question

Witam, mam problem z zadaniem Dołki. Na pierwszy rzut oka wydawało mi się, że trzeba przeprowadzać pełne symulacje przebytej trasy kulki. Niestety tego typu brut daje jedynie 10%. Grafy też odpadają, bo tutaj także byłaby symulacja, na co nie mamy czasu. W treści zadania powiedziane jest o modyfikacjach, czyli skłaniałbym się ku jakiemuś drzewu przedziałowemu, lecz nie wiem w jaki sposób użyć drzewa przedziałowego. Pomoże ktoś? Z góry dzięki za poświęcony czas oraz nadsyłane komentarze i odpowiedzi :D

Answer 1

Wydaje mi się, że mozna to zrobić pierwiastkami. Bardzo podobnie jak zadanie Holes z codeforces:https://codeforces.com/problemset/problem/13/E

Dzielisz sobie ciąg na podprzedziały długości pierwiastek.

I teraz dla każdego z N elementów, trzymasz do jakiego przeskoczysz najbliższego w kolejnym przedziale. Na początku napełniasz to dynamikiem, w czasie liniowym. I potem jak masz querry, to skaczesz sobie wykonując sqrt(N) skoków, a jak masz update, to musisz zaktualizować tylko dp w swoim przedziale, w którym jest element A, więc też wykonasz sqrt(N) skoków.

Wydaje mi się, że do wejdzie, bo N <= 10^5.

Śmiem twierdzić, że to zadanie, to jest kopia Holes z codeforces. Limity są takie same jak w Holes i treść wydaje mi się, że też.

Na kółku OKI zawansowane 2022 / 2023, Pan Mikołaj Bulge, świetnie wyjaśnij kiłka zadań na sqrt, między innymi:

- Little Elephant And Array - podstawa sqrt - Super zadanie, stosunkowo nie trudne.

- Kontenery z 2 etapu OI - podstawa sqrt, też barzdo fajne

- I właśnie to zadanie Holes z codeforces

Link do zajęć z kółka z sqrt: https://www.youtube.com/watch?v=ltHNUi6KKmw&list=PL9BlBU4U-rDM3sfyyyvCqwytcTB8joHCt&index=7

Warto obejrzeć, bo dobrze wytłumaczył to zadanie!