Мін-Макс-Множення!#485

Мін-Макс-Множення! (Розбір)

Автор: Тимур Деґтярь

Розробники: Андрій Столітній, Тимур Деґтярь

Автор розбору: Андрій Столітній

Ми хочемо порахувати

S = \sum_{l=1}^{n} \sum_{r=l}^{n} \operatorname{mn}(l,r)\cdot\operatorname{mx}(l,r)

за \mathcal{O}(n\log n).

Внесок підмасивів довжини легко рахується окремо як

\sum_{i=1}^{n} a_i^2.

Далі розглядаємо тільки підмасиви довжини .

Напишемо функцію \text{solve}(l, r), яка рахує суму для всіх підмасивів, що повністю лежать у [l, r). Нехай m = \lfloor(l + r)/2\rfloor. Тоді всі підмасиви діляться на:

  1. повністю в ;

  2. повністю в ;

  3. такі, що перетинають середину: i \le m-1, j \ge m.

Перші два типи рахуємо рекурсивними викликами \text{solve}(l, m) та \text{solve}(m, r). Залишається навчитися ефективно рахувати внесок підмасивів, що перетинають середину.

Для відрізка йдемо j = m,\dots,r-1, підтримуємо

mn_R(j) = \min(a_m,\dots,a_j), \quad mx_R(j) = \max(a_m,\dots,a_j),

та префікси

\text{prmin}[k] = \sum_{t=m}^{k-1} mn_R(t), \quad \text{prmax}[k] = \sum_{t=m}^{k-1} mx_R(t), \quad \text{pr}[k] = \sum_{t=m}^{k-1} mn_R(t)\cdot mx_R(t),

де всі суми беруться за модулем.

Тоді, наприклад, \text{prmin}[q] - \text{prmin}[p] дорівнює \sum_{j=p}^{q-1} mn_R(j).

Перебираємо лівий кінець від m-1 до (у зворотному напрямку), підтримуємо

mn_L = \min(a_i,\dots,a_{m-1}), \quad mx_L = \max(a_i,\dots,a_{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, внесок

    (p-m)\cdot(mn_L\cdot mx_L);
  • для j \in [p, q): \operatorname{mn} = mn_R(j), \operatorname{mx} = mx_L, внесок

    mx_L\cdot\bigl(\text{prmin}[q]-\text{prmin}[p]\bigr);
  • для j \in [q, r): \operatorname{mn} = mn_R(j), \operatorname{mx} = mx_R(j), внесок

    \text{pr}[r]-\text{pr}[q].

Випадок p \ge q

Аналогічно, але ролі мінімуму і максимуму частково міняються:

  • для j \in [m, q): і мінімум, і максимум задаються лівою частиною, внесок

    (q-m)\cdot(mn_L\cdot mx_L);
  • для j \in [q, p): \operatorname{mn} = mn_L, \operatorname{mx} = mx_R(j), внесок

    mn_L\cdot\bigl(\text{prmax}[p]-\text{prmax}[q]\bigr);
  • для j \in [p, r): і мінімум, і максимум задаються правою частиною, внесок

    \text{pr}[r]-\text{pr}[p].

Усі ці суми беруться з префіксів за .

На кожному рівні рекурсії ми обробляємо елементи відрізка [l, r) за \mathcal{O}(r-l), глибина рекурсії — \mathcal{O}(\log n), тому загальна асимптотика \mathcal{O}(n\log n), а використана пам'ять — .