Футбол в Ужляндiї#167

Футбол в Ужляндiї (Editorial)

Рахувати перетини напряму — це \mathcal{O}(Q^2) пар, тому підемо від протилежного: порахуємо пари, які не перетинаються, і віднімемо їх від загальної кількості \binom{Q}{2}.

Два прямокутники не перетинаються тоді й лише тоді, коли їхні проєкції не перетинаються хоча б по одній осі. За формулою включень-виключень

|\text{не перетинаються}| = |X| + |Y| - |XY|,

де — пари з неперетинними проєкціями на вісь рядків, — на вісь стовпців, а — пари, у яких неперетинні обидві проєкції.

Величини і рахуються одновимірно. Для : пара неперетинна за , якщо в одного прямокутника x_2 строго менший за x_1 іншого. Побудуємо масив кількостей за значенням x_2 і його префіксні суми; тоді для кожного прямокутника додамо кількість тих, у кого x_2 < x_1 поточного. Кожна невпорядкована пара врахується рівно раз, бо «лівішим» може бути лише один із двох. Аналогічно для .

Величина потребує двовимірного підрахунку. Зафіксуємо прямокутник і порахуємо ті , що лежать строго лівіше за і водночас строго вище або строго нижче:

  • x_{2B} < x_{1A} і y_{2B} < y_{1A} — ліворуч-вгорі;

  • x_{2B} < x_{1A} і y_{1B} > y_{2A} — ліворуч-внизу.

Обидва запити — це підрахунок точок у прямокутній області, тому достатньо двох двовимірних масивів префіксних сум: одного за парою (x_2, y_2) і другого за парою (x_2, y_1). Кожен запит тоді обробляється за , і кожна невпорядкована пара знову рахується рівно раз — «лівішим» є лише один прямокутник.

Загальна складність — \mathcal{O}(NM + Q): побудова таблиць плюс лінійний прохід по прямокутниках.

Відповідь сягає \binom{Q}{2}, тобто може виходити далеко за межі 32-бітного типу — рахуйте у 64-бітному.