For the first two subtasks, when a new person stands, you only need to check their neighbourhood to see if other people will stand due to it. Then we can DFS and mark people who stand as visited. At most ~MN~ people will stand.

Time Complexity: ~\mathcal{O}(MN+K)~

For the third subtask, note that for any configuration, the end state will appear as the union of disjoint rectangles. Additionally, there are at most ~K~ such rectangles. Two rectangles which have any squares within Manhattan distance ~2~ of each other are merged into the smallest rectangle containing both. Whenever each of the ~K~ initial people stand, loop through the rectangles to see which are able to be merged with the new person's rectangle and merge appropriately. Note that you may need to merge multiple times for a single person's rectangle, but since there are at most ~K~ rectangles, this happens at most ~K~ times in total.

Time Complexity: ~\mathcal{O}(K^2)~

For the final subtask, the idea from the third subtask is used. Instead of looping through all the rectangles, we maintain the rectangles in a segment tree of sets. Each node represents a range of rows. Each node contains two sets which contain disjoint intervals of columns. The first set contains intervals of columns of rectangles which completely cover the range of the node. The second set contains intervals of columns of rectangles which have non-empty intersection with the range of the node. Using this segment tree, you can query a sub-rectangle to see how it can be merged. As in subtask 3, you may need to query multiple times for the same, expanding rectangle. A similar segment tree must be constructed where each node represents a range of columns and each set contains intervals of rows.

Unfortunately, this solution has a terrible constant factor and performs similarly to optimized ~\mathcal{O}(K^2)~ solutions.

Time Complexity: ~\mathcal{O}(K \log^2 K)~