题面 传送门：洛谷 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作为关键字二分？也布星啊。 那咋搞啊？ 不如，我们换个想法，我们把其中一个关键字枚举，再看在这个关键字的限制下，另外一个尽可能小。 仔细想想，应该是能覆盖到所有的情况的。 所以说，我们...

题面 传送门：洛谷 Solution 首先，长成这样的题目一定是淀粉质跑不掉了。 考虑到我们不知道K的大小，我们可以开一个splay来统计比某个数小的数的数量。 不会点分治的戳我 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545...

什么是淀粉质点分治？ 就是把分治搬到树上，以某个点为根，分别分治处理子树的答案，再计算子树与子树间的答案的玄学算法。 举个例子： 如何求出一颗树上距离为K且所经过的点最少的点对？ 对于这种题，我们可以把某个点（一般为重心）作为根，然后对左右子树递归处理，先分别得出左右子树的答案，再求出横跨两个子树之间的点对的答案。 为什么要学淀粉质 对于上面那道题，如果我们用传统的暴力做法，最优的复杂度只能...

DAY 1 8：30 总算拿到题目啦！ 打开题目一看，T1T2T3全部512MB，1s，没有什么特别奇怪的时间限制的题目，题目应该可做(吧)。 8：32 啥废事都没做，直接开T1。 等等。。。。。。等一下下 这熟悉的题意。。。。。。 这不是神TM的积木大赛原题吗？ 直接5min消灭，过了大样例，稳如老狗。 8：37 快速过了一眼T2,T3。T2好像不怎么可做，想了5分钟只会一个a^n的10分...

什么是裴蜀定理 裴蜀定理（或贝祖定理，Bézout’s identity）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约 数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且（a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。 ——百度百科 用人话来说就是： $\sum a_i*...

什么是边双？ 双连通分量又分点双连通分量和边双连通分量两种。若一个无向图中的去掉任意一个节点（一条边）都不会改变此图的连通性，即不存在割点（桥），则称作点（边）双连通图。一个无向图中的每一个极大点（边）双连通子图称作此无向图的点（边）双连通分量。求双连通分量可用Tarjan算法。——百度百科 用人话来说，就是在无向图上以边为关键字，对原图缩点 为什么要学边双 与强连通分量类似，我们可以求...