Solutions

又一个神仙构造题。 对于第一个小问，相对是简单的。 首先 $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$ 为边界个数。 ...

以下假设 $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 的时候算一下两边的贡献然后额外把少算的贡献算上即可。