Відрізки та не перетинаються, якщо один з них цілком лівіше за інший. Це відношення транзитивне: якщо лівіше за , а лівіше за , то й лівіше за . Тому трійка попарно неперетинних відрізків — це просто три відрізки, які можна вишикувати один за одним зліва направо.
Скористаємось цим: зафіксуємо середній відрізок трійки. Якщо для відрізка позначити
L_j — кількість відрізків, що цілком лівіше за нього (їхній правий кінець строго менший за l_j),
R_j — кількість відрізків, що цілком правіше за нього (їхній лівий кінець строго більший за r_j),
то кожна трійка з середнім елементом утворюється незалежним вибором одного відрізка зліва і одного справа. Отже, відповідь дорівнює
Кожну трійку враховано рівно один раз, бо середній елемент у ній визначений однозначно.
Залишилось швидко порахувати L_j і R_j. Складемо відсортований масив усіх правих кінців — тоді L_j — це кількість елементів, строго менших за l_j, що знаходиться двійковим пошуком. Аналогічно R_j — кількість лівих кінців, строго більших за r_j.
Складність — \mathcal{O}(n \log n). Відповідь сягає порядку n^3, тобто 10^{16}, тому обов'язково беріть 64-бітний тип.