Я обнаружил несколько иное доказательство формулы Пика, ничего радикально нового в нём нет, но оно не использует индукцию, не рассматривает частные случаи и не полагается на формулу Эйлера для многогранников.

Схема такая:

1. Установить справедливость формулы для прямоугольной трапеции с основаниями параллельными Oy и боковой стороной на Ox.
2. Воспользоваться формулой сумм трапеций для нахождения площади.

Дана перестановка длинны n ≤ 10^5. Каждый её элемент раскрашен в один из n цветов. Необходимо для каждого элемента i найти количество инверсий одного с ним цвета. Ожидаемая сложность n log(n).

Кроме очевидного "для каждого цвета взять дерево отрезков и посчитать инверсии" мне в голову ничего не приходит. Что ещё можно попробовать?