Олексій та відрізки#37

Олексій та відрізки (Розбір)

Відрізки та не перетинаються, якщо один з них цілком лівіше за інший. Це відношення транзитивне: якщо лівіше за , а лівіше за , то й лівіше за . Тому трійка попарно неперетинних відрізків — це просто три відрізки, які можна вишикувати один за одним зліва направо.

Скористаємось цим: зафіксуємо середній відрізок трійки. Якщо для відрізка позначити

  • L_j — кількість відрізків, що цілком лівіше за нього (їхній правий кінець строго менший за l_j),

  • R_j — кількість відрізків, що цілком правіше за нього (їхній лівий кінець строго більший за r_j),

то кожна трійка з середнім елементом утворюється незалежним вибором одного відрізка зліва і одного справа. Отже, відповідь дорівнює

\sum_{j=1}^{n} L_j \cdot R_j.

Кожну трійку враховано рівно один раз, бо середній елемент у ній визначений однозначно.

Залишилось швидко порахувати L_j і R_j. Складемо відсортований масив усіх правих кінців — тоді L_j — це кількість елементів, строго менших за l_j, що знаходиться двійковим пошуком. Аналогічно R_j — кількість лівих кінців, строго більших за r_j.

Складність — \mathcal{O}(n \log n). Відповідь сягає порядку n^3, тобто 10^{16}, тому обов'язково беріть 64-бітний тип.