Llf's blog

标签 题解 下的文章

Llf in 题解
April 19, 2018

题解-洛谷P2486 [SDOI2011]染色

题目链接: 洛谷 P2486 BZOJ P2243 方法 可以想到,颜色段的个数也是具有可加性的,但是如果两段连接处(即线段树中左子树的最右边的点和右子树的最左端的点)的颜色是相同的话,中间就只能算作一段,需要将颜色段个数-1。 所以我们在线段树里多加两个变量,分别为这一段最左端的点颜色和最右端的颜色,合并时和查询时判断一下即可。 注意的是查询链上时也需要判断。每次查询时记录一下左端点...