CF1303F Number of Components

You are given a matrix $ n \times m $ , initially filled with zeroes. We define $ a_{i, j} $ as the element in the $ i $ -th row and the $ j $ -th column of the matrix. Two cells of the matrix are connected if they share a side, and the elements in these cells are equal. Two cells of the matrix belong to the same connected component if there exists a sequence $ s_1 $ , $ s_2 $ , ..., $ s_k $ such that $ s_1 $ is the first cell, $ s_k $ is the second cell, and for every $ i \in [1, k - 1] $ , $ s_i $ and $ s_{i + 1} $ are connected. You are given $ q $ queries of the form $ x_i $ $ y_i $ $ c_i $ ( $ i \in [1, q] $ ). For every such query, you have to do the following: 1. replace the element $ a_{x, y} $ with $ c $ ; 2. count the number of connected components in the matrix. There is one additional constraint: for every $ i \in [1, q - 1] $ , $ c_i \le c_{i + 1} $ .

N/A

N/A