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

题面 洛谷P4197 Solution 这题的确是可以用库鲁斯卡尔重构树+主席树来搞，但是本蒟蒻太菜了并不会，因此只能给大家讲讲离线+splay启发式合并的搞法。 首先，我们考虑把询问离线下来并按限制从小到大排序。然后我们可以考虑把边一条一条插入到图里面去，直到某个询问的限制。这样子，问题就变为了询问某一个连通块的K小值，连通块可以合并。 这个问题就肥肠简单了，我们可以用各种各样的数据结构...

题面 洛谷P3302 Solution 拿到这道题，我们不妨先想一下静态的树上K大怎么搞。 静态树上K大有两种办法，一是树链剖分+平衡树，二是主席树做链前缀和。前者的复杂度是$O(log^2n)$的，而后者只有$O(logn)$。 我们考虑把数字全部离散化，然后开权值主席树，每颗主席树记录从它出发到根的路上每个数字出现了多少个。接下来，我们只需要找到LCA。因为数字出现个数满足可减性，因此...

为什么要学左偏树 有时候，某些题目要求我们合并两个堆。 合并两个堆，大家都知道可以用splay暴力启发式合并处理。很不幸的是，这玩意的复杂度是$O(nlog^2n)$的，在一些毒瘤题目专门考可并堆的题目中，是注定要被卡的。 可并堆系列算法可以很优雅的解决这系列的算法，她们可以在$O(nlogn)$的时间内处理两个堆合并的问题。而我现在要讲的左偏树就是可并堆中的一种。 什么是左偏树 正如她字面...

题面 洛咕 Solution 题目要求求出区间众数，强制在线。 区间众数是一个比较尴尬的问题，我们无法用区间数据结构来处理这个问题，因为我们没法很好的合并区间众数的答案。 既然区间数据结构解决不了这个问题，我们可以考虑一下使用基于分块的算法，例如莫队。 这题用莫队非常好处理，不幸的是，这题要求强制在线。 因此我们考虑使用分块算法。 分块算法的核心在于把一整个块的信息压缩起来以便快速处理。 ...

题面 传送门：洛谷 Solution 一开始我看到pty巨神写这套题的时候，第一眼还以为是个SB题：这不直接开倒车线段树统计就完成了吗？ 然后冷静思考了一分钟，猛然发现单纯的线段树并不能解决这个问题，好像还要在外面再套上一颗树。 这就很shit了。你问我资磁不资磁树套树，我是不资磁的，树套树是暴力数据结构，我能资磁吗？ 很不幸，昨天现实狠狠地打了我一脸：时间不够开新坑的，不切题又浑身难受，...

题面 传送门：洛谷 Solution 这题其实是有类似模型的。 我们先考虑不修改怎么写。考虑这样做：每个点向它跳到的点连一条边，最后肯定会连成一颗以n+1为根的树（我们拿n+1代表被弹出去了）。题目所问的即是某个点到树根的链的长度。 那么，如果我们加上修改，显然，某个点连向的点会发生改变。对于一个能修改边的树，我们可以很自然的想到用LCT维护之。 至于怎么求某条链的长度呢？这也是LCT的基...

题面 传送门：洛谷 Solution 这题… 我们可以发现题目要求我们维护一个动态森林，而且只查询连通性… 显然LCT模板题啊，关于LCT玩法，可以猛戳这里学习 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859...

为啥要学LCT啊 在开坑之间，我们来先看一段对话： Q：给你一颗森林，现在不断的连接森林中的两棵树，保证不连出环，多次问你某两个点的连通性？ A（dalao&蒟蒻）：这不是SB题吗？显然并查集水过啊。 Q：说的好，但是如果我要删除某些边呢？ A（dalao）：那就可持久化并查集啊，你的问题怎么那么水。 A（蒟蒻）：…（发出gg的声音） 这时候，如果我们并不想写可持久化并查集的话，就得...

题面 传送门：洛谷 Solution 这题的思想挺好的。 对于这种最大值最小类的问题，很自然的可以想到二分答案。很不幸的是，这题是双关键字排序的，我们怎么二分呢？ 先二分a再二分b？怎么看都布星啊。 那a+b作为关键字二分？也布星啊。 那咋搞啊？ 不如，我们换个想法，我们把其中一个关键字枚举，再看在这个关键字的限制下，另外一个尽可能小。 仔细想想，应该是能覆盖到所有的情况的。 所以说，我们...