### coder_with_h's blog

By coder_with_h, history, 3 years ago, ,

Given a graph with N nodes and M edges. Each node is painted in one of N colors initially. There are Q queries of the following form: Repaint a single node to the given color. After performing each query, output the number of edges having both endpoints of the same color.

• +3

 » 3 years ago, # |   +10 HintSqrt decomposition
•  » » 3 years ago, # ^ |   0 can you please elaborate
•  » » » 3 years ago, # ^ |   0 1) We count number of edges having both endpoints of the same color before the quries. It will be ans.2) Divide nodes to 2 groups: 1 group: Nodes, which have more than sqrt(n) child. 2 group: Other nodes.3) For query for 1 type: if is it node from 1 groups: we just upd color, color[v] = col. else as they have less than sqrt(n) childs, we just going to childs and update ans.4) We will go with nodes from 1 groups, update answer like this: ans -= cnt[ls[v]][v] ans += cnt[color[v]][v] where, cnt[x][v] is number of nodes which have color x and it is child of v. ls[v] = it is last color of v. Memory limit will be Sqrt(n) * N.
•  » » » » 3 years ago, # ^ |   0 cnt[x][v] is number of nodes which have color x and it is child of v. The number of different colors is n and the number of nodes is n the memory limt will be n*n ??
•  » » » » » 3 years ago, # ^ |   0 cnt[x][v], it is array for nodes in 1 groups. The number of nodes, which have more than sqrt(n) child, will be less than sqrt(n), so we have Sqrt(N)*N.
•  » » » » » » 3 years ago, # ^ |   0 thanks
•  » » » » 7 weeks ago, # ^ |   0 Should'nt we update the cnt matrix everytime we perform the query operation or all the queries independent??