Ktoś ma jakieś szybkie rozwiązanie? Ja wysłałem O(n log^3 n), które było trochę wolne, dopychałem je kolanem i nie wiem czy się udało, ale strzelam że da się szybciej...

Edit: jest 10/10, ale jakim kosztem

Ja mam O(n log n), które korzysta z parametric search (<- nie potrafię wykazać że zachodzi ta fajna nierówność, które pozwala tego użyć) dla oraz CHT. Zamieniamy sobie nawiasowanie na drzewo gdzie wierzchołki odpowiadają poprawnym nawiasowaniom, a krawędź jest pomiędzy tymi wierzchołkami, które odpowiadają zagałęzionym nawiasom np. (()()()) to 1-2, 1-3, 1-4. Rozwiązanie O(n^2*k) robimy w taki sposób, że dla każdego wierzchołka liczymy dp[i][j], gdzie i to numer syna, a j to liczba operacji które użyliśmy dla tych synów, które przyspieszyć przy pomocy convex hull trick i zbić złożoność do O(n*k). Aby dojść do O(n log n) należy użyć parametric search, gdzie koszt nakładamy na każdą operację. Wtedy w synach liczymy po prostu jednowymiarowe dp[], które liczy się chyba podobnie. Sorry, że tak chaotycznie, ale nie chce mi się zbytnio tego rozpisywać, jak coś niejasne to mogę wyjaśnić.

Huh, to ja mam parametric search + jakiś trick z trzymaniem deque kolejnych kandydatów na optymalny punkt podziału, co daje O(n log^2 n) zapytań o koszt przedziału (a każde takie zapytanie robię jakimiś jump pointerami po takim drzewku jak ty opisałeś). Czyli w sumie podobny zbiór koncepcji, tylko bez CHT, i gorzej poskładany w całość xd Poza tym wyniki liczę w kolejności indeksów od lewej do prawej, a nie po drzewku (które mam osobno tylko po to żeby odpowiadać na zapytania o koszty), i to pewnie komplikuje sprawę.

Ja mam O(n log n) bez myślenia o drzewku, aczkolwiek implementację zrobiłem O(n log^2 n), bo sobie binsearchowałem w otoczkach (czego da się uniknąć). Robimy parametric search, a potem by wyliczać dynamik szybko trzymamy sobie stos convex hulli. Kolejne otoczki na stosie odpowiadają kolejnym niedomkniętym blokom nawiasów. Query na otoczce na szczycie stosu ma nam dawać wynik dla OPT punktu podziału leżącego w tym niedomniętym bloku. Jak napotykamy nowy nawias otwierający "(" to pushujemy nowy pusty hull. Jak napotykamy zamykający ")" to ściągamy ostatnią otoczkę, i do niższej pushujemy jedną funkcję otrzymaną z bloku co domknęliśmy.

Ja miałem O(n log^2 n). Ofc też mam parametric searcha. Kluczowym problemem u mnie było jak odpowiadać na zapytania "ile jest poprawnych nawiasowań na przedziale od i do j?". Na takie zapytania można odpowiadać w czasie stałym po preprocessingu O(n log n). Gdyby mieć zapytania na samym poczatku programu, to można by to zrobić poprzez D&C. Trzeba się trochę zastanowić jakie info trzeba mergować z lewej i prawej połówki, ale się da. A jak zapytań nie znamy, to trik jest taki, aby te wszystkie informacje zapamiętać na przyszłość (w szczególności jest n log n pamięci).

Jak już to mam i mam parametric searcha to muszę sobie liczyć jakoś tego dpka. Obserwacja jest taka, że jak mam dwie pozycje x<y i rozwazam z nich przejscia do jakiegos t, to x będzie lepsze na prefiksie, a y na sufiksie. Mogę sobie taki moment zmiany zbinsearchować. Przy takiej obserwacji utrzymuję dwukierunkową listę sensownych kandydatów i dla każdej sąsiedniej pary na tej liście znam moment kiedy ten wcześniejszy stanie się gorszy. Wynik zawsze idzie z pierwszego nieusuniętego elementu na liście.

@Wojtek: No, to mam tak samo, tylko koszt na przedziale liczę w O(log n).

Btw, ten trick z kolejką kandydatów i binsearchowaniem momentu gdy jeden stanie się lepszy od drugiego w bólach wyparsowałem z https://codeforces.com/blog/entry/8219?#comment-139241

> parametric search (<- nie potrafię wykazać że zachodzi ta fajna nierówność, które pozwala tego użyć)

Jeśli dobrze kojarzę, to jeśli mamy problem, w którym:
– trzeba podzielić dany ciąg wejściowy na k spójnych kawałków tak, by zminimalizować sumę kosztów kawałków; oraz
– funkcja kosztu kawałka spełnia „quadrangle inequality” postaci: koszt(a, c) + koszt(b, d) <= koszt(a, d) + koszt(b, c),
to automatycznie działa na tym problemie sporo optymalizacji dynamików: D&C, parametric search itd.

Intuicyjnie, quadrangle inequality jest swego rodzaju uogólnieniem pojęcia funkcji wypukłej na funkcje przyjmujące kawałki ciągu jako argument. Dla funkcji wypukłej (w 1D), „im większy x, tym szybciej rośnie funkcja”. Dla funkcji spełniającej quadrangle inequality: jak dokładam element X_i na koniec spójnego przedziału kończącego się X_{i-1}, to ten element zwiększa koszt przedziału tym mocniej, im dłuższy był oryginalny przedział.

Przykładowe funkcje, które spełniają tę nierówność:
– koszt(a, b) = kwadrat sumy od a-tego do b-tego elementu nieujemnego ciągu;
– koszt(a, b) = f(suma od a-tego do b-tego elementu nieujemnego ciągu), gdzie f jest funkcją wypukłą;
– koszt(a, b) = X[a] * Y[b], gdzie X jest ciągiem rosnącym, a Y jest ciągiem malejącym;
– koszt(a, b) = liczba spójnych podprzedziałów ciągu (x_a, ..., x_b) spełniających jakąś własność 𝒫.

Koszt z zadania to ten ostatni przykład, dla 𝒫 = „podprzedział oznacza poprawne wyrażenie nawiasowe”.