Sasha and Algorithm of Silence's Sounds
Contest: Codeforces Round 539 (Div. 1)
Difficulty rating: 3200
Tags: data structures, trees

One fine day Sasha went to the park for a walk. In the park, he saw that his favorite bench is occupied, and he had to sit down on the neighboring one. He sat down and began to listen to the silence. Suddenly, he got a question: what if in different parts of the park, the silence sounds in different ways? So it was. Let's divide the park into $$$1 \times 1$$$ meter squares and call them cells, and numerate rows from $$$1$$$ to $$$n$$$ from up to down, and columns from $$$1$$$ to $$$m$$$ from left to right. And now, every cell can be described with a pair of two integers $$$(x, y)$$$, where $$$x$$$ — the number of the row, and $$$y$$$ — the number of the column. Sasha knows that the level of silence in the cell $$$(i, j)$$$ equals to $$$f_{i,j}$$$, and all $$$f_{i,j}$$$ form a permutation of numbers from $$$1$$$ to $$$n \cdot m$$$. Sasha decided to count, how many are there pleasant segments of silence?

Let's take some segment $$$[l \ldots r]$$$. Denote $$$S$$$ as the set of cells $$$(i, j)$$$ that $$$l \le f_{i,j} \le r$$$. Then, the segment of silence $$$[l \ldots r]$$$ is pleasant if there is only one simple path between every pair of cells from $$$S$$$ (path can't contain cells, which are not in $$$S$$$). In other words, set $$$S$$$ should look like a tree on a plain. Sasha has done this task pretty quickly, and called the algorithm — "algorithm of silence's sounds".

Time passed, and the only thing left from the algorithm is a legend. To prove the truthfulness of this story, you have to help Sasha and to find the number of different pleasant segments of silence. Two segments $$$[l_1 \ldots r_1]$$$, $$$[l_2 \ldots r_2]$$$ are different, if $$$l_1 \neq l_2$$$ or $$$r_1 \neq r_2$$$ or both at the same time.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 1000$$$, $$$1 \le n \cdot m \le 2 \cdot 10^5$$$) — the size of the park.

Each from next $$$n$$$ lines contains $$$m$$$ integers $$$f_{i,j}$$$ ($$$1 \le f_{i,j} \le n \cdot m$$$) — the level of silence in the cell with number $$$(i, j)$$$.

It is guaranteed, that all $$$f_{i,j}$$$ are different.

Output format:
Print one integer — the number of pleasant segments of silence.

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

Note:
In the first example, all segments of silence are pleasant.

In the second example, pleasant segments of silence are the following:

Example input:
1 5
1 2 3 4 5

Example output:
15

Example input:
2 3
1 2 3
4 5 6

Example output:
15

Editorial:
A range $$$[l \ldots r]$$$  — a tree, if the graph formated by it doen't have any cycle and there is only one connected component in this graph. Let's $$$t_r$$$ be such minimal position, that $$$[t_r \ldots r]$$$ doen't contain cycles (forest). It is obvous that $$$t_r \leq t_{r+1}$$$. Suppose for each $$$r$$$ we find $$$t_r$$$. Then the task now is to count the number of such $$$t_r \leq l \leq r$$$ that graph formated by the range $$$[l \ldots r]$$$ consists of one connected component.
How to find $$$t_r$$$ for each $$$r$$$. Let's move two pointers: $$$t_r$$$ and $$$r$$$. For each moment we store a graph formated by that range. If you add $$$1$$$ to one of the pointers then you should add/delete up to $$$4$$$ edges to the graph. Before adding an edge check whether two verticies are in different components (not to form a cycle), and if they are in one component, then it is needed to delete some edges  — move the first pointer. So now we need some structure that can process $$$3$$$ types of queries online: add an edge, delete an edge, check if two verticies are in one connected component. As long as the graph will never have a cycle, so it is possible to answer queries using link-cut tree ($$$O(log(n \cdot m))$$$ for one query).
It is left to count the number of suitable $$$l$$$ ($$$t_r \leq l \leq r$$$) for each $$$r$$$. Let's iterate $$$r$$$ from $$$1$$$ to $$$n \cdot m$$$ and maintain $$$cmp_i$$$  — the number of connected components for $$$[i \ldots r]$$$. Then for a fixed $$$r$$$ you should add to the answer the number of such $$$i$$$ that $$$t_r \leq i \leq r$$$ and $$$cmp_i = 1$$$. What is going on when we move $$$r$$$ and add some edge at that moment. Let's that edge be $$$(x, r+1)$$$ and $$$t_r \leq x$$$ (if $$$x < t_r$$$ then you can skip this edge). For $$$i$$$, for which $$$x \lneq i \leq r$$$, $$$cmp_i$$$ won't change after you add an edge, but for $$$t_r \leq i \leq x$$$ two trees merge in one  — $$$cmp_i$$$ decreases by $$$1$$$. Let's have a segtree to store $$$cmp_i$$$, then decreasing by $$$1$$$ is equivalent to adding $$$-1$$$ on a range, and the number of $$$1$$$ on a range is the number of minimums. All such queries can be done in $$$O(log(n \cdot m))$$$.
The total complexity is $$$O(n \cdot m \cdot log(n \cdot m))$$$.