576e
[CF576E] Painting Edges
Painting Edges 动态加边和二分图容易想线段树分治,分别维护 k 种颜色的并查集。 不过每条边的存在时间不能确定。 设边 i 的两次操作的时间为 \(x_i,y_i\),那么对于 \(t\in[x_i+1,y_i-1]\) 有两种情况,颜色改变或改色不变。 则我们把每次操作影响的时间放在 ......
CF576E Painting Edges
根据不知从何而来的传统,考前需要写数据结构。 ### Part 1 如何判断二分图 你要是用染色法暴力过了这道题那就只能说是真神仙…… 但是我们可以使用染色的思想。 考虑到颜色数不多,可以开 $k$ 个**拓展域并查集**,对于原图每个点我们拆成两个:$i$ 和 $i+n$,如果 $i+n$ 和 $ ......