Задача від Степана#16

Задача від Степана (Editorial)

Прямокутник можна повертати, тому кожен з них зручно одразу нормалізувати: запишемо його як пару , де w = \min(\text{сторін}), а h = \max(\text{сторін}). Після цього прямокутник накривається прямокутником тоді й лише тоді, коли

w_B \ge w_A \quad \text{і} \quad h_B \ge h_A.

Тобто треба порахувати, скільки прямокутників доміновані хоча б одним іншим.

Задача розв'язується сортуванням із заміткою. Відсортуємо прямокутники за спаданням , а при рівних — за спаданням . Тепер оброблятимемо їх у цьому порядку, підтримуючи — максимальне серед уже оброблених.

Коли ми дійшли до чергового прямокутника, усі раніше оброблені мають не менше за його власне. Тому він є маленьким тоді й лише тоді, коли H \ge h. Після перевірки оновлюємо H = \max(H, h).

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

За умовою всі прямокутників різні, тому питання «прямокутник накриває сам себе» не виникає.

Складність — \mathcal{O}(N \log N), що цілком достатньо при N \le 200\,000.