Зафіксуємо вертикальну лінію: вона розділяє точки на ліві й праві. Рухаючи від до n-1, точки переходять зі «правих» у «ліві» — по одній, тож усього оновлень. Лишається за фіксованого швидко знайти найкращу горизонтальну лінію.
Позначення. Тримаємо дерево відрізків за координатою : у листку лежать \ell_y — сумарна вага лівих точок цього рядка, і r_y — правих. Для горизонтального розрізу на висоті маємо чотири сектори
де , — сумарні ваги лівих і правих точок. Нерівномірність — це \max(A,B,C,D) - \min(A,B,C,D).
Ключова величина — префіксна різниця
Тоді A - B = s, а C - D = T - s.
Чотири режими. Зі зростанням величини і не спадають, а і не зростають. Тому по послідовно змінюються чотири режими (і саме в такому порядку):
максимум серед \{C,D\}, мінімум серед ;
максимум і мінімум обидва серед \{C,D\};
максимум і мінімум обидва серед ;
максимум серед , мінімум серед \{C,D\}.
Номер режиму не спадає з , тож межі між режимами шукаються спуском по дереву відрізків за \mathcal{O}(\log n): тримаємо накопичені і і питаємо, чи режим у цій точці ще не перевищив заданий.
Крайні режими — монотонні. У режимі 1 нерівномірність дорівнює \max(C,D) - \min(A,B): перший доданок спадає, другий зростає, отже вся величина строго спадає. Найкраще — на останньому цього режиму. Симетрично в режимі 4 величина зростає, тож найкраще — на першому . Два запити, і обидва рахуються прямо.
Середина. У режимах 2 і 3 нерівномірність — це |C - D| та |A - B| відповідно, тобто |T - s| та . Але в режимі 2 виконано |s| \le |T-s|, а в режимі 3 — навпаки, тож в обох випадках величина однаково записується як
Це опукла функція від з мінімумом у s = T/2, а режим 2 тримає s \le T/2, режим 3 — s \ge T/2. Тому мінімум по всьому середньому блоку виражається лише через найменше та найбільше значення у ньому:
Отже у вузлах дерева треба зберігати, окрім сум і , ще й мінімум та максимум префіксної різниці всередині вузла. Склеювання очевидне: у правого сина всі префікси зсунуті на (\ell - r) лівого:
і симетрично для мінімуму.
Разом. Для кожного : перекидаємо нові точки ліворуч (\mathcal{O}(\log n) на точку, всього разів), двома спусками знаходимо межі режимів, беремо три кандидати — кінець режиму 1, початок режиму 4 і формулу для середини — і виводимо мінімум.
Складність — \mathcal{O}(n \log n). Ваги до 10^9 і точок до 2 \cdot 10^5, тож усі суми — -бітні.