| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
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.
Can anyone please help me solve this problem?
Sqrt decomposition
can you please elaborate
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.
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 ??
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.
Should'nt we update the cnt matrix everytime we perform the query operation or all the queries independent??