Sum of Matchings
Contest: Educational Codeforces Round 124 (Rated for Div. 2)
Difficulty rating: 2600
Tags: brute force, combinatorics, constructive algorithms, dfs and similar, graph matchings, greedy, math

Let's denote the size of the maximum matching in a graph $$$G$$$ as $$$\mathit{MM}(G)$$$.

You are given a bipartite graph. The vertices of the first part are numbered from $$$1$$$ to $$$n$$$, the vertices of the second part are numbered from $$$n+1$$$ to $$$2n$$$. Each vertex's degree is $$$2$$$.

For a tuple of four integers $$$(l, r, L, R)$$$, where $$$1 \le l \le r \le n$$$ and $$$n+1 \le L \le R \le 2n$$$, let's define $$$G'(l, r, L, R)$$$ as the graph which consists of all vertices of the given graph that are included in the segment $$$[l, r]$$$ or in the segment $$$[L, R]$$$, and all edges of the given graph such that each of their endpoints belongs to one of these segments. In other words, to obtain $$$G'(l, r, L, R)$$$ from the original graph, you have to remove all vertices $$$i$$$ such that $$$i \notin [l, r]$$$ and $$$i \notin [L, R]$$$, and all edges incident to these vertices.

Calculate the sum of $$$\mathit{MM}(G(l, r, L, R))$$$ over all tuples of integers $$$(l, r, L, R)$$$ having $$$1 \le l \le r \le n$$$ and $$$n+1 \le L \le R \le 2n$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$2 \le n \le 1500$$$) — the number of vertices in each part.

Then $$$2n$$$ lines follow, each denoting an edge of the graph. The $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \le n$$$; $$$n + 1 \le y_i \le 2n$$$) — the endpoints of the $$$i$$$-th edge.

There are no multiple edges in the given graph, and each vertex has exactly two incident edges.

Output format:
Print one integer — the sum of $$$\mathit{MM}(G(l, r, L, R))$$$ over all tuples of integers $$$(l, r, L, R)$$$ having $$$1 \le l \le r \le n$$$ and $$$n+1 \le L \le R \le 2n$$$.

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

Example input:
5
4 6
4 9
2 6
3 9
1 8
5 10
2 7
3 7
1 10
5 8

Example output:
314

Editorial:
Instead of counting the edges belonging to the maximum matching, it is easier to count the vertices. So, we will calculate the total number of vertices saturated by the maximum matching over all possible tuples $$$(l, r, L, R)$$$, and then divide the answer by $$$2$$$. Furthermore, it's easier to calculate the number of unsaturated vertices than the number of saturated vertices, so we can subtract it from the total number of vertices in all graphs we consider and obtain the answer.
Let's analyze how to calculate the total number of unsaturated vertices. Each graph $$$G'(l, r, L, R)$$$ is a subgraph of the given graph, so it is still bipartite, and the degree of each vertex is still not greater than $$$2$$$. A bipartite graph where the degree of each vertex is at most $$$2$$$ can be represented as a set of cycles and paths, and the maximum matching over each of these cycles/paths can be considered independently. Each cycle has an even number of vertices (since otherwise the graph would not be bipartite), so we can saturate all vertices on a cycle with the matching. For a path, the number of unsaturated vertices depends on its length: if the number of vertices in a path is even, we can match all vertices on it; otherwise, one vertex will be unsaturated. So the problem reduces to counting paths with odd number of vertices in all possible graphs $$$G'(l, r, L, R)$$$.
Every path with an odd number of vertices has a center (the vertex which is exactly in the middle of the path). Let's iterate on the center of the path and its length, and calculate the number of times this path occurs in all graphs we consider. Suppose the center of the path is the vertex $$$x$$$, and the number of vertices in it is $$$2k+1$$$. Then, for this path to exist, two conditions must hold:
• every vertex $$$y$$$ such that the distance from $$$x$$$ to $$$y$$$ is not greater than $$$k$$$ should be present in the graph;
• every vertex $$$z$$$ such that the distance from $$$x$$$ to $$$z$$$ is exactly $$$k+1$$$ should be excluded from the graph.
It means that, for each of the two parts of the graph, there are several vertices that should be present in the graph, and zero or two vertices that should be excluded from the graph. It's easy to see that among the vertices we have to include, we are only interested in the minimum one and the maximum one (all vertices between them will be included as well if these two are included). So, we need to implement some kind of function that allows us to calculate the number of segments that cover the minimum and the maximum vertex we need, and don't cover any of the vertices that we have to exclude — this can be easily done in $$$O(1)$$$. Note that the segments should be considered independently for both parts of the graph.
Overall, for each vertex we have to consider at most $$$O(n)$$$ different lengths of odd paths with the center in this vertex. The minimum/maximum indices of vertices in both parts we have to include in the graph can be maintained while we increase the length of the path, so the whole solution works in $$$O(n^2)$$$.