Drone Photo
Contest: SWERC 2021-2022 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Tags: combinatorics, math, sortings

Today, like every year at SWERC, the $$$n^2$$$ contestants have gathered outside the venue to take a drone photo. Jennifer, the social media manager for the event, has arranged them into an $$$n\times n$$$ square. Being very good at her job, she knows that the contestant standing on the intersection of the $$$i$$$-th row with the $$$j$$$-th column is $$$a_{i,j}$$$ years old. Coincidentally, she notices that no two contestants have the same age, and that everyone is between $$$1$$$ and $$$n^2$$$ years old.

Jennifer is planning to have some contestants hold a banner with the ICPC logo parallel to the ground, so that it is clearly visible in the aerial picture. Here are the steps that she is going to follow in order to take the perfect SWERC drone photo.

- First of all, Jennifer is going to select four contestants standing on the vertices of an axis-aligned rectangle.
- Then, she will have the two younger contestants hold one of the poles, while the two older contestants will hold the other pole.
- Finally, she will unfold the banner, using the poles to support its two ends. Obviously, this can only be done if the two poles are parallel and do not cross, as shown in the pictures below.

Being very indecisive, Jennifer would like to try out all possible arrangements for the banner, but she is worried that this may cause the contestants to be late for the competition. How many different ways are there to choose the four contestants holding the poles in order to take a perfect photo? Two choices are considered different if at least one contestant is included in one but not the other.

Input format:
The first line contains a single integer $$$n$$$ ($$$2\le n \le 1500$$$).

The next $$$n$$$ lines describe the ages of the contestants. Specifically, the $$$i$$$-th line contains the integers $$$a_{i,1},a_{i,2},\ldots,a_{i,n}$$$ ($$$1\le a_{i,j}\le n^2$$$).

It is guaranteed that $$$a_{i,j}\neq a_{k,l}$$$ if $$$i\neq k$$$ or $$$j\neq l$$$.

Output format:
Print the number of ways for Jennifer to choose the four contestants holding the poles.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first sample, there are $$$4$$$ contestants, arranged as follows.

There is only one way to choose four contestants, with one pole held by contestants aged $$$1$$$ and $$$2$$$ and the other one by contestants aged $$$3$$$ and $$$4$$$. But then, as we can see in the picture, the poles cross.

Since there is no valid way to choose four contestants, the answer is $$$0$$$.

In the second sample, the $$$4$$$ contestants are arranged as follows.

Once again, there is only one way to choose four contestants, but this time the poles don't cross.

Therefore, the answer is $$$1$$$.

In the third sample, the $$$9$$$ contestants are arranged as follows.

There are $$$6$$$ ways of choosing four contestants so that the poles don't cross, as shown in the following pictures.

Example input:
2
1 3
4 2

Example output:
0

Example input:
2
3 2
4 1

Example output:
1

Editorial:
For each $$$i = 1, \, \ldots, \, n^2$$$, let:
• $$$s_i$$$ denote the $$$i$$$-year-old contestant;
• $$$u_i$$$ be the number of contestants on the same row as $$$s_i$$$ who are (strictly) under $$$i$$$ years old;
• $$$v_i$$$ be the number of contestants on the same column as $$$s_i$$$ who are (strictly) under $$$i$$$ years old.
Let $$$A$$$ be the answer to the problem, i.e. the number of ways to choose four contestants so that the poles do not cross. We claim that $$$$$$ 2A=\sum_{i=1}^{n^2} \: [u_i(n - 1 - v_i) + (n - 1 - u_i)v_i]. $$$$$$ This gives a solution to the problem with overall time complexity $$$\mathcal O(n^2\log n)$$$, or $$$\mathcal O(n^2)$$$ if we use counting sort (which is feasible since the ages are in the range $$$[1, \, n^2]$$$). Let us now justify the claim.
Given an axis-aligned rectangle, we say that a contestant $$$s$$$ standing on one if its vertices is intermediate if exactly one of the two contestants on vertices adjacent to $$$s$$$ is younger than $$$s$$$. Rectangles in which the poles don't cross can be characterised by the fact that exactly two of the contestants on their vertices are intermediate (see figure (a) below for an example). On the contrary, rectangles in which the poles do cross have no intermediate contestants (figure (b)).
The right-hand side of the equation is the sum over all contestants $$$s$$$ of the number of rectangles for which $$$s$$$ is intermediate. Therefore, by the previous remark, this summation equals twice the number of rectangles with non-crossing poles, i.e. twice the answer to the problem.