Jobs#403

Jobs (Editorial)

Зафіксуємо вертикальну лінію: вона розділяє точки на ліві й праві. Рухаючи від до n-1, точки переходять зі «правих» у «ліві» — по одній, тож усього оновлень. Лишається за фіксованого швидко знайти найкращу горизонтальну лінію.

Позначення. Тримаємо дерево відрізків за координатою : у листку лежать \ell_y — сумарна вага лівих точок цього рядка, і r_y — правих. Для горизонтального розрізу на висоті маємо чотири сектори

A = \sum_{t \le y} \ell_t, \quad B = \sum_{t \le y} r_t, \quad C = L - A, \quad D = R - B,

де , — сумарні ваги лівих і правих точок. Нерівномірність — це \max(A,B,C,D) - \min(A,B,C,D).

Ключова величина — префіксна різниця

s(y) = A - B = \sum_{t \le y} (\ell_t - r_t), \qquad T = L - R = s(n).

Тоді A - B = s, а C - D = T - s.

Чотири режими. Зі зростанням величини і не спадають, а і не зростають. Тому по послідовно змінюються чотири режими (і саме в такому порядку):

  1. максимум серед \{C,D\}, мінімум серед ;

  2. максимум і мінімум обидва серед \{C,D\};

  3. максимум і мінімум обидва серед ;

  4. максимум серед , мінімум серед \{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 — навпаки, тож в обох випадках величина однаково записується як

\max\bigl(|s|,\ |T - s|\bigr) \;=\; \max\bigl(s,\ -s,\ T-s,\ s-T\bigr).

Це опукла функція від з мінімумом у s = T/2, а режим 2 тримає s \le T/2, режим 3 — s \ge T/2. Тому мінімум по всьому середньому блоку виражається лише через найменше та найбільше значення у ньому:

\min_{y} \;=\; \max\bigl(\, s_{\min},\ -s_{\max},\ T - s_{\max},\ s_{\min} - T \,\bigr).

Отже у вузлах дерева треба зберігати, окрім сум і , ще й мінімум та максимум префіксної різниці всередині вузла. Склеювання очевидне: у правого сина всі префікси зсунуті на (\ell - r) лівого:

\mathrm{maxs} = \max\bigl(\mathrm{maxs}_{\text{лів}},\ (\ell-r)_{\text{лів}} + \mathrm{maxs}_{\text{прав}}\bigr),

і симетрично для мінімуму.

Разом. Для кожного : перекидаємо нові точки ліворуч (\mathcal{O}(\log n) на точку, всього разів), двома спусками знаходимо межі режимів, беремо три кандидати — кінець режиму 1, початок режиму 4 і формулу для середини — і виводимо мінімум.

Складність — \mathcal{O}(n \log n). Ваги до 10^9 і точок до 2 \cdot 10^5, тож усі суми — -бітні.