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

题面 SDOI2009 学校食堂 Solution 这是一道状压妙题。 首先，因为后面的东西能提到前面来做，导致了严重的后效性。为了消除这个后效性，考虑用状压来处理这个问题。 我们可以发现最多的提前量很小，只有7，考虑这样设： 设$f[i][j][k]$表示$[1,i-1]$已经完成了，从$i$开始往后7个的完成状态为$j$，上一个完成的相对$i-1$的位置为k。 转移比较正常：我们枚举一...

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

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

题面 洛谷P3174 Solution 我们不难发现，一条“毛毛虫”一定是由一条主链外加主链的点所连到的点构成的。 那既然是一条链，它的形态无外乎以下两种： 因此，我们可以直接枚举最上面的那个点，他做为根会产生的最大的答案即为其孩子的最大答案与次大答案之和再减去多算的一小部分即可。(具体转移可以看看代码，要做点简单的分类讨论) 时间复杂度$O(n)$ 就酱，这题我们就切掉啦(*´ﾟ∀ﾟ｀...

题面 洛谷 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重构树 这张图可以一目了...

题面 洛谷P3567 Solution 大水题啊，真没什么好讲的 我们考虑建一颗权值主席树，从左往右逐个插入。因为个数满足可减性，因此我们可以很方便的“扣”出$[L,R]$区间构成的主席树。接下来只需要在树上二分看一下有没有出现次数超过$K$的即可。 时间复杂度$O(nlogn)$ 就酱，这题就被我们切掉啦︿(￣︶￣)︿ Solution 123456789101112131415161...