我们尝试类比序列上的情况来看这一题。 对于序列上的情况,我们维护一个集合 ,其中 表示,长度为 的 …
lp3313 SDOI2014 旅行
虽然这一题被划在主席树下面,但是一眼看过去这不就是树链剖分动态开点线段树的模板题么。 树链剖分后我们考虑对每一 …
lp2146 NOI2015 软件包管理器
简化题意: 存在一棵树,其上所有点的初始值为0。 存在两种操作,分别是,将一个点的所有父亲节点改为1,或者将一 …
lp2486 SDOI2011 染色
考虑这一题在链上的情况。 显然,可以建一棵线段树,修改是打标记下传,查询是左右相加特判左右相邻处颜色是否相同。 …
lp3676 小清新数据结构题
仔细考虑这道题,我们可以将问题转化为「修改」和「换根」两个操作。 对于修改操作,我们知道,每个点的权值对且仅对 …
CF487E Tourists
众所周知,圆方树是用来处理图上点双相关问题的。 同时,点双又是一个和简单路径密切相关的东西。故而这一题我们可以 …
CF600E Lomsat gelral
一道树上启发式合并的例题。 首先考虑暴力的做法。统计每一个子节点的信息,然后传到父节点。 我们发现这样做的复杂 …