题面 P3645 [APIO2015]雅加达的摩天楼 Solution 与其说这题是分块妙题，我更倾向于把这题称为分层图妙题。 这题有一个一眼贪心做法：对于每只doge，我们都暴力地去建它连向它能跳到的点的边，边权为跳的次数。然后直接求一遍单元最短路即可。 很显然，这玩意的边的数量是$O(n^2)$的，求一遍最短路的复杂度达到了惊人的$n^2logn^2$ 这显然是要T飞的，但是我们会从中...

题面 P3247 [HNOI2016]最小公倍数 Solution 这是一道妙题。 首先，根据常识，题面要我们求的是找一条从s,t的路径，使得路径上$max\ a=a,max\ b=b$。 这咋求呢？我们会发现，我们要求的路径本质上是一个连通块，连通块可以考虑用并查集处理。 接下来考虑对a分块，先把所有的边按照$a$来排序，再分块，每个块里连的所有边保证$<=a_{[size*x]}...

题面 洛谷团队题（尚未入团的请尽快加入团队） 梗 $\huge μ’sic\ Forever!$ 114514.avi.zip 1919810 （(懂的人自然懂(确信)) 真寻酱实在是太可爱了 ⑨个样例(我够良心吧) 真*Solution 稍有常识的人都可以看出,一个文件目录在任意时刻都是一个树的形式（如果没有快捷方式的话）。 像这样：（样例） 解法一 我们来看看type=1啥意思… ...

题面 APIO2012 派遣 Solution 这是一道左偏树的模板题，不会左偏树的可以戳这里 显然，我们可以发现对于同一颗子树，我们想让取的人尽可能便宜，如果说目前为止取的价格超过$C$,就优先把贵的人先丢掉。 因此，我们考虑用左偏树来维护这个东西。对于每一个人，我们都建一颗以价格为关键字的大根堆。考虑从下往上合并，一旦堆的元素总和超过$C$就不断弹栈，弹到合法为止。然后我们算一下$l_...

题面 洛谷P2173 Solution 首先，我们可以发现颜色总数特别的少，再考虑到有改变边的颜色的操作，可以考虑用LCT来解决。 我们建$c$颗LCT，每颗LCT存每个颜色对应的边，splay记录每颗splay的MAX_w。 对于修改权值，考虑直接暴力修改每个颜色的LCT里对应的点的权值 对于修改颜色，我们可以暴力在每一颗LCT里面枚举来找一下有没有这条边，有的话就断掉，然后在对应的LC...

题面 洛谷P3285 Solution 这是一道数据结构大暴力题。 我们可以很显然的发现对于询问排名，维护排名的操作，我们可以直接上一个维护下标的splay。 因为点的数量奇多，这让我们回想起NOIP2017 列队，我们可以用“splay 动态开点”这样的操作来解决，即一开始我们把所有信息全部压到一个点里面去（即一个点代表一段区间），需要的时候再用“拆点”把点拆开。 问题是这破题很让人讨厌...

题面 洛谷 P1501 Solution 这是一道肥肠考验LCT基本功的一道题。 口胡起来是很容易的：对于每一个加/乘操作，我们把对应的链split出来，然后打标记即可；Link/Cut是基本操作；查询的话我们也是把对应的链split出来，然后直接输出根的sum即可。 这里的打标记和线段树II那道题非常像，不会的同学可以先去做线段树II。 都在写LCT了，怎么可能没打过线段树II。我们只需...

题面 洛谷P1110 Solution 我们看到这道题，我们不妨想把处于同一个点的骑士全部丢到一个小根堆左偏树里面。这样子，我们从下往上合并，合并完就去检查一下根是否满足当前城市的要求，一直弹根弹到满足要求为止。 至于能力的变化，这里的操作要求无外乎乘法和加法。因此，我们可以像线段树II那道题那样做两个标记，处理一下即可。每次合并、弹根之前都pushdown标记。 就酱，这题就被我们切掉啦...

题面 [Luogu P4768] [NOI2018]归程 Solution 这题可能要用到Kruskal重构树的相关知识，如果有需求的同学可以看这里 首先，根据我们之前在运输计划那道题的经验，我们会发现我们开车能经过的边一定在以海拔为关键字的最大生成树上。 根据Kruskal重构树的性质：Kruskal重构树是一个堆，我们可以考虑这样做： 我们先把Kruskal重构树按每条路的海拔从大到小...

为什么要学Kruskal重构树 有时候，题目让我们多次求一个图的两点路径上最小值最大/最大值最小是多少。这种时候，根据一个比较显然的结论，我们可以把问题搬到一颗最小/最大生成树里面去做。 这个时候，我们当然可以倍增来搞这个问题。但在这里，我想向大家引入一种新的数据结构，它是基于kruskal求生成树的算法改来的，因此被称为Kruskal重构树。 什么是Kruskal重构树 这张图可以一目了...