Brief
NEUQ 寒假集训自主刷题记录，比较 trivival 会简记一下思路，比较困难会写解题报告或者题解记录一下。
\(\textcolor{grey}{\bigstar}\) 表示思维难度偏低、且各方面比较普通或比较套路的题（不考虑使用的算法）。
\(\textcolor{green}{\bigstar}\) 表示整体难度一般甚至偏低、但思考过程或结论可能具有启发性的小清新题目。
\(\textcolor{brown}{\bigstar}\) 表示思维难度中等的中档题。
\(\textcolor{blue}{\bigstar}\) 表示需要较高思维难度、思考过程或结论很具有启发性的题目。
\(\textcolor{magenta}{\bigstar}\) 表示需要一定知识基础和相关进阶算法的题。
\(\textcolor{red}{\bigstar}\) 表示思考了一段时间，但思考过程不完整，思路没有到位或只有部分正确，最终看题解才做出来的题。（最需要练习的题目）
1.15
做题之余，整体复习了一下数论，稍微学习了一下二次剩余和离散对数。
题目 \(01\) ：ABC336F - Rotation Puzzle \(\textcolor{grey}{\bigstar}\textcolor{magenta}{\bigstar}\) [折半(搜索)思想]
思路：考虑进行四进制状压，\(0,1,2,3\) 分别代表左上、右上、左下和右下的旋转，但是有 \(4^{20}\) 种枚举状态。注意到最终状态是确定的，而且旋转操作可逆，那就可以采取折半搜索的方法，从起始状态枚举 \(10\) 步，把状态存到哈希表中，再从末状态枚举 \(10\) 步，再从哈希表中查找，这样就只需要枚举 \(4^{10} = 2^{20}\) 种状态了。假设上限步数为 \(n\) ，则时间复杂度为 \(O(2^{n}nHW)\) ，取 \(n = 20\) 即可。
题目 \(02\) ： ABC335F - Hop Sugoroku \(\textcolor{grey}{\bigstar}\textcolor{magenta}{\bigstar}\) [根号分治]
思路：设 \(f_i\) 代表以 \(i\) 为结尾且 \(i\) 被涂黑的方案数，不难发现 \(f\) 的转移可以根据 \(a_i\) 的大小进行根号分治。如果 \(a_i \ge \sqrt{n}\) ，直接暴力每次跳 \(a_i\) 进行转移，如果 \(a_i < \sqrt{n}\) ，因为从 \(i\) 能跳到的所有位置 \(p \bmod a_i\) 一定等于 \(i \bmod a_i\) ，所以可以直接开一个二维数组记录模 \(x\) 等于 \(y\) 的位置上被加的贡献。时间复杂度为 \(O(n\sqrt{n})\) 。
1.16
研究一个与离散对数有关的题，还没研究出来，然后上午 \(11\) 点的时候被叫去给预备队出题，然后花了 \(2.5\text{h}\) 跟 ljc 和 zyb 搞了一套入门级别的题，然后下午的时候激情看榜（出了好多锅，甚至 \(\text{B}\) 题的数据还锅了，成为背锅人），最后一起写了题解。
晚上继续研究那道题，最后终于搞明白了。近期准备写一个数论学习总结。
题目 \(\text{03}\) ： ABC335G - Discrete Logarithm Problems \(\textcolor{blue}{\bigstar}\textcolor{magenta}{\bigstar}\textcolor{red}{\bigstar}\) [阶 | 原根 | 离散对数]
思路：【题解】ABC335G。
搞完这个题之后，听 zyb 说了说昨晚 div.3的 G 题，发现题有点怪，但做法很一般，那就口胡一个题解。
题目 \(\text{04}\) ：CF1921G - Mischievous Shooter \(\textcolor{brown}{\bigstar}\) [递推 | 二维前缀和]
思路：这题看着听唬人，实际上不太难想，只需要采取最普通的思路，只需要维护一下每行、每列、左斜线和右斜线的前缀和，四个方向都要跑一下类似于二维前缀和的递推，推出以每个点为端点，距离这个端点曼哈顿距离 \(\le k\) 的方格的和即可，时间复杂度 \(O(nm)\)。但是边界啥的懒得想了，感觉稍微有些难写。
又听 zyb 说了昨晚 div.3 的 F 题，据说是根号分治，但想了半天没想出来其中一边怎么分，所以打算明天研究一下。
1.17
上午写昨天的没搞完的 ABC335G 的题解，然后发现一个关键证明锅了，然后又花了一上午研究才彻底通透。
中午的时候博客出锅了，修了修 Blog，发现 hexo-renderer-kramed 和
hexo-renderer-marked 引擎渲染行间公式的时候
$$的转义有问题，离大谱。
下午听学长讲了几个构造题，挺有意思的，因为没有地方测也没有写，所以就不作为正式题目了。
一个是 lbf 学长自己想的跟俄罗斯方块有关的构造，给定一个初始局面，给一些面积为 \(4\) 的块，要求构造一些下落的方块之后回到初始局面，保证宽为偶数。想一想发现只需要开始时在最高的地方整一个反着的 \(\text{T}\) 字，然后向两端铺㇅字，之后再随机应变向上填充，刚好能填充满 \(4\) 行。
另外一个是 \(\text{ec final}\) 的一个题。就是给定两个 \(01\) 串 \(A\) 和 \(B\) ，保证两个串的首位都是 \(1\) ，每次可以把 \(A\) 的一个区间去掉前导零后看作三进制，然后转化成二进制再填回去，平均每位不超过 \(8\) 步把 \(A\) 构造成 \(B\) 。因为可以去掉前导零，所以只需要花费很少的步数把 \(A\) 串变成全 \(1\) ，然后考虑怎么把全 \(1\) 串变成 \(B\)。因为 \((11)_{3} = (100)_2\) ，\((10)_3 = (11)_2\) ，所以假设 \(B\) 中有 \(x\) 个 \(1\) ，那只需要把 \(A\) 先变成连续的 \(2x\) 个 \(1\) ，这样每次修改连续的 \(2\) 个 \(1\) ，比如 \(11 \rightarrow 100 \rightarrow 110 \rightarrow 1000\) ，即可实现把 \(11\) 变成 \(1\) 加上任意多个 \(0\) ，步数很少，目测是足够的。
晚上研究了一下昨天说的哪个 div.3 F 题，发现自己被卡在了如何优美的定义数组上，遂记之。
题目 \(\text{05}\) ： CF1921F - Sum of Progression \(\textcolor{brown}{\bigstar}\textcolor{magenta}{\bigstar}\) [根号分治]
思路：我感觉这题的难度不在于想到根号分治，其实根号分治比较一眼，我被卡在了一个奇怪的地方。当 \(d \ge \sqrt{n}\) 的时候显然直接暴力跳即可。当 \(d < \sqrt{n}\) 的时候，可以预处理。具体的，枚举每一个步长 \(d\) ，再枚举起点 \(st\) ，然后挨着跳，预处理前缀和与 \(\sum k \cdot a _{(k - 1)d + st}\) 的前缀和，这样做的时间复杂度为 \(O\left(\sum_{d = 1}^{\sqrt{n}} d \cdot \displaystyle\frac{n}{d}\right) = O(n\sqrt{n})\)。但这样问题就出在预处理的数组要开 \(3\) 维，第一维存步长 \(d\)，第二维存起点 \(st\)，第三维存跳到哪儿了，因为数组没办法根据不同的 \(d\) 给 \(st\) 开不同的长度，所以空间必须全都开满，所以空间复杂度就是 \(O(\sqrt{n} \cdot\sqrt{n} \cdot n) = O(n^{2})\) 就炸了。但其实仔细想想没有必要开 \(3\) 维，因为只要确定当前跳到的位置 \(p\) ，和步长 \(d\) ，其他能跳到的位置可以通过 \(p + kd\) 计算得出，起点自然就确定了，所以只需要开二维数组预处理即可，剩下的就没有难度了。
1.18
今天上午跟出题组其他人一起准备了下午的预备队天梯赛 \(1\) 的题，并且写了题解。
简要在这里写一下我搬的那题的题解：由勾股定理 \(a^{2} = c^{2} - b^{2} = (c + b)(c - b)\)，这启示我们去找 \(a^{2}\) 的约数。将 \(a\) 进行质因数分解有 \(a = p_{1}^{k_1} p_{2}^{k_2} \cdots p_{m}^{k_m}\)，则 \(a^{2} = p_{1}^{2k_1} p_{2}^{2k_2} \cdots p_{m}^{2k_m}\)，这一步的时间复杂度为 \(O(\sqrt{a})\)。考虑通过 \(a^{2}\) 的唯一分解，dfs 每一个质因数的指数，不重不漏地枚举 \(a^{2}\) 的约数。通过这个网站 https://oeis.org/A066150 ，我们得知 \(10^{24}\) 以内因数个数最多的数的因数个数是 \(1290240\)，所以时间复杂度可以保证，数学巨神 wrx 也给出了一个很严格的上界 \(\operatorname{d}(n) < n^{\frac{1.066}{\ln\ln n}}\)，通过这个也可以粗略计算 \(10^{24}\) 以内的数的因数个数最大是 \(10^6\) 级别。枚举约数的时候，顺便判断一下能否写成 \(a^{2} = (c + b)(c - b)\) 的形式即可，其中 \(a < b < c\)。
下午写题，晚上打了一场 Edu div.2，\(6\) 题过了 \(5\) 题，但罚时吃满了，预测上不了紫，希望不要 fst ，A 到 E 都挺简单，D 细节有点多，E 题好像还是原题。简记一下 D 和 E。
题目 \(\text{06}\) ：CF1922D - Berserk Monsters \(\textcolor{grey}{\bigstar}\) [模拟 | 链表]
思路：考虑每个怪最多只会死一次，维护一个链表，里面是当前活着的怪。维护两个 vector 分别代表这轮要寄的和下轮要寄的，每轮遍历一下这轮要寄的从链表中删除，然后更新一下下轮要寄的即可。
题目 \(\text{07}\) ：CF1922E - Increasing Subsequences \(\textcolor{green}{\bigstar}\) [构造 | 二进制]
思路：考虑将 \(x\) 二进制分解，假设最高位为第 \(dig\) 位，那么先构造一个长度为 \(dig\) 的上升序列 \(h\)，这样一开始的贡献是 \(2^{dig}\) 。之后从高到低遍历 \(x\) 的其他位，如果第 \(i\) 位是 \(1\) ，那么在后面加一个介于 \(h_i\) 和 \(h_{i + 1}\) 之间的数，这样产生的新的贡献就是 \(2^{i}\) ，这样最多需要 \(60 + 60 = 120\) 位就够了。
题目 \(\text{08}\) ：ABC334F - Christmas Present 2 \(\textcolor{grey}{\bigstar}\) [动态规划 | 单调队列]
思路：考虑 \(f_{i}\) 代表送到第 \(i\) 的点然后回家的最小代价，因为一次最多拿 \(k\) 个礼物，所以这个 dp 显然有类似滑动窗口的转移，跑一个前 \(i\) 个点的距离的前缀和预处理转移需要的代价，然后用单调队列优化即可。
题目 \(\text{09}\) ： ABC334G - Christmas Color Grid 2 \(\textcolor{grey}{\bigstar}\textcolor{magenta}{\bigstar}\) [点双连通分量 | 圆方树]
思路：考虑跑个点双，建出圆方树，然后每个统计每个圆点周围的方点个数，设为 \(x\) 。那么删除这个圆点会导致连通块个数增加 \(x - 1\) ，但是有一种特殊情况，就是只有一个圆点连接着 \(0\) 个方点，这样删除这个圆点会让连通块个数减 \(1\) 。用 tarjan 跑一下点双，剩下的期望随便算算就行了。
1.19
昨晚 CF 打完太兴奋了，然后打农和刷 B 站，凌晨 \(3\) 点才睡，第二天很晚才到 \(\text{9028}\) 训练，直接摆了一天，口胡了几个想补的题，完全不想写，明天再写吧（逃。
1.20
补了一下前天晚上 Edu 的 F 题，晚上打了场 ABC，结果 E 题最后 \(n\) 忘记加 \(1\)，一直找不到什么错，心态卡崩了，浪费了很多时间。而且长时间疏于数据结构，导致可持久化线段树已经忘得差不多了，粘板子改的也非常慢，最后 G 也没写完/kk/kk/kk。
题目 \(10\) ：CF1922F - Replace on Segment \(\textcolor{brown}{\bigstar}\textcolor{red}{\bigstar}\) [区间dp]
思路： 考虑区间 dp。设 \(f_{i, j, x}\) 表示把区间 \([i, j]\) 上的数全部变成 \(x\) 的最小代价。考虑转移，发现分为两种情况。第一种是将区间分为至少两端分别变成 \(x\) ，这种情况可以通过 \(f_{i, j, x} = \min\limits_{k = i}^{j - 1}\{f_{i,k,x} + f_{k+1, j, x}\}\) 进行转移。第二种是先操作一些区间，最后将 \([i, j]\) 整体一次变成 \(x\) ，但这种情况要求先通过前面的操作将区间 \([i, j]\) 的所有数变成非 \(x\) 的数，思考一下可以发现，去掉 \([i, j]\) 上等于 \(x\) 的数的代价最小的方案，一定是一段一段地用数字覆盖。考虑令 \(g_{i, j, x}\) 表示将区间 \([i, j]\) 整体变成一个数 \(y\)，使得 \(y \neq x\) 的最小代价，这个可以通过 \(f\) 轻松推出。考虑取出区间 \([i, j]\) 上所有 \(a_p = x\) 的位置，令 \(h_r\) 表示前 \(r\) 个位置均被覆盖成非 \(x\) 的数的最小代价，有转移 \(h_r = \min\limits_{l = 1} ^{r} \{h_{l - 1} + g_{pos_{l},pos_{r},x}\} , f_{i, j, x} \leftarrow h_{\operatorname{cnt}(x)} + 1\)，\(\operatorname{cnt}(x)\) 表示区间 \([i, j]\) 上 \(x\) 的个数。还剩最后一个问题，这样的总复杂度转移看似是 \(O(Tn^{5})\) 的，因为除去枚举区间的 \(O(n^{2})\)，还有 \(O(n^{3 })\) 的转移。其实分析一下每一个位置对于复杂度的贡献发现 \(O\left(\sum\limits_{i = 1}^{n} [\operatorname{cnt}(i)]^{2}\right) = O(n^{2})\)，所以枚举完区间之后的转移实际上是 \(O(n^{2})\)，所以总复杂度是 \(O(Tn^{4})\)，卡满是 \(5 \times 10^{8}\)，但循环完全跑不满，而且有 \(3\text{s}\) 的时限，可以通过，实际上最慢的只跑了 \(600\text{ms}\) 左右。（这里 \(n\) 和 \(X\) 同阶，不做区分）
题目 \(11\) ：ABC337G - Tree Inversion \(\textcolor{brown}{\bigstar}\textcolor{magenta}{\bigstar}\) [树形dp | 换根dp | 主席树]
思路：考虑先 dfs 一遍，开个树状数组，把结点 \(1\) 的答案算出来，然后考虑换根时贡献的改变。考虑从 \(fa\) 换到 \(u\) ，假设 \(v\) 在 \(u\) 的子树内部，那么所有 \(fa\) 到 \(v\) 的路径上 \(w = fa\) 的贡献都要减掉，即减去 \(u\) 的子树内结点编号小于 \(fa\) 的结点的个数。同理，贡献还要加上 \(u\) 的子树外结点编号小于 \(u\) 的结点的个数。直接预处理出树的 dfs 序，每次换根相当于查询一个区间有多少个数小于 \(k\)，因为没有修改所以是静态的查询，直接用主席树处理即可。（以后有时间一定把数据结构封装一个模板）
1.21
昨天晚上因为 E 题忘记写 \(n + 1\) 卡了 \(40\text{min}\) 心态崩了，打农打到特别晚，因此第二天起的特别晚，摆了一天，F 题处于一种一知半解的状态，然后打了晚上的 ARC。C 题是一个很天才的套路，但我不知道，看题解知道了这个套路，遂记之。
题目 \(12\) ：ARC170C -Prefix Mex Sequence \(\textcolor{blue}{\bigstar}\textcolor{red}{\bigstar}\) [dp]
思路：如果这题思路一直限制在 \(\operatorname{mex}\) 上，那么可能很难回到正轨了。首先注意到前 \(i - 1\) 数的 \(\text{mex}\) 的最大为 \(i\)，所以直接枚举 \(\text{mex}\) 是 \(O(\min(n, m))\) 级别的，那假设我们设 \(f_{i, j}\) 代表前 \(i\) 个数的 \(\text{mex}\) 为 \(j\) 且符合题目条件的方案数，发现 \(s_{i + 1} = 1\) 时下一个状态的 \(\text{mex}\) 我们无法得知，不能进行转移，然后我就卡在这里了。注意到不管 \(\text{mex}\) 是什么数， 假设 \(s_{i + 1} = 1\)，那么 \(a_{i + 1}\) 一定在 \(a_1 , a_{2} , \cdots, a_{i}\) 中没出现过。那我们不妨设 \(f_{i, j}\) 代表前 \(i\) 个位置在满足题意的条件下有 \(j\) 个不同的数的方案数，这样可以巧妙避免 \(\text{mex}\) 被记录到状态中导致无法转移的问题，更具体地说 \(\text{mex}\) 只会对这个 dp 的转移过程进行限制。若 \(s_{i + 1} = 1\)，相当于能且只能填入 \(\text{mex}\{a_1, a_2, \cdots, a_{n}\}\)，所以 \(j\) 一定会加 \(1\)，即进行转移 \(f_{i, j} \rightarrow f_{i + 1, j + 1}\) ；若 \(s_{i + 1} = 0\)，如果填入之前已经填入的数，即进行转移 \(j \times f_{i, j} \rightarrow f_{i + 1, j}\)，如果填入之前不存在的数，那么有 \((m + 1) - j - 1\) 种填数方式，减 \(1\) 是因为 \(\text{mex}\{a_1, a_2, \cdots, a_{n}\}\) 不能填，即进行转移 \((m - j) \times f_{i, j} \rightarrow f_{i + 1, j + 1}\)。最终答案 \(\displaystyle{ans = \sum\limits_{i = 1}^{\min(n, m + 1)} f_{n, i}}\)，时间复杂度为 \(O(n^{2})\)，可以通过。
1.22
vp 了 Codeforces Round 845 Div.2，赛时 \(4\) 题，后面的题还没补，但是觉得 D 挺有意思的，遂记录一下。
题目 \(13\) ：CF1777D - Score of a Tree \(\textcolor{brown}{\bigstar}\) [贡献的拆分 | 树形结构]
思路：考虑把贡献拆开，计算每个结点 \(x\) 在 \(t\) 时刻对答案的贡献。注意到结点 \(x\) 在 \(t\) 时刻的值只会被 \(x\) 向下 \(t\) 层的子节点影响，假设 \(x\) 向下 \(t\) 层的子节点有 \(cnt\) 个，那么这 \(cnt\) 个结点的权值在 \(t = 0\) 时有奇数个 \(1\) 才能使得 \(x\) 结点在 \(t\) 时刻的权值为 \(1\)，所以初始时这 \(cnt\) 个结点的方案数为 \(\binom{cnt}{1} + \binom{cnt}{3} + \binom{cnt}{5} + \cdots = 2^{cnt - 1}\)，因为其他结点初始的值对 \(x\) 在 \(t\) 时刻的权值没有影响，所以有 \(2^{n - cnt}\) 种方案。所以如果 \(x\) 向下 \(t\) 层具有子节点，不管具有多少个子节点，对答案的贡献都是 \(2^{cnt - 1} \times 2^{n - cnt} = 2^{n - 1}\)。所以只需要 dfs 求出每个节点向下最深的结点的深度，然后计算贡献即可。
1.23
学长给预备队出了一套模拟赛，听到学长讲了一个有意思的东西，就是三个整点没法组成一个等边三角形。因为边长 \(a\) 的平方一定是整数，而 \(\displaystyle{S = \frac{\sqrt{3}}{4}a^{2}}\) 一定是无理数，但是根据皮克定理，整点多边形的面积一定是有理数，所以一定不存在三个整点构成的等边三角形。
补了一下上场 ARC 的 D 题，一个很有意思的博弈论思维题。
题目 \(\text{14}\) ：ARC170D - Triangle Card Game \(\textcolor{blue}{\bigstar}\) [博弈论 | 思维题]
思路：考虑组成三角形的三边满足的限制，发现写成三个不等式非常繁琐，但可以简化一下写法。假设 \(a \ge b > 0\)，则 \(a, b, c\) 构成三角形的充要条件是 \(a - b < c < a + b\)。发现只要确定了 \(a, b\)，那么 \(c\) 必须落在区间 \((a - b, a + b)\) 上。假设 Alice 选了 \(a_i\)，Bob 选了 \(b_j\)，那么有两种情况：
\(a_i \ge b_j\)
此时 Alice 下一次必须选区间 \((a_i - b_j, a_i + b_j)\) 上的数才能赢，所以 Bob 肯定希望 Alice 能选的可行区间半径尽量小，所以 Bob 一定会选 \(b_{1}\)（假设数组 \(a, b\) 都从小到大排过序了），这样我们只需要看有没有 \(a_k\) 满足 \(k \neq i\) 且 \(a_{k} \in (a_i - b_1, a_i + b_1)\) 即可，实际上就是判断距离 \(a_i\) 最近的数的距离是否小于 \(b_1\)。
\(a_i < b_j\)
此时 Alice 下一次必须选区间 \((b_j - a_i, b_j + a_i)\) 上的数才能赢。此时 \(a_i\) 为可选区间的半径，半径越大 Alice 肯定越容易赢。再结合 \(1\) 中的分析，可以得出 Alice 的最优策略为：在保证 Bob 选择 \(b_1\) 时自己不会输的条件下，选择最大的 \(a_i\)。
由上，我们可以 \(O(n\log n)\) 地解决此题，其中的 \(\log\) 来自排序。
1.24
听 czy 学长讲了个奥数题思维题，准备出到预备队的比赛里，觉得很有意思，准备专门开一篇博客记录这种题和类似的 idea。
1.25
又 vp 了一场 CF div.2，赛后补了 D 和 E 写一下简要题解，D 是一个均摊时间复杂度的妙妙题。
题目 \(\text{15}\) ：CF1905D - Cyclic MEX \(\textcolor{brown}{\bigstar}\) [时间复杂度均摊]
思路：先把 \(0\) 移到最右边，考虑每次循环左移时每个位置 \(\text{mex}\) 的变化。容易得到 \(0\) 左边的所有位置的 \(\text{mex}\) 全都是 \(0\)，假设循环左移时最左边移到最右边的数是 \(x\)，那么 \(0\) 右边所有位置的 \(\text{mex}\) 如果比 \(x\) 小则不会受到影响，如果比 \(x\) 大则会变成 \(x\)，最后一个位置的 \(\text{mex}\) 依然是 \(n\)。所以相当于维护一个单调非降的序列的和，每次操作把大于 \(x\) 的后缀变成 \(x\)，并且在末尾添加上一个 \(n\)。我们可以把连续且相同的一些位置缩成一个块，这样每次暴力修改是 \(O(cnt)\) 的，\(cnt\) 是大于 \(x\) 的块数。因为每个块只会被删除一次，每次修改最多添加 \(2\) 个新的块，所以总块数 \(O(\sum cnt) = O(n)\)，均摊每次操作是 \(O(1)\)，总时间复杂度是 \(O(n)\) 的。
题目 \(\text{16}\) ：CF1905E - One-X \(\textcolor{blue}{\bigstar}\) [贡献的拆分 | dp]
思路：注意到线段树每层最多只有两种不同的线段长度，而且根节点线段长度相同的线段树的结构是相同的。假设当前根节点线段长度是 \(len\)，编号为 \(id\)，那么当前结点产生的贡献是 \(id \cdot (2^{\lfloor\frac{len + 1}{2}\rfloor} - 1)\cdot (2^{\lfloor\frac{len}{2}\rfloor} - 1)\)。所以直接递推出每一层的两种线段的个数与编号之和，直接计算贡献即可。加上快速幂，总时间复杂度是 \(O(\log^{2}(n))\) 的。
1.26
晚上打了一场 CF Round 921 div.2，赛时 \(59\text{min}\) 做了 \(4\) 题终于上紫名了，总算是实现了高中退役前的梦想。
晚上随便打了点牛客周赛的题，就不写了。
题目 \(\text{17}\) ：CF1925E - Space Harbour \(\textcolor{brown}{\bigstar}\textcolor{magenta}{\bigstar}\) [线段树]
思路：考虑在 \(pos\) 位置插入一个新的港口对其他位置的贡献。对于 \(pos\) 左边，插入前的总贡献是 \(v_{pre} \times (nxt - x)\)，插入后总贡献是 \(v_{pre} \times(pos - x)\)，\(\Delta = v_{pre}\times(pos - nxt)\)。对于 \(pos\) 右边，插入前的总贡献是 \(v_{pre} \times (nxt - x)\)，插入后的总贡献 \(v_{pos} \times (nxt - x)\)，\(\Delta = (v_{pos} - v_{pre}) \times(nxt - x) = -(v_{pos} - v_{pre})x +(v_{pos} - v_{pre})nxt\)。所以每个位置 \(x\) 的贡献是 \(kx + b\) 的形式，操作只有对 \(k\) 和 \(b\) 的区间加，对 \(kx + b\) 的区间查询，可以用线段树维护。
1.27
补一下昨天的 CF div.2 的 F 题。
题目 \(\text{18}\) ： CF1925F - Fractal Origami \(\textcolor{blue}{\bigstar}\) [几何]
思路：【题解】CF1925F
1.28 ~ 1.30
摸鱼 + 摆烂 + 给最后一场比赛搞题。
1.31
收拾东西，回家喽！