This problem can be solved by appropriately managing the connected components, where adjacent cells with the same color are considered connected.

Solution using ordered set

Maintain the following three data structures and update them for each query: - an array \(C\) storing the number of cells with each color; - an ordered set \(S\) that stores the index of leftmost cell of each connected component; - a dictionary \(D\) that stores the color of each cell.

A query of the second type can be simply responded by printing \(C[c]\). A query of the first type can be processed as follows:

1. Let \(L\) be the largest element less than or equal to \(x\) among the elements of \(S\). Let \(R\) be the smallest element strictly greater than \(L\) among the elements of \(S\).
   (The connected component containing \(x\) is the right half-open interval \([L,R)\).)
2. Update \(D\) and \(C\) by:
   • \(C[D[L]] \leftarrow C[D[L]] - (R-L)\)
   • \(D[L] \leftarrow c\)
   • \(C[D[L]] \leftarrow C[D[L]] + (R-L)\)
3. If adjacent connected components have the same color, remove the boundary.
   • If \(D[R]=D[L]\), remove \(R\) from \(S\) (right bound).
   • Let \(L'\) be the largest element strictly less than \(L\) among the elements of \(S\). If \(D[L']=D[L]\), then remove \(L\) from \(S\).

This process can be done in \(O(\log N)\) time per query, so the problem has been solved in a total of \(O(Q\log N)\) time.

writer’s solution (C++)

Solution using DSU (Disjoint Set Union)

Maintain the following two data structures and update them for each query: - an array \(C\) storing the number of cells with each color; - a DSU that manages the connected components, maintaining the index of the leftmost cell, size, and the color.

Just as the solution using an ordered set, it is sufficient to:

1. discover the connected component containing \(x\),
2. update \(C\) and the color of the connected component, and
3. merge adjacent connected components if they have the same color.

This process can be in amortized \(O(\alpha(N))\) time per query, so the problem has been solved in a total of \(O(Q \alpha(N))\) time.
(\(\alpha\) is the inverse Ackerman function.)

writer’s solution (C)