To skoro jeszcze nikt nie spytał - jak rozwiązaliście to zadanie?

Na początek skupmy się na jakiejś sensownej charakteryzacji f(A, B). Załóżmy bez straty ogólności, że |A|>=|B|. Okazuje się, że to jakie konkretnie wartości tworzą B nie ma znaczenia, a liczy się tylko i wyłącznie jego długość (ale dla A jak najbardziej wartości mają znaczenie). Konkretniej, niech długości kolejnych monotonicznych przedziałów w A to będą c_1, ..., c_p. okazuje się, że f(A,B)<=x wtedy i tylko wtedy gdy |B| >= sum floor((c_i-2)/(x-1)). W dowód wchodzić nie będę, tym bardziej, że sam go nie dociągnąłem w pełni. Aczkolwiek to że jest to warunek konieczny jest całkiem łatwe i daje intuicję, czemu to może mieć sens.

Skoro już mamy taką charakteryzację to trzeba przejść do zastanowienia się co z tym. Przeiterujemy się po wszystkich wartościach x i wyznaczymy liczbę par A', B' takich że f(A', B')<=x. Dzięki, że liczą się tylko jakieś podłogi przy dzieleniu przez x, okazuje się, że dla ustalonej wartości x jest tak naprawdę tylko O(n/x) nierozróżnialnych grupek początków i końców i nie jest trudno wymyślić zarys algorytmu, który takie coś przetworzy w czasie O(n/x), co daje rozwiązanie O(n log n). Po drodze warto naklepać sobie strukturkę zbioru, która wspiera operacje "dodaj a kopii liczby b do zbioru", "usuń a kopii liczby b ze zbioru", "odejmij 1 od wszystkich liczb w zbiorze", "podaj sumę kwadratów/sumę/liczbę wszystkich liczb w zbiorze" (a tak naprawdę wymagania są bardziej szczegółowe, ale wchodzić w nie nie będę). Owa strukturka ma mniej więcej odpowiadać na ile sposobów można wybrać koniec A' oraz przedział B' dla ustalonego początku A' i ten zbiór się aktualizuje wraz z przesuwaniem początku A'. Ale konkretna implementacja tego wszystkiego jest niesamowicie męcząca i zajęła mi 8h

Dowód wzoru, który podał Wojtek:

Załóżmy, że |A| >= |B|. Jeśli mamy monotoniczny przedział w A, to jasne, że trzeba pomiędzy niego wstawić co najmniej tyle elementów B, ile powiedział Wojtek, żeby go podzielić na odpowiednio krótkie przedziały.

Jeśli mamy rosnące trzy elementy w A: a1 < a2 < a3, to możemy je zawsze rozdzielić dowolnym elementem b, żeby było < > <. Jeśli b < a2, to robimy: a1 < a2 > b < a3. Jeśli b > a2, to robimy: a1 < b > a2 < a3.

Jeśli nam zostaną nadmiarowe elementy w B, to parujemy je z ostatnimi elementami w A, i robimy tak, żeby końcówka zawsze była na zmianę < > < > < > . Załóżmy na przykład, że mamy ciąg, który kończy się ... < a1 i teraz chcemy wstawić dwa dodatkowe elementy a2, b2 na koniec. Jeśli min(a2, b2) < a1, to robimy: < a1 > min(a2, b2) < max(a2, b2). Jeśli min(a2, b2) > a1, to robimy: < a2 > a1 < b2.

Mój algorytm zliczania jest trochę inny, ale też O(n log n).

Idę prawym końcem po A. Dla każdego x trzymam strukturę danych, która zawiera zbiór punktów, w których trzeba porozdzielać A, i zlicza liczbę możliwości. Gdy przesuwam się w prawo po A, to te punkty, które są w aktualnym przedziale monotonicznym będą przesuwać się w prawo, a wcześniejsze stoją w miejscu.

Każdą strukturkę trzeba zmieniać tylko wtedy, gdy dzieje się coś ważnego:
* dodanie nowego punktu; trzeba to zrobić dla każdego x takiego, że x-1 | c-2; tych dzielników jest średnio log c
* koniec przedziału monotonicznego; to jest istotne tylko dla tych x, które są krótsze od długości przedziału

Żeby nie trzeba było poprawiać każdej struktury cały czas, to trik jest taki, że po każdej operacji struktura liczy sobie "jaki byłby końcowy wynik, gdyby od teraz już nie trzeba było nic poprawiać". Jak jest jakaś zmiana, to odejmujemy ten przewidywany wynik, robimy operację, i dodajemy nowe przewidywanie.

Żeby dało się to liczyć szybko, potrzebuję dla obu typów punktów rozdzielających dwóch liczb: suma pozycja(i) oraz suma i * pozycja(i).