P12049 KMN's Petri Dish

 **Please read the Hint section carefully.** KMN is a top biology competition contestant. She has a Petri dish with many cells inside. Each cell occupies some grid cells. Each grid cell has a letter indicating which cell occupies it. The same cell is represented by the same letter. Different adjacent cells are represented by different letters. Each time, KMN asks you about a rectangle. If we cut the Petri dish with this rectangle, how many cells will be contained in the cut-out part (inside the rectangle)? If one cell is cut into multiple pieces, they are counted as multiple cells. However, these cells may also split or merge, so you also need to maintain update operations.

There is an $n \times n$ colored matrix. A connected component is defined by the familiar 4-connected grid graph: starting from a grid cell $A$, each step moves to a same-colored grid cell whose Manhattan distance is at most $1$. If you can reach another grid cell $B$, then $A$ and $B$ are in the same connected component. There are $q$ operations. + Point update: modify the color of cell $(x,y)$. + Range query: given $(l,r,u,d)$, ask: if we only keep the submatrix formed by rows $[u,d]$ and columns $[l,r]$, how many connected components are there? Note: when determining whether two cells are in the same connected component using the definition above, you are not allowed to move outside the queried region. Each query is independent.

The first line contains a positive integer $n$. The next $n$ lines each contain $n$ lowercase letters, representing the colored matrix. The number of colors in the matrix does not exceed $26$, corresponding to the $26$ lowercase letters. The next line contains a positive integer $q$, the number of operations. The next $q$ lines each start with a positive integer $op$, indicating the operation type. + Update operation: $op=1$. The same line then contains two positive integers $x,y$ and a character $c$, meaning to change the character at $(x,y)$ to $c$. + Query operation: $op=2$. The same line then contains four positive integers $u, l, d, r$, with meanings as above.

Output $q \div 2$ lines, each containing one positive integer, the answer. It is guaranteed that type $2$ operations make up exactly half of all operations.

**The full score of this problem is $3 \times 10^5$ points.** For $100\%$ of the testdata: $1 \le l,r,u,d \le n \le 500$. $1 \le q \le 5000$. It is guaranteed that the numbers of type $1$ and type $2$ operations are equal. The SubTasks of this problem are only used to group testdata of similar sizes. There is no bundling relationship. Test point information: |SubTask ID|$n=$|$q=$| |:-:|:-:|:-:| |$1$|$50$|$1000$| |$2$|$50$|$5000$| |$3$|$100$|$1000$| |$4$|$100$|$5000$| |$5$|$300$|$1000$| |$6$|$300$|$3000$| |$7$|$300$|$5000$| |$8$|$500$|$1000$| |$9$|$500$|$3000$| |$10$|$500$|$5000$| For $100\%$ of the testdata, it is guaranteed that KMN is a biology competition master, so even for a $500\operatorname{cm} \times 500\operatorname{cm}$ Petri dish she can observe every grid cell and its changes accurately. This problem uses `Special Judge`. When a test point has $x$ type II operations, then for each type II operation: if your answer matches the standard answer, you get $\frac{10000}{x}$ points. Therefore, if your program cannot solve a certain query, please output a single integer on one line (it must be within the int range), to ensure that the later queries can still be judged and scored normally. Translated by ChatGPT 5