如果前面的是怪物题，那这个是克苏鲁题，不可名状，只能感性理解。 什么逆天东西啊喂！ 首先我们得先看懂题，注意 Torus 指的不是球，他实际上你硬要画出来是一个…甜甜圈。 但我们还是在矩形纸上考虑问题吧，不然太难描述了。 我们可以把他假想成，一个无限延伸的平面，上下左右都复制当前纸，这样直观一点。 好的，我们想象一下，一个环可以长什么样。 他首先不能在纸上是一个圆对吧这样切了就爆了。 他能是怎么样的？他肯定至少要能穿过边界对吧，然后呢他这个要求联通，等价于说你要按照这个环切了之后呢，存在一个连通块，满足他进行在 $x$ 和 $y$ 上都进行类似 mod 的操作重叠在一起后覆盖了整个矩形。 或者本质一点，他应该是，所有的连通块，全等？？？ 我感觉是这样的。 然后我们发现他实际上画在这个无限平面上呢，是类似一堆这个同一个方向的线，类似平行，但是可能扭来扭去。 显然我们可以在无限平面上任意平移这个我们考虑的矩形。 然后显然我们根据拓扑原理，你是直的是弯的的是根本不重要的，你只要交点结构一样即可。 你交点的这个位置是不重要的，重要的是你交点在整个图形中的层次与地位。 然后你发现就非常多的画环的方式都是等价的，比如一个横线是一个等价类，一个竖线是一个等价类，一个对角线也是一个等价类。他们的特点都是可以通过连续地平移矩阵，或者连续地扰动这个路径得到同一个地方。 然后我们有一个非常重要的感性理解，就是其实像比如说无论是横的啊，竖的啊，对角线的啊，还是缠两圈的对角线啊，甚至自己跟自己交错的神秘斜线。他们本质相同。我们都可以通过旋转和缩放我们所观测的这个矩形来发现，比如一个对角线，你给他转一下再缩放一下，对角线就变为竖线了。因此我们可以选择最简单的横线和竖线思考问题。 然后我们可以开始思考问题了。是的现在才开始思考问题。 我们注意到，如果等价类 $\ge 3$ 个，那他们必定共点。 不然因为你不能边相交，三个拓扑上方向不同的一定会围出我们不想要的环。 然后我们发现这等价于仙人掌上所有环共点。 我们试图构造，发现这是好构造的，你就钦定一个中心点，然后向外辐射即可。 只要满足这个条件就是 Yes。 显然剩下的树你随便挂在一边即可。 如果等价类 $=2$ 个，那他们要么共点，要么其中一个等价类只有一个环，且与其他所有的环相交。 理由同理，如果共点的话我们在第一个情况就算过了，不用管。 如果是一个等价类只有一个环，且与其他所有的环相交，这相当于一个川中间画了一横。 然后这个东西你发现你可以看成是，仙人掌上的所有其他环都挂在一个特定的环上。 这个也是好判的，你记 $i$ 在 $c_i$ 个环里，你只要看 $\sum c_i = sz+cnt-1$ 即可。 然后如果只有一个等价类，我们发现他一定得是一堆竖线，然后一个横线段（不是横直线）贯穿。 这等价于所有的环都挂在一条链上，你建出圆方树进行简单的树形 DP 即可。 然后我们终于理解完了这个题目。但也只是理解，至于证明？ 我们伟大的信息学，不需要证明。

非常非常厉害厉害的题目，总算是自己做出来了个厉害题。 首先显然正难则反。 嗯。我们一个想法呢，是说，我们可以按点分类，分成 A 点：连接 1 2 的点，B 点：1 3, C 点：2 3, X 点：1 2 3, O 点：无。 然后呢，我们想一下啊，我们发现我们只要把 ABC 中不同的两个点，连起来，然后就一定是一条合法路径。 当然这个有 corner case，就是如果是个三元环，那就爆了。 为什么呢？因为两点都连有不同的两种颜色，所以满足。 所以似乎这个如果有 ABC 点的话，那只能有这一种，换句话来说只能有两种颜色。 好的，然后 X 点同理，你发现，这个如果有 X 点似乎其他必须得是 O 点。 然后你写完发现样例过不了。 为啥呢，因为 corner case。 然后你很容易发现，我们如果是 X 点的情况，因为 corner case，我们如果两个不同颜色的边连到了同一个点双里，那就爆了，因为会形成一条路。 然后另一种情况就是，你根本没有 X 点，你可能是有一堆奇奇怪怪的三元环（如样例 1），他因为俩点接到同一个点上了，所以爆了。 然后你怎么着一下，然后就把这个情况全部判掉，然后就过了。

怪物题目。 我一直在想正着做，然后就爆了。 我们考虑反着做。 首先你解放一条边，显然这条边一定得是红蓝边重合。 然后你解放倒数第二条边，然后你发现他一定得是红蓝边分别连接了两个相同的这个解放块。 然后你发现你相当于是合并解放块的过程。 然后你干脆啊，直接就给他启发式合并，把整个块变成一个点，然后他就相当于要求红蓝边是重边。 显然因为两个是树，所以呢你根本不用区分哪个是红边哪个是蓝边，直接找重边即可，因为树不可能有重边。

广义串并联好题。 首先我们看到 $m \le n + 13$ 这个就是广义串并联。 其次，对于这种东西，我们可以把点双搞出来，这个简单路径的限制如果是难点可以用点双解决。 首先肯定不可能出点双再进来。 你考虑我们发现如果 $1$ 和 $n$ 不在一个点双以内，那我们直接就连一条 $1,n,L$ 的路径显然不会更改答案。 所以我们直接考虑它点双。 好的然后我们既然用的是这个广义串并联，我们就要考虑 $K_4$。 然后你发现，如果有这个 $K_4$ 就一定存在 $>L$ 的路径。 然后我们知道他是广义串并联，然后我们缩图即可。 而且注意到 $1$ 和 $n$ 是可以不缩的，如果不缩导致不行说明也是不行的（类似 $K_4$ 的分析） 重边显然是要 check 边长短。 二度点显然把两个长度加起来即可。 这个告诉我们的就是说这个 VCC 非常的好用在简单路径中。 以及这个广义串并联看到部分分就要想到。 或者更本质的来说，你如果是要搞类似这种就是一排排过去，长得跟毛细血管一样的，那就是可以试试广义串并联。

唐唐题。 考虑直接开导！ 我们很容易发现我们画在图像上，我们一定是优先节省这个费用最大的东西。 然后我们把每次增广的这个流过去的流量与每流一次的代价啥的都算出来。 然后直接贪心即可。

很厉害的题目。 首先我们知道他是网络流。 怎么流呢。 其实最重要的呢，是这个条件如何刻画。 我们要把这个条件转化为什么东西来进行这个刻画。 一个 native 的想法是，你列成一个矩阵分别是当前阶段的这些位置和当前时间，然后像网格图一样穿起来。 但你发现这样是完全不可行滴！因为你根本不知道每个位置现在是什么数。 然后我们发现一个重要的观察，你要么是从上一个同一个数那里继承，然后就一直从那个时候一直霸占这个位置，要么呢就是现在开始，踢掉一个并放进去。 还有就是，你发现关心这个具体是哪个位置放的是哪个数是十分愚蠢的，我们发现他只是一个霸占的过程，在你霸占的过程中呢你可以直接看作这个位置消失了，那你根本不需要知道哪个位置放的是哪个数，你只要知道有多少个位置被霸占即可。 然后你发现你变成了，给一堆区间，然后你可以选一些区间（即霸占他们）并获得一些受益，但同一个时间不能选很多区间。 然后这个就是经典模型，从 $1$ 到 $n$ 穿起来即可，容量为 $m-1$，代价为 $0$，然后在旁边接一些边，容量为 $1$ 费用为 $-w$，可以把这个流量引到旁边去表示你用了这个区间。 注意我们同时只能有 $m-1$ 个被霸占，因为你每次还要放一个数进去。 注意 $s,t$ 可能重合，有可能会死循环，注意特判或者多拉一条边。

十分厉害的题目。 我自己其实是想到了一个方法，但感觉十分的模糊，并不是很会实现，于是大学习了水球老师的做法。 我自己的方法： 首先啊这个行和列显然是可以随便调换的，所以我们把行按照 a 小到大排序。 我们核心思想是每一行的这个每个颜色都一定是连续的，不可能出项两个颜色相同的连续段在同一行。 然后我们第一行按顺序直接填。 从第二行开始像扫描线一样。我们可以在块与块的交界处出现新块，部分覆盖块但不能严格包含（即两边都超过）原来的块。 然后你发现对于竖向的 b 最小的就是块动的最少的，b 最大的就是块更替最频繁的。 这个你可以通过对 b 做差分得到，但实现我并不会实现。 接下来讲水球的做法。 这个是另一条路线。 我们考虑一个一个把数填进去。 于是我们立马得到了结论：如果一行内有与他颜色相同的但列内没有就只会增加列，如果行列都有则不会改变，如果行列都没有则都会加。 然后我们就非常 clear 了。 我们考虑直接填，每次看剩的 $a,b$ 来填。 然而我们发现我们如果剩一些空格就很难办了。 于是我们先想下如果有空格怎么办。 我们肯定希望我们填空格根本不影响任何的 $a,b$。 那我们直接给每行每列都来一个普适的空格值，填在对角线上。 好的接下来我们肯定贪心地先把 $a,b$ 都有的消耗掉即可，这个是好做的，你直接用全新的颜色即可。 接下来剩一些单独的 $a,b$，我们直接使用对应行内用过但列内没用过的。 怎么选呢，你发现首先普适色肯定不能选，我们实际上可以在对应行内用过的颜色里随便选一个，因为其他的我们都填的是全新色，而我们没填当前格所以列里面肯定不会有我们用的这个色。 实现上我们可以在全新色阶段直接给对应的行和列贴上一个标记色即可。 这样是好做的。 这个题目告诉我们碰壁了就换路线。

厉害厉害厉害！ 就是在面对这类的排列的题目，尤其是排序类，一个非常重要的方向就是从图理论出发。 非常经典的就是 $i\to p_i$ 建边，然后每次交换就是可以合并两个环或者拆开两个环，目标是 $n$ 个自环。 然而在这里你发现首先你这样连会导致 $O(n)$ 个边的变动，不可取，我们希望有常数级别的边的变动。 然后一个 native 的想法是你考虑 $p_i\to p_{i+1}$。于是我们得到了一个下界，大概是与目标图的不同边的数量除以 $4$ 向上取整。 但我们很容易发现这个下界相当的松，构造十分的困难况且我们还能举出反例，我们需要一个紧一些的下界，而且另一个原因是，这个链的形状我们实在是不太好刻画，这个链的信息实际上蛮多的，这也是导致下界很松的原因之一。 我们想要的是环，最好是数个数，但正常的方法不行了，怎么办？ 这个题目牛逼的来了，他指出：我们可以 $p_i + 1\ to p_{i+1}$。 注意这个是在排列前后添了 $0,n+1$ 的情况下。 我们发现他本质上来讲，是把一条链，进行了错位，把链变成了自环。 其根本思想在于，我们可以通过改变连边方式本身来改变图的性质。 这确乎是一个范式的突破。我们的图理论与排列理论相结合，不再拘泥于那一种的连边方式，而是我们可以尝试多种的，不同的，适配每个题目性质的连边方式，这是前所未有的。 我做这个题目的时候就卡在我根本没有向这个地方想，被这个集体无意识给禁锢住了。 一个顺畅的思考路径应该是想到 native 的想法后想到这个链化为自环然后做完。 这个连边方式跟这个题目的性质有什么适配性呢？这还得从 $i\to p_i$ 说起。 我们说到，这个东西最大的问题在于，他需要更改 $O(n)$ 个，而其根本是他是对段进行操作。 然后我们自然地想到这个我们要把段转化为单点，自然是使用差分。这是差分思想的一种灵活运用。 我们发现我们可以让每个连边关联于他前后的东西，我们最好是希望在进行一系列操作之后，中间的影响恰好被抵消掉了，我们不用管。 然后我们想着要把 $p_i$ 和 $p_{i+1}$ 关联起来，既然如此，我们 $p_i\to p_{i+1}$ 如何？ 这就诞生了我们的链。 但我们想要的是环啊，于是我们就把他挪一下，让最终图全是自环。 我们注意到，原图是不重要的，最终图是重要的。 然后变成了 $p_i + 1\to p_{i+1}$。 然后我们发现这个题已经做完了一大半。 我们发现我们每个操作本质上相当于交换对应的两个对这个出边，自然也就是最多多出现两个自环，且奇偶性一定不会变。 我们发现这个下界紧得多，我们试图构造。 我们发现我们本质上就是要每次多两个自环，也就是多两个 $x\to x+1$,$y\to y+1$。 然后我们不难这样构造：我们找到第一个前面有比他大的东西的 $x$，再找 $x$ 前面最大的 $y$，然后你发现 $x-1$ 在 $y$ 前面，$y+1$ 在 $x$ 后边，然后我们按顺序这样拼一下，把 $x-1\to x$ 拼起来，$y\to y+1$ 拼起来即可，不难发现在没排序的情况下总是能找到的。 ...

今天是五一节。 它本来应该是平凡的一天。 中午妈妈问我今天要不要出去逛逛。 我不得不答应。 我反常地开始想晚上吃什么。 烤肉我吃过好多次了，只有第一次是好吃的，后面的每次我总是抱着能像第一次一样好吃的幻想，结果总是落空。 我想吃牛排。 我说：我想吃牛排。 妈妈说：最近牛排好贵，我们吃烤肉吧。 好吧。那吃烤肉吧。 然后到了晚上了，她拉着我去一家商场里面。 整个商场我看到的全是饭店，而且个个看起来都比牛排和烤肉好吃。 我们走进了一家烤肉店。 整个烤肉店勾起了我以前吃的不好吃的烤肉的回忆。 妈妈问我我要吃什么，我说你知道我要吃什么，但她反常地让我自己选。 然后我拿着盘子，不知道选什么。 她说都拿一样，试试哪个好吃。 我照做了。 然后开始烤肉了。 我把我拿的全吃了一遍，除了烤面包没有合我胃口的。 然后我开始刷手机。 妈妈说：这样你吃点甜点，面包之类的吧。 然后我拿了两片面包，一边看手机，一边吃面包。 面包吃完了我又拿了两片。 我不记得我拿了多少片了，我只记得我拿了好多。 然后不知道什么时候，妈妈说：该走了，你吃饱了吧。 我视频还没看完，于是我说我没吃饱。 过了一会儿，她说你现在总吃饱了吧。 尽管视频没看完我还是得说我吃饱了。 妈妈说：我们回家吧。 但我反常地想试着逛逛商场。 然后我就带着妈妈一路乱走，一路路上，却全是些服装店，饰品店。 妈妈今天怎么这么不对劲。 换作以前，我如果拉着她乱逛，她可能就发毛了。 我想上厕所了。 但我转了半天没找到厕所。 妈妈说：那我们回家上厕所吧。 我不得不答应。 在找电动车的时候，我说：妈妈，你今天好像跟以前不一样。 她说：怎么啦，你想干什么就干什么呀。 到一半的路上，她说：反正这么近，几分钟，我们明天再来吧。 我急了。 我还没去那些满眼的饭店里转转。 而且我明天不想出门。 我说： 你不是说我想干什么就能干什么吗，我现在想去逛街。 我命令她掉头。 但她一直重复说： 很近，明天再来吧。 我想哭。 到家了。我打开了电脑。 电脑里响起了我单曲循环了不知道多少遍的 hypertrance。 我扑到了我的被子上，多么的柔软。 我哭了。 我总是幻想着我能变成尼采笔下的超人， 浑身都是欲望， 但我是蛆。 连食欲都没有。 也许每天喝着营养液维持生命体征的生活更适合我。 也许像花角那样的原子人生活。 整天带着 kig。 每天只要写写代码，做做音乐。 的生活。 更适合我。 我爱那样的生活。

又一个神仙构造题。 对于第一个小问，相对是简单的。 首先 $O(nm)$ 是唐的，你枚举结尾然后暴力跑。 一个 native 的想法是你考虑找一棵树然后换根，然而你发现你并找不出来一棵这样的树。 然后你考虑奇怪的方法，我们发现这个是可达性，然后试图使用 bitset 然后发现做完了。 你直接每次按顺序用 bitset 模拟即可。 对于第二个小问，有点困难。 一个 native 的想法是你考虑钦定两个终点，然后画在图上需要你做一个割出来把点割成两边，但实际上这很困难。 另一个 native 的想法是你直接考虑钦定一个线从头到尾一点不动，其他的方向尽量远离这条线，这实际上大部分情况下是可以的，但完全图会出问题。 然后我们参考一下题解。 首先 $n=2$ 爆了。 你发现你还是从后往前，不过是类似于把一股线编织起来，然后呢你记录这个每个线最终到哪里，以及每个终点汇聚了多少线。 然后你就很神奇的，你直接瞎搞，直到你发现如果你再把这根线会进去（因为你是从后向前，所以他合并的是一个根在右边的树，最左边的线头都只有一根）会直接导致答案合法，然后你就临时抱佛脚把这个方向转一下。 结果你突然发现这样是对的，因为这个不可能两个线头都是 $n-1$。 然后就很神奇的做完了这个题。 这么看来其实这个不合法的条件是相当松的，不过因为这个题目本身的原因，这个解空间的形状奇特，导致找到一个普适的方法变得困难。