Oleg and chess
Contest: Tinkoff Challenge - Elimination Round
Difficulty rating: 3400
Tags: data structures, divide and conquer, flows, graph matchings

Oleg the bank client solves an interesting chess problem: place on n × n chessboard the maximum number of rooks so that they don't beat each other. Of course, no two rooks can share the same cell.

Remind that a rook standing in the cell (a, b) beats a rook standing in the cell (x, y) if and only if a = x or b = y.

Unfortunately (of fortunately?) for Oleg the answer in this problem was always n, so the task bored Oleg soon. He decided to make it more difficult by removing some cells from the board. If a cell is deleted, Oleg can't put a rook there, but rooks do beat each other "through" deleted cells.

Oleg deletes the cells in groups, namely, he repeatedly choose a rectangle with sides parallel to the board sides and deletes all the cells inside the rectangle. Formally, if he chooses a rectangle, lower left cell of which has coordinates (x1, y1), and upper right cell of which has coordinates (x2, y2), then he deletes all such cells with coordinates (x, y) that x1 ≤ x ≤ x2 and y1 ≤ y ≤ y2. It is guaranteed that no cell is deleted twice, i.e. the chosen rectangles do not intersect.

This version of the problem Oleg can't solve, and his friend Igor is busy at a conference, so he can't help Oleg.

You are the last hope for Oleg! Help him: given the size of the board and the deleted rectangles find the maximum possible number of rooks that could be placed on the board so that no two rooks beat each other.

Input format:
The first line contains single integer n (1  ≤  n ≤  10000) — the size of the board.

The second line contains single integer q (0  ≤  q  ≤  10000) — the number of deleted rectangles.

The next q lines contain the information about the deleted rectangles.

Each of these lines contains four integers x1, y1, x2 and y2 (1  ≤ x1 ≤ x2 ≤ n, 1  ≤ y1 ≤ y2 ≤ n) — the coordinates of the lower left and the upper right cells of a deleted rectangle.

If is guaranteed that the rectangles do not intersect.

Output format:
In the only line print the maximum number of rooks Oleg can place on the board so that no two rooks beat each other.

Constraints:
Time limit: 6.5 s
Memory limit: 256.0 MB

Note:
Here is the board and the example of rooks placement in the first example:

Example input:
5
5
1 1 2 1
1 3 1 5
4 1 5 5
2 5 2 5
3 2 3 5

Example output:
3

Example input:
8
4
2 2 4 6
1 8 1 8
7 1 8 2
5 4 6 8

Example output:
8

Editorial:
Naive solution: Make bipartite graph, there is edge i → j only if cell (i, j) is free.
Then answer is maximum matching.
But this solution time complexity is O(n3)
To get faster solution, let's cut our field into rectangles that are free of occupied cells.
We will go from left to right wth line sweep and store all vertical free spaces to the left of the line in the set. Triples (y1, y2, x) — from y1 to y2 border of free space is x. When we meet rectangle (x1, y1, x2, y2), we should take everything that lies between y1 and y2 in the set, seperate boundary segments, throw out everything that lies inside, construct new rectangles, and add (y1, y2, x2 + 1) to the set. We will have O(n) rectangles.
Then for each rectangle (x1, y1, x2, y2) we need to add for all vertices from left part from x1 to x2 edges to all verticles of right part from y1 to y2.
Let's build segment tree for all verticles of left part, and another segment tree for all vertices from right part.
Then to add rectangle of free cells to our graph, lets split segment [x1;x2] into log vertices in segment tree of left part, and segment [y1;y2] into log in segment tree of right part.
Then for all pairs of these vertixes add edge with capacity ∞.
For all vertices of left segment tree add edges from them to their parents with capacity ∞.
For all vertices of right segment tree add edges from their parents to them with capacity ∞.
For all leafs of the left segment tree add edge from source to them with capacity 1.
For all leafs of the right segment tree add edge from them to sink with capacity 1.
Then max flow in this graph is the answer.
Why does this work fast?
At first let's try the Edmonds–Karp algorithm. It works in O(nE) in this task, where E — is the number of edges, $$E = O(n \log^2 n)$$. In the given constraints E is bounded by value about several million, because the rectangles do not intersect. This gives complexity about 1010, and indeed, this algorithm passes, but very close to the time limit.
Let's not try Dinic algorithm. We can prove (using a theorem that is known as Karsanov theorem in Russian) that, similar to matching search, the Dinic algorithm has no more than $$O(\sqrt{n} \log n)$$ phases. With the use of the same bound on the edges number, we can get around 109 operations that is ok.
Also there are alternative solution with sparse table.