Llf's blog

标签 省选 下的文章

Llf in 题解
April 24, 2018

题解-洛谷P4092 [HEOI2016/TJOI2016]树

第一次写树剖没看题解A题,发现题解洛谷题解区大佬里竟然没有一个做法一样的,实在是太激动了 树剖学习:https://llf0703.com/p/shu-lian-pou-fen.html 题目链接 洛谷 P4092 BZOJ P4551 方法 裸树剖 ,直接用线段树维护每一段区间中被标记的最深的节点就行了。先全部赋值为-1,然后向上传递时直接取两段中的最大值即可(因为越深的点d...
Llf in 题解
April 19, 2018

题解-洛谷P2486 [SDOI2011]染色

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