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!