Автор: Тимур Деґтярь
Розробники: Андрій Столітній, Тимур Деґтярь
Автор розбору: Андрій Столітній
Ми хочемо порахувати
за \mathcal{O}(n\log n).
Внесок підмасивів довжини легко рахується окремо як
Далі розглядаємо тільки підмасиви довжини .
Напишемо функцію \text{solve}(l, r), яка рахує суму для всіх підмасивів, що повністю лежать у [l, r). Нехай m = \lfloor(l + r)/2\rfloor. Тоді всі підмасиви діляться на:
повністю в ;
повністю в ;
такі, що перетинають середину: i \le m-1, j \ge m.
Перші два типи рахуємо рекурсивними викликами \text{solve}(l, m) та \text{solve}(m, r). Залишається навчитися ефективно рахувати внесок підмасивів, що перетинають середину.
Для відрізка йдемо j = m,\dots,r-1, підтримуємо
та префікси
де всі суми беруться за модулем.
Тоді, наприклад, \text{prmin}[q] - \text{prmin}[p] дорівнює \sum_{j=p}^{q-1} mn_R(j).
Перебираємо лівий кінець від m-1 до (у зворотному напрямку), підтримуємо
Для цього треба додати внесок усіх підмасивів , де j \in [m, r-1].
Використовуємо два вказівники по правій частині:
— перша позиція, де a_p \le mn_L;
— перша позиція, де a_q \ge mx_L.
Далі маємо два випадки.
Випадок p < q
Тоді:
для j \in [m, p): \operatorname{mn} = mn_L, \operatorname{mx} = mx_L, внесок
для j \in [p, q): \operatorname{mn} = mn_R(j), \operatorname{mx} = mx_L, внесок
для j \in [q, r): \operatorname{mn} = mn_R(j), \operatorname{mx} = mx_R(j), внесок
Випадок p \ge q
Аналогічно, але ролі мінімуму і максимуму частково міняються:
для j \in [m, q): і мінімум, і максимум задаються лівою частиною, внесок
для j \in [q, p): \operatorname{mn} = mn_L, \operatorname{mx} = mx_R(j), внесок
для j \in [p, r): і мінімум, і максимум задаються правою частиною, внесок
Усі ці суми беруться з префіксів за .
На кожному рівні рекурсії ми обробляємо елементи відрізка [l, r) за \mathcal{O}(r-l), глибина рекурсії — \mathcal{O}(\log n), тому загальна асимптотика \mathcal{O}(n\log n), а використана пам'ять — .