这实际上是一个 Tarjan 求割点的裸题。 具体来说是这样的。首先，对于每一个连通块，答案显然是独立的。然后 …
lp4577 FJOI2018 领导集团问题
我们尝试类比序列上的情况来看这一题。 对于序列上的情况，我们维护一个集合 ，其中 表示，长度为 的 …
lp2564 SCOI2009 生日礼物
尺取法即可。 开一个桶维护珍珠的颜色，然后扫一遍。每一次将最前端的点弹出，然后移动至下一个合法点。
lp2219 HAOI2007 修筑绿化带
我们知道，如果我们确定了每个大矩形包含的权值最小的小矩形，那么我们只需要枚举一遍每一个大矩形并比较它们的回形部 …
lp3313 SDOI2014 旅行
虽然这一题被划在主席树下面，但是一眼看过去这不就是树链剖分动态开点线段树的模板题么。 树链剖分后我们考虑对每一 …
lp3285 SCOI2014 方伯伯的OJ
题目要求维护一个编号序列和一个排名序列，并支持四种操作： 1.按照编号修改编号，并返回该编号的排名。 2.将一 …
lp3168 CQOI2015 任务查询系统
观察题面，我们发现这是一道变态题：区间加点，单点查询第k大，强制在线——这tm不是变态题么！别的不说，权值怎么 …
lp3302 SDOI2013 森林
我们发现，树上的链上第k大是可以使用主席树来维护的。对于每一个节点，我们从它的父亲复制一个版本，然后每一次求出 …
lp2501 HAOI2006 数字序列
我们分别考虑一二问。 对于第一问，我们思考一个子序列是合法的「不用修改」的子序列的充要条件。 容易想到的，这个 …
lp3233 HNOI2014 世界树
让我们来分析这道题。 我们很容易地可以发现，如果一个节点是末端节点，那么它肯定是由它祖先中的第一个节点管辖更优 …
lp2519 HAOI2011 problem a
我们为每个考生设置一个可能的区间。这个区间的左端点是l=a+1，右端点是r=n-b。 仔细观察，会发现，这个可 …
lp2486 SDOI2011 染色
考虑这一题在链上的情况。 显然，可以建一棵线段树，修改是打标记下传，查询是左右相加特判左右相邻处颜色是否相同。 …
lp5290 十二省联考2019 春节十二响
首先我们考虑一种n^2logn的做法：将所有的子程序根据内存消耗来排序，然后每一次选中内存消耗最大且尚未被选中 …
lp2590 ZJOI2008 树的统计
树剖套线段树裸题。
lp4582 FJOI2014 树的重心
两个重心的情况想想都麻。我们首先考虑一个重心的情况。 我们把 假设我们现在已经求出了每个子树的大小，那么我们发 …
lp1337 JSOI2004 平衡点 or 吊打XXX
首先我们认识一种算法——爬山算法。这种算法总是贪心地接受更优秀的解。 但是，我们知道，并不是所有的解都是一个单 …
lp4332 SHOI2014 三叉神经树
我们知道，每一个\(x_{i}\)各不相同。这启发我们，这一题的点将形成一棵树的结构。 仔细观察题目描述，我们 …
lp3203 HNOI2010 弹飞绵羊
依照题意，我们发现，题目求的就是指定点到根的路径长度。 于是，我们对于每一个修改弹力的操作，都可以转化为断边和 …
lp2147 SDOI2008 洞穴勘测
维护链接和断开，LCT裸题，（看起来）也可以用按秩合并优化并查集。
lp3320 SDOI2015 寻宝游戏
我们找到了这样一个结论： 「一个树上点集构成的最小生成树中，若两点间有路径，则此两点的DFS序在树上相近。」 …