I'm sorry about my poor English.
First, make every cross a node. Give each node a position $$$(x, y)$$$. There is an edge between two nodes if and only if:
- $$$|x_1-x_2|+|y_1-y_2|=1$$$ - The edge splits two different characters.
For example, for the example situation in the problem.
We will get the graph:
When calculating the answer of a range $$$[l,r]$$$, it is just like adding edges at the left side of $$$x=l$$$, the right side of $$$x=r$$$, and removing all the edges out of $$$[l,r]$$$. For example, we need to calculate the answer in range $$$[2,4]$$$ in the previous graph. We just need to calculate the number of "faces" in the remaining graph.