Construction

牛牛题。 首先你把答案 reverse 一下，就是指定一个根，然后每次扩展一个相邻于当前连通块的点。 先考虑如何 check。 首先一个 native 的想法是考虑两种方向相反的 DFS 序。 然后你发现一个菊花图就把你 hack 了。 然后另一个 native 的想法是用两个根这样做。 但实际上你通过跑一下你发现还是会出问题，然后你看一下相同的两棵树，你发现他们一般动一两条边，然后他们分别连的都是同一连通块。 这启示我们从一个点连到哪个点进行考虑。 我们注意到我们根据一个拓扑序来构造一棵树的话，本质上你是把每个点选择一个前面的点挂上去。其实跟整个树的结构无关。你只关心每一步了连到了哪个点。 然后我们就想，如果对于两个拓扑序来讲一个点都能挂到前面的两个点上，那是不是就不唯一了呢？这个感觉是非常对的。 形式化的来讲，你对每个 $i$ 都找出 $i$ 在每个拓扑序中的位置，然后把前面的所有数的集合交起来。如果存在一个 $i$ 使得该集合大小超过 $1$ 则不合法。 然后你趁洗澡的时候对拍，然后回来发现拍了四万多组了都没出问题，就把他当对的了。 然后接下来的思路，你灵光一现，想到我们其实不怎么关心是怎么遍历的，我们关心的是从哪个点开始遍历的。 然后我们就想一条边他是怎么被经过的。然后你发现除了连接叶子的边其他边都要被正反经过一遍。 我们把叶子剥了，把每个里叶子都作为起点扫一遍就能做到。（这个显然是下界） 然后我们发现这个图的性质很优雅。我们发现这样一并把原来的性质满足了。 但我们还要考虑叶子怎么放置。我们发现我们直接紧贴着放在里叶子的后面即可。因为你发现这样一定不会重。 然后就做完了。 啊？ 等等，然后怎么做答案呢。 直接做即可。 我好厉害。 你发现你输出解会有点问题。 但不慌，你扰动一下，你每次把 $G$ 翻转一下。 然后就过了！！！

十分厉害的题目。 我自己其实是想到了一个方法，但感觉十分的模糊，并不是很会实现，于是大学习了水球老师的做法。 我自己的方法： 首先啊这个行和列显然是可以随便调换的，所以我们把行按照 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$ 拼起来即可，不难发现在没排序的情况下总是能找到的。 ...

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

看错题了，我一开始没看到要求最小化那个不同种类数，但我也做出来了。 我想的就是研究这个性质，首先设原序列是 $a$，gcd 序列是 $b$，然后你发现我们一定要求 $lcm(b_i,b_{i+1})=a_{i+1}$。 然后呢你找 $b$，然后你发现如果 $p|b_{i-1},p|b_{i+1}$ 于是 $p|b_i$，$(b_{i-1},b_{i+1})|b_i$。 然后你发现这个是充要条件，然后一个构造就是 1 n/2, 2, n / 2 + 1…..。 然而这样没有限制最小化不同种类数，但无论如何这个性质还是蛮厉害的。 然后回到正题，你发现你看错题了。 然后我们想着这个既然要最小是吧，那我们就直接想一下最小是多少，显然是不能小于 $k$ 满足 $k$ 个点的图的欧拉路径长度等于 $n$。 然后你试图构造发现你不会构造。 你乱搞一波，然后发现 easy version 可以 $2^i3^{m-i}$。 然后你发现你如法炮制，$2^{i}3^{m-i}5^{j}7^{k-j}$。 然而你发现你这个对应交换 $i,j$ 也会被判为相同。 然后你发现你还剩了蛮多位置。然后变成 $2^{i+j}3^{i}5^{m-i}7^{j}11^{k-j}$ 即可。 注意欧拉路径写法，不要像我一样 wa 十几发。

很清奇的构造题，以前似乎从来没见过逼近这一块的构造，而且这还是逼近无理数，我说实话开始有点懵。 这个题你如果事先知道连分数理论的话应该是相当简单的。 首先串联是电阻相加，并联是电阻的倒数相加再倒数。 然后一个很厉害的放缩就是你考虑每次在原电路上串联或者并联一个电阻。然后这个时候你发现他会让分子加上分母或者分母加上分子。 这就是 Stern-Brocot 树啊，然后你发现把整个连分数理论套上去基本上就做完了，你直接在 Stern-Brocot 树上二分，然后很容易通过连分数理论证明精度是足够的。 这个题其实就是科技题吧，学会科技就好做了。 Continued Fraction Theory

神啦兄弟神啦。 逆天构造拼尽全力无法战胜。 明明想出了所有的结论，却仍然不会构造。 我们称左上右下为 A 区，左下右上为 B 区。 结论 1: 一个三角形可以被放入矩形当且仅当没有连续上升或连续下降。换个说法就是有 2 个点的两条边在不同区。 这个显然，手玩即可。 结论 2: 一定不会有一个点被包含在三角形内。 如果这样的话可以通过把原来那个三角形删了并通过手玩发现至少获得两个三角形，一定更优。 结论 3: 答案图一定不会有两个分开的三角形连通块。 如果 P 和 Q 在横坐标或者纵坐标上有交叉，那直接去交叉的那个点，然后在另一侧取两侧的两个外围点组成三角形就联通了。 如果整个 P 在 Q 左下角，那取 P 的一个点然后取一条132形三角形（一个多边形一定有逆序对）然后再把其包含的点像 2 一样塞进去即可。 结论 4: 一个点如果周围被三角形挤满，那一定四个象限都有边。 假设没有，那就有一边是不符合条件的三角形。 结论 5：一个多边形的坨坨子里面不会有空。 这个十分大便，你就分讨吧，然后会发现这个是对的。 结论 6：前缀最大值最小值后缀最大值最小值一定在边界上。 因为你不可能在里面啊，你在里面与 4 矛盾，然而又不能在里面空出来，这样与 5 矛盾。 然后呢一个 native 的想法是增量构造，你直接把能连的都连上。 然后你如果是 acm 赛制你一发交上去然后你发现你通过了。 但我们是 oier 不是 acmer 我们不能这样，我们不能瞎猜，得有理有据的推。 然后你发现推不出来。 好的。然后这个逆天构造干了个事情。他宣称答案就是以前缀最大值前缀最小值后缀最大值后缀最小值为边界组成的坨坨子，并且内部通过单调栈来进行分配。 这实际上就是增量构造构造出来的东西。但这个东西十分的吓人，你哪知道这个为什么是最优的，感觉一眼看上去是完全没有这个道理的。 然而你发现你不知道一个叫作平面图欧拉定理的东东：$V+F=E+1$（此处 F 不包括最外面那个平面）。 其实是忘了。 然后你发现我们直接构造出来的东西的这个三角形数算一下为这个 $2V-P-2$。$P$ 为边界个数。 ...