Ynoi Easy Round 2022 C. 堕天作战 TEST_98

小清新线段树练习题。

注意到操作 11 等价于区间所有数无条件减去 xx，然后把原本等于 xx 的数再加回 xx（使得这些等于 xx 的数恰好变成 00），操作 22 因为 00 对区间和没有贡献，所以这严格等价于求区间所有元素的总和。为了不退化成暴力，考虑如何保证减法操作不会无休止地引发复杂的分支逻辑。注意到题目保证 x≥0x \ge 0，这意味如果一个元素在不断的减法中变成了负数，那么它在未来永远不可能再等于任何 xx，势能线段树一下就没了。

难度评测：Medium-

MEX Foundation Contest D. The Jump from Height of Self-importance to Height of IQ Level

小清新平衡树练习题。

注意到如果一个区间不存在长度为 33 的递增子序列，它必然可以被划分为两个递减的子序列。所以只要在平衡树上维护一下区间内所有不是前缀最小值的元素中的最小值和区间内所有不是后缀最大值的元素中的最大值。一旦发现有元素能卡进这两个值构成的范围，就说明找到了长度为 33 的递增子序列。

考虑如何快速跨区间更新。注意到在一个尚未出现长度为 33 递增子序列的合法右子树区间里，所有大于某个阈值的元素从左到右必然是严格单调递减的。这意味着，当我们需要在右子树中寻找大于左子树最小值的最小元素时，其实就是在找满足条件的最靠右的元素。借助单调性，我们直接在树上无脑往下走一条链，可以保证单次操作复杂度为 O(log⁡2n)\mathcal{O}(\log^2 n)。

难度评测：Easy+

Ynoi2019 Happy Sugar Life

时代的眼泪 加强版，太色情了。

注意到直接处理四维限制的二维上升点对非常困难，考虑容斥原理。由于询问固定了右侧点 (xj,yj)(x_j, y_j) 必然在询问矩形内部，可以离线扫描线求出所有以矩形内元素为右侧点的全局合法上升点对数量，剩下的工作就只是减去左侧点 (xi,yi)(x_i, y_i) 不在矩形内的部分。

考察这些不在矩形内的左侧点，它们必然严格落入互不重叠左下方、正下方和正左方三个区域。左下方的点对任何矩形内的右侧点都必然合法，所以这部分贡献直接等于左下方的单点数乘上矩形内的单点数。而正下方区域本质上是要求在 xx 的区间限制内，满足 yi<VL≤yj≤VRy_i < V_L \le y_j \le V_R 的点对数量。正左方区域同理。由于坐标的对称性，正左方区域的询问只需将原序列替换为对应的逆排列。

考虑如何快速求解正下方区域的贡献。这部分等价于查询区间内满足 yi≤Y1,yj≤Y2y_i \le Y_1, y_j \le Y_2 的对数，将序列以 B≈255B \approx 255 划分为若干块，预处理出每个块内元素的二维前缀合法对数，以及每个值域前缀在各个块内的出现频次。当需要跨区间查询时，对于整块直接利用预处理数组进行 O(1)\mathcal{O}(1) 累积，对于散块则借助预处理的频次无脑往下扫一遍即可。整体时间复杂度为 O(mn)\mathcal{O}(m\sqrt{n})，有点卡常。

难度评测：Hard-

OOI2025 Day2 D. Order Statistics

注意到直接模拟每次选取最大 kk 个元素减 11 的过程显然无法接受，考虑对操作的宏观等效性进行刻画。由于所有的函数查询最终都要求将数组升序排序，这意味着元素的初始位置除了处理相同大小元素的优先级外，不再具有其它意义。因此，我们跳出位置的限制，转而只关心最终数组在值域上的频率分布。

考察全局总计 mkmk 次减法操作的分配。这本质上相当于用一个阈值 VV 对数组进行削平。具体而言，由于每个元素单次最多被减小 11，整体最多被减小 mm 次，我们可以通过二分找到一个最小的阈值 VV，使得所有大于 VV 的元素被削减至 VV（且限制单点削减量不超过 mm）的总减小量不超过 mkmk。此时必然多出 RremR_{rem} 次操作，根据优先减前排元素的规则，这恰好会导致原数组中 RremR_{rem} 个特定的元素被额外减小至 V−1V-1。由于最终询问会要求排序，这 RremR_{rem} 个元素必然自动“挤”在所有的 V−1V-1 对应的区间内，我们完全不需要追踪它们的原始下标。

考虑如何快速求解特定值域的统计信息以及应对带修询问。既然只需要值域的出现频次，可以将原数组以及所有修改涉及的元素离散化，建立两个树状数组分别维护区间的出现次数和真实权值和。处理查询时，先通过树状数组辅助二分求出阈值 VV 和剩余量 RremR_{rem}，从而能够在 O(1)\mathcal{O}(1) 次树状数组查询内得出操作后任意值域的元素个数与总和。对于 F(x)F(x) 查询只需再次嵌套一层值域二分，对于 S(l,r)S(l,r) 则直接转化为求两次分布的前缀和并作差。整体时间复杂度为 O(qlog⁡Ulog⁡K)\mathcal{O}(q \log U \log K)，其中 UU 为答案值域范围，KK 为离散化大小），常数较小。

难度评测：Easy

KTSC2021 Day1 B. 뚫기

KOI 典中点凸包 ds 题。

考察飞船的行动轨迹，其实际操作必然可以抽象为使用了 TT 次瞬间移动，并将全程切分为了 T+1T+1 个具备固定 yy 坐标的水平段，途中强行击破了 PP 个无法避开的障碍物。总代价可严格表达为 W=A⋅T+B⋅PW = A \cdot T + B \cdot P。

由于每次询问给定不同的 AA 和 BB，且代价函数是关于 A,BA, B 的一次多项式，根据线性规划原理，对于任意非负的 (A,B)(A, B) 组合，使得代价最小的策略点 (T,P)(T, P) 必然严格落在所有可行策略点集构成的下凸包上。

考虑指定了一条凸包切线斜率时，如何求出对应的极值点。定义 dp 状态表示到达当前列、处于特定 yy 坐标的最小代价。每一列的推进包含两步转移：穿过当前列障碍等于在值域 [Y1,Y2][Y_1, Y_2] 范围内执行区间加 BB；而允许任意传送，则等价于利用当前的全局最小代价，对所有 dp 值执行对全局最小值 +A+ A的区间取 min⁡\min。，我们可以通过离散化 yy 坐标建立线段树，在 O(Nlog⁡K)\mathcal{O}(N \log K) 内求出特定斜率下切到的最优点 (T,P)(T, P)。

考虑到凸包的顶点极其稀疏，可以直接分治求凸包，先用极端的斜率求出最小化 TT 和最小化 PP 的两个端点，然后计算这两点连线的斜率作为新的 (A,B)(A, B) 比例传入线段树，若求出的新点严格位于连线下方，则将其加入点集并向两侧递归。只需极少的 dp 调用即可完整描绘下凸包。

剩下的三份就做完了，整体时间复杂度为 O(∣Hull∣⋅Nlog⁡K+Qlog⁡∣Hull∣)\mathcal{O}(|\text{Hull}| \cdot N \log K + Q \log |\text{Hull}|)。

难度评测：Medium

Ynoi 2019 魔法少女网站

考察对多维限制的解绑，核心操作必然可以抽象为动态维护一个随阈值 xx 变化的 0/10/1 序列，并求出指定区间 [l,r][l,r] 内所有连续 11 极大连通段长度 LL 的代价总和 W=∑L(L+1)2W = \sum \frac{L(L+1)}{2}。

考虑分块，定义状态表示块内元素在特定 xx 下的前后缀连续 11 长度及块内总贡献。每一块的激活过程实质上是单调的，将块内元素按权值升序排列后，随着 xx 的增大，块内元素被逐个激活。可以预处理出这 BB 种激活态下的前缀连续段 pre、后缀连续段 suf 以及内部总代价 ans。可以在 O(N)\mathcal{O}(N) 空间下保存完整的块内状态机。

剩下的随便乱搞，整体时间复杂度为 O(M⋅NBlog⁡B)\mathcal{O}(M \cdot \frac{N}{B} \log B)，空间复杂度仅为 O(N)\mathcal{O}(N)。

难度评测：Medium+（卡常难度）

Ynoi2078 《A Path Towards Autonomous Machine Intelligence》阅读报告（更新中…）

考察对时间维度的区间查询与空间维度的单点作用叠加，等价于维护一系列分段的仿射变换和取最值操作，并求出指定时间区间 [l,r][l, r] 内所有操作按顺序复合后，在特定空间坐标 XX 上的最终映射结果。

考虑对时间建线段树，定义节点状态表示该时间区间内所有操作叠加后，对全空间 [1,n][1, n] 划分出的若干个连续且变换相同的独立作用段。底层的单一操作最多将空间切分为 33 段，且区间合并过程在空间坐标上是单调的。利用双指针将左右儿子的空间区段按坐标线性求交集，并将对应区段的变换函数逐个复合。

剩下的在线查询定位 O(log⁡M)\mathcal{O}(\log M) 个区间并在内部二分计算，整体时间复杂度为 O(Mlog⁡2M)\mathcal{O}(M \log^2 M)，动态开点线段树可以做到 O(Mlog⁡M)\mathcal{O}(M \log M) 的空间复杂度。

这个题的 11 个 log⁡\log 做法还没写。

难度评测：Easy（22 个 log⁡\log 做法）/Hard（11 个 log⁡\log 做法）

2023暑期多校Day3 C. Stillwater Prison

注意到点在凸多边形内到边界的最短距离，必然是它到所有边所在直线距离的最小值。因为每条边的距离都可以表示为一个二元一次函数 f(x,y)=Ax+By+Cf(x,y) = Ax+By+C，所以只要在由所有查询点构成的 KDT 上维护一个二维李超树。一旦所有边对应的函数全部插入完毕，只要顺着树搜到底，路径上记录的最优函数就能算出真正的最短距离。

考虑如何快速在子树区间进行函数下放与剪枝。注意到两个二元一次函数的差值 Δf=ΔAx+ΔBy+ΔC\Delta f = \Delta A x + \Delta B y + \Delta C 依然是严格线性的，它在任何矩形包围盒内的最小值必然在边界顶点处取得。这意味着当我们需要判断一个在中心点处于劣势的平面能否在局部区域“翻盘”时，其实就是在看 Δf\Delta f 在该区域的最小值是否为负。借助 ΔA\Delta A 和 ΔB\Delta B 符号对应的单调性，我们直接无脑提取包围盒最靠左/右、上/下的边界值，就能 O(1)\mathcal{O}(1) 锁定极值点。配合建树时始终沿最长维度进行切割的策略来规避狭长包围盒，可以保证单次平面插入的最坏复杂度严格界定为 O(q)\mathcal{O}(\sqrt{q})。

难度评测：Easy+