Solutions

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

很厉害的题目。 首先我们知道他是网络流。 怎么流呢。 其实最重要的呢，是这个条件如何刻画。 我们要把这个条件转化为什么东西来进行这个刻画。 一个 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$ 拼起来即可，不难发现在没排序的情况下总是能找到的。 ...

又一个神仙构造题。 对于第一个小问，相对是简单的。 首先 $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 的时候算一下两边的贡献然后额外把少算的贡献算上即可。