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

又一个神仙构造题。 对于第一个小问，相对是简单的。 首先 $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 树的形式出现，我感觉这种方式更好出 oi 题。 例题：Square Resistance Value 贴上 DeepSeek 的讲解： 连分数是一个被严重低估的数学工具。它用一串整数编码一个实数，并且这串整数直接给出了该实数的最佳有理逼近序列。下面我从定义开始，逐步推进到关键性质、证明，最后给出你想要的概括。 1. 什么是连分数 一种最常用的形式是简单连分数（Simple Continued Fraction）： 对于实数 $\alpha$，令 $$ \alpha_0 = \alpha, \quad a_0 = \lfloor \alpha_0 \rfloor $$ 然后递归定义： 如果 $\alpha_n$ 不是整数，则 $$ \alpha_{n+1} = \frac{1}{\alpha_n - a_n}, \quad a_{n+1} = \lfloor \alpha_{n+1} \rfloor $$ 这样会得到一个可能终止的整数序列 $a_0, a_1, a_2, \dots$，记作 $$ \alpha = [a_0; a_1, a_2, a_3, \dots] $$ 其含义是： $$ \alpha = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \ddots}}} $$ ...

很清奇的构造题，以前似乎从来没见过逼近这一块的构造，而且这还是逼近无理数，我说实话开始有点懵。 这个题你如果事先知道连分数理论的话应该是相当简单的。 首先串联是电阻相加，并联是电阻的倒数相加再倒数。 然后一个很厉害的放缩就是你考虑每次在原电路上串联或者并联一个电阻。然后这个时候你发现他会让分子加上分母或者分母加上分子。 这就是 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$ 为边界个数。 ...

以下假设 $n,m$ 同阶。 很好的题目！ 第一个重要的观察就是，这个操作的顺序显然是不影响这个答案的。 我们想到我们不能直接去进行这个操作，因为他涉及到 $O(n)$ 个点，就算再怎么维护，都是困难的，我们要把他压缩一波。 我们要把这个信息最好是压到 $O(1)$，但在没有预处理的情况下有些困难。 我们先不考虑查询，我们直接考虑给一堆修改，你怎么小空间地干这个事情。 首先明显的想法是，这个前缀加有点太蠢了，考虑差分一下，变成单点加，后缀最大值。 然后你发现你可以把调换两维啊。既然你这个单点加的顺序没有关系，那我们就直接从后往前考虑，刚好算得就是后缀最大值。 然后你就变成了，把这些操作呢按照以 $x$ 为第一关键字从大到小，以 $y$ 为第二关键字从小到大排序，依次考虑，于是你发现你根本不需要考虑 $x$ 的问题，你直接把排完序后的 $y$ 求一个前缀最大值就可以了。 这个时候你发现前缀最小值这个东西是好东西！他可以看作是一个半裙元素，可以简单地拼接，且信息量为 $O(1)$。只需记录内部前缀最大值，以及总和，即可方便地合并。 然后我们到了这个序列上呢，你发现你还是要把区间排序，这个事情难做的，因为你至少要根号 log 的复杂度。然后考虑你干脆先排好序，然后在排好序的序列上找 $i\in[l,r]$，把这个子序列拿出来即可。 然后就出现了一个 KDT 的做法，你考虑类似整体二分一样，把所有询问一起做，从后往前扫一遍，考虑每个点对每个询问的贡献，画在二维平面上，就是矩形加上一个半裙元素，使用 KDT 做到 $O(n\sqrt n)$。 但是呢，KDT 常数太大了，于是我们考虑其他做法。 我们考虑分块对吧，然后呢我们想想对什么分块，对扫描的东西？还是原本的下标？ 原本的下标的话，你发现仍旧是退化成了一个你要往里面加东西，而这个你加一个至少要 $O(\log n)$，不可取。 我们对扫描的东西分块，我们就发现我们直接在每个块里面算即可，合并块之间是好合并的，你对每个询问来讲，你如果知道了每个块内部的东西，那合并起来，直接把所有的信息加在一起即可。 我们考虑如何计算一个块内所有下标在 $[l,r]$ 内的答案。 我们突然发现这个块内的元素只有 $O(\sqrt n)$ 个啊！那你不是总共只有 $O(n)$ 种可能的本质不同询问，那你直接把所有的算出来就可以了，至于把原询问映射到小询问上，这个是简单的，直接离散化。 我们问题转化为了，给定长为 $n$ 的序列 $a$ 和半裙元素序列 $b$，要求在 $O(n^2)$ 的时间复杂度内求出对于每个 $[l,r]$，满足 $a_i \in [l,r]$ 的 $i$ 的子序列的 $b$ 的和是多少。 我们一招鲜吃遍天。既然我们都搞的是本质不同询问，那你再搞一次，用 TB5？ ...

看到子串出现类直接套上一个 SAM。 然后非常套路地使用线段树合并来维护子树的 endpos。 我们的限制即相当于是，给定一堆长度相等的线段（存在线段树里），然后要你算多少种方案插两根针不会把所有线段全部插到。 我们考虑正难则反，考虑多少种会把所有插到。 然后我们再转化，考虑一根针能插到的线段的起点位置是一个线段，即我们要选两个定长线段覆盖所有点。 这个问题简单多了，我们设第一个线段的末尾是 $x$，另一个的开头是 $y$。 我们先假设两个不是线段，我们假设要用 $[-\infin, x]$ 和 $[y,\infin]$ 来覆盖所有点。 二元限制我们画成图，容易发现满足条件的 $(x,y)$ 点对是一个右下角的，阶梯状面积，其中凹点在 $x=y$ 上，且凹点的 $x$ 就是点的位置。 然后我们考虑两个线段的限制，他其实就是给 $x$ 设定了一个上界，$y$ 设定了一个下界，然后这样合法的仍旧是一个阶梯状。 我们考虑在使用线段树维护阶梯状的时候，我们不从横坐标维护有多少个 $y$ 满足在当前 $x$ 下合法，我们维护那个突出去主对角线的面积。 你发现这个东西是好维护的，你对每个线段树节点维护第一个和最后一个点，然后 pushup 的时候算一下两边的贡献然后额外把少算的贡献算上即可。

Test Test Test Test Test Test a #include <bits/stdc++.h> $a$ $$ a $$