Конфликт интересов

Автор задачи: Аслан Тамаев, разработчик: Михаил Иванов

Сначала найдём число способов выбрать высоты горизонтальных сторон одного прямоугольника. Спроецируем для этого прямоугольник на вертикальную ось, он на ней высечет промаркированный отрезок длины $$$H$$$. Нам надо выбрать на нём подотрезок длины не более $$$h$$$. Если длина равна единице, то есть $$$H$$$ положений, где его разместить, если двойке, то $$$H-1$$$, и так далее — если $$$h$$$, то есть $$$H-h+1$$$ положений. По формуле для суммы арифметической прогрессии всего $$$\frac{(H+(H-h+1))h}2=\frac{(2H-h+1)h}2$$$ положений. Аналогично, вертикали для вертикальных сторон можно выбрать $$$\frac{(2W-w+1)w}2$$$ способами.

Итого есть $$$\frac{(2H-h+1)h}2\cdot\frac{(2W-w+1)w}2$$$ способов выбрать один прямоугольник. Если мы временно забудем про условие, что прямоугольники не пересекаются, то второй прямоугольник можно выбрать столькими же способами, и всего получается $$$\left(\frac{(2H-h+1)h}2\cdot\frac{(2W-w+1)w}2\right)^2$$$ способов выбрать пару прямоугольников.

Теперь надо вычесть количество пересекающихся пар прямоугольников. Заметим, что прямоугольники пересекаются тогда и только тогда, когда пересекаются их проекции на вертикальную ось и пересекаются их проекции на горизонтальную ось. Пусть $$$P_{H,h}$$$ — число способов выбрать на промаркированном отрезке длины $$$H$$$ два пересекающихся отрезка с целыми концами длины не более $$$h$$$. Тогда количество пересекающихся пар прямоугольников равно $$$\left(\frac{(2H-h+1)h}2\cdot\frac{(2W-w+1)w}2\right)^2-P_{H,h}\cdot P_{H,h}$$$, и, таким образом, задача решится, как только мы найдём $$$P_{H,h}$$$.

Давайте предположим, что на отрезке длины $$$H$$$ надо разместить пересекающиеся отрезки длин $$$p$$$ и $$$q$$$. Сколько есть способов сделать это? Если $$$p + q \ge H + 1$$$, то отрезки пересекутся при любом раскладе, то есть способов будет ровно $$$(H + 1 - p)(H + 1 - q)$$$. Нам будет удобно переписать это число в более симметрическом виде: $$$(H + 1)((H + 1) - (p + q)) + pq$$$.

Что же, если $$$p + q \le H$$$? И в этом случае формула есть, правда, немного другая: а именно, из всех $$$(H + 1)((H + 1) - (p + q)) + pq$$$ способов надо вычесть те $$$((H + 2) - (p + q))((H + 1) - (p + q))$$$, когда отрезки всё-таки не пересекаются (зафиксируем положение первого отрезка и для него посмотрим, сколько не пересекающихся с ним положений второго отрезка: увидим, что это сначала арифметическая прогрессия, убывающая от $$$(H + 1) - (p + q)$$$ к нулю, потом постоянный ноль, а потом арифметическая прогрессия, возрастающая назад к $$$(H + 1) - (p + q)$$$; удвоенная сумма арифметической прогрессии как раз даст нужный результат). Получится $$$((p + q) - 1)((H + 1) - (p + q)) + pq$$$.

Итак, надо перебрать все $$$p$$$ от 1 до $$$h$$$, все $$$q$$$ от 1 до $$$h$$$, для каждого из них взять $$$(H + 1)((H + 1) - (p + q)) + pq$$$, если $$$p + q \ge H + 1$$$, иначе взять $$$((p + q) - 1)((H + 1) - (p + q)) + pq$$$ и всё это сложить. Для начала заметим, что $$$pq$$$ можно сложить отдельно, получится $$$\left(\frac{h(h + 1)}2\right)^2$$$, и потом мы это добавим к первому слагаемому. А первое слагаемое зависит только от $$$p + q$$$, которое обозначим за $$$s$$$.

Так что надо перебрать все $$$s$$$ от 2 до $$$2h$$$, для каждого из них взять $$$(H + 1)((H + 1) - s)$$$, если $$$s \ge H + 1$$$, и $$$(s - 1)((H + 1) - s)$$$, если $$$s \le H$$$, и всё это сложить. А по сколько раз брать слагаемое? Столько раз, сколько способов есть представить $$$s$$$ в виде суммы двух слагаемых $$$p$$$ и $$$q$$$, каждое из которых от 2 до $$$h$$$. Это число можно выразить как $$$\min\{s - 1, 2h + 1 - s\}$$$.

Заметим, что $$$\min\{H + 1, s - 1\}((H + 1) - s)$$$ как раз равно $$$(H + 1)((H + 1) - s)$$$, если $$$s \ge H + 1$$$, и $$$(s - 1)((H + 1) - s)$$$, если $$$s \le H$$$ (если $$$s = H + 1$$$, то $$$(H + 1)((H + 1) - s) = (s - 1)((H + 1) - s)$$$, поскольку вторая скобка равна нулю). Поэтому итоговая формула такова: $$$$$$ P_{H, h} = \left(\frac{h(h + 1)}2\right)^2 + \sum_{i = 2}^{2h}{\min\{s - 1, 2h + 1 - s\}\min\{H + 1, s - 1\}(H + 1 - s)}. $$$$$$ Если по этой формуле найти $$$P_{H, h}$$$ и $$$P_{W, w}$$$ и подставить в формулу выше, то ответ будет найден за $$$\mathcal O(\max\{h, w\})$$$, и эта асимптотика достаточно хороша, поскольку по условию $$$h, w \leqslant 3\cdot 10^5$$$. Заинтересованный читатель спросит: а можно ли решить задачу с временной сложностью $$$\mathcal O(1)$$$? Что ж, да, можно. Указанная выше сумма может быть ещё лучше свёрнута, хоть этого подвига и не требовалось совершить на олимпиаде. Если $$$2h \leqslant H$$$, то $$$$$$ P_{H, h} = h^2\left(Hh-\frac{11h^2 - 6h - 5}{12}\right), $$$$$$ а если $$$2h > H$$$, то $$$$$$ P_{H, h} = \frac{5h^4 + (H - 1)H(H + 1)(H + 2) - 10(2H + 1)h^3 - 4\left(H^2 + H - 1\right)(2H + 1)h + \bigl(24H(H + 1) + 1\bigr)h^2}{12}. $$$$$$ В качестве упражнения можете доказать, что при любых целых $$$H$$$ и $$$h$$$ эти выражения принимают целые значения, а в качестве значительно более сложного упражнения — что не просто целые, а те, что нужно.