Shifting Dominoes
Contest: Codeforces Global Round 8
Difficulty rating: 3200
Tags: data structures, geometry, graphs, trees

Bill likes to play with dominoes. He took an $$$n \times m$$$ board divided into equal square cells, and covered it with dominoes. Each domino covers two adjacent cells of the board either horizontally or vertically, and each cell is covered exactly once with a half of one domino (that is, there are no uncovered cells, and no two dominoes cover the same cell twice).

After that Bill decided to play with the covered board and share some photos of it on social media. First, he removes exactly one domino from the board, freeing two of the cells. Next, he moves dominoes around. A domino can only be moved along the line parallel to its longer side. A move in the chosen direction is possible if the next cell in this direction is currently free. Bill doesn't want to lose track of what the original tiling looks like, so he makes sure that at any point each domino shares at least one cell with its original position.

After removing a domino and making several (possibly, zero) moves Bill takes a photo of the board and posts it. However, with the amount of filters Bill is using, domino borders are not visible, so only the two free cells of the board can be identified. When the photo is posted, Bill reverts the board to its original state and starts the process again.

Bill wants to post as many photos as possible, but he will not post any photo twice. How many distinct photos can he take? Recall that photos are different if the pairs of free cells in the photos are different.

Input format:
The first line contains two positive integers $$$n$$$ and $$$m$$$ ($$$nm \leq 2 \cdot 10^5$$$) — height and width of the board respectively.

The next $$$n$$$ lines describe the tiling of the board, row by row from top to bottom. Each of these lines contains $$$m$$$ characters, describing the cells in the corresponding row left to right. Each character is one of U, D, L, or R, meaning that the cell is covered with a top, bottom, left, or right half of a domino respectively.

It is guaranteed that the described tiling is valid, that is, each half-domino has a counterpart in the relevant location. In particular, since tiling is possible, the number of cells in the board is even.

Output format:
Print a single integer — the number of distinct photos Bill can take.

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

Note:
In the first sample case, no moves are possible after removing any domino, thus there are four distinct photos.

In the second sample case, four photos are possible after removing the leftmost domino by independently moving/not moving the remaining two dominoes. Two more different photos are obtained by removing one of the dominoes on the right.

Example input:
2 4
UUUU
DDDD

Example output:
4

Example input:
2 3
ULR
DLR

Example output:
6

Editorial:
Let's think of how a certain cell can be freed up. One way is to just lift the domino covering it from the start. If we didn't do it, then we must move the domino covering the cell, and there is exactly one way of doing so. But at this point the cell we've moved to should have been free. We can follow this chain of events, and we must eventually arrive to a cell that was covered by the initially removed domino.
This is more readily seen if we draw a graph with vertices being cells, and edges leading from the cell freed up by moving a domino to the cell becoming occupied by doing so. Note that some of the cells are impossible to free up with such a move.
Let us study this graph a bit more. If we color the board like a chessboard, we can see that edges always connect cells of the same color, so the two subgraphs for white and black cells are independent. Further, since initially a white and a black cell are freed, the two free cells will always have different colors.
In this graph each vertex (= cell) has out-degree at most $$$1$$$. In general directed graphs of this kind are called functional graphs, and look like a bunch of trees linked to directed cycles. However, it turns out that our graph can not have cycles! To prove this, let's look a how this cycle would look like:
Centers of all the cells in a cycle form a lattice polygon. The area of such a polygon can be found with Pick's formula: $$$S = I + B / 2 - 1$$$, where $$$I$$$ and $$$B$$$ is the number of lattice points inside and on the boundary respectively. However, we can observe that:
• $$$B$$$ is the length of the boundary. The boundary can be broken into segments of length $$$2$$$. The length of upward and downward arrows is the same, therefore the length of vertical borders is divisible by $$$4$$$, same for horizontal arrows. Thus $$$B$$$ is divisible by $$$4$$$, and $$$B / 2$$$ must be even.
• Inside of the polygon can be broken down into $$$2 \times 2$$$ squares, therefore $$$S$$$ must be even.
• $$$I = S - B / 2 + 1$$$ should therefore be odd. However, the inside of the cycle is isolated from the outside, and therefore should be independently tilable with dominoes. But the number of cells (= vertices) inside the cycle is odd, therefore it's impossible.
Since our directed graph has no cycles, it must be a directed forest, which makes it much easier to handle.
Now consider a pair of cells $$$c_1, c_2$$$ of different colors, and look at the paths $$$P_1$$$ and $$$P_2$$$ starting at these cells. If these paths reach the boundary without visiting the same domino, then the pair $$$c_1, c_2$$$ is impossible to free up, since we would have to remove at least two dominoes.
If the paths do visit at least one common domino, then we argue that the pair is possible to free up. Indeed, consider the first domino $$$D$$$ on $$$P_1$$$ that is also visited by $$$P_2$$$. If we remove $$$D$$$, then the parts of $$$P_1$$$ and $$$P_2$$$ until $$$D$$$ can not intersect, thus it is possible to move dominoes to free $$$c_1$$$ and $$$c_2$$$ without trying to move any domino twice.
To figure out the answer, consider the two forests $$$F_1$$$ and $$$F_2$$$ built up by black and white cells of the board. If we label each cell of each forest with the index of the domino covering this cell, then the answer is equal to the number of pairs of cells $$$c_1 \in F_1$$$, $$$c_2 \in F_2$$$ such that the paths starting at $$$c_1$$$ and $$$c_2$$$ have common labels. To actually compute the answer we will instead count the cell pairs with label-disjoint paths.
This is now a fairly standard data structure problem. Construct Euler tours in both $$$F_1$$$ and $$$F_2$$$. Then, the subtree of each vertex is a segment in the Euler tour. For a cell $$$c_1 \in F_1$$$ labeled with domino $$$D$$$, suitable cells in $$$F_2$$$ are the ones not in the subtree of a cell sharing the label with $$$c_1$$$ or with any parent of $$$c_1$$$.
Perform a DFS of $$$F_1$$$, following edges in reverse. When we enter a cell labeled $$$D$$$, locate the cell with this label in $$$F_2$$$ and mark all vertices in its subtree. At this point, we should add the number of unmarked cells in $$$F_2$$$ to the answer. When we leave the cell, revert to the previous configuration before marking the subtree. Implementation-wise, this can be done with a segment tree that supports adding on a segment (= subtree in the Euler tour), and finding the number of zeros (= unmarked cells).
Segment tree is the most demanding component of the solution, thus the complexity is $$$O(nm \log (nm))$$$.