KOI TST 2026 部分题解

· · 个人记录

d1p1

固定 k，容易发现每个位置只会被至多两个长度为 2^k-1 的合法区间覆盖，因此修改单点每次只影响 \mathcal O(\log n) 个区间。

修改单点时先将以前覆盖它的删掉，再从小到大加入新的区间即可。时间复杂度 \mathcal O(n\log n)\sim\mathcal O(n\log^2n)。

d1p2

还不会。

d1p3

转 45 度分析，就明显一些（？

首先要想到怎么刻画贪心合并出来的子树形态：考虑从下往上做，上传 f_{u,i} 表示 u 子树高度在 i 位置时的最小宽度。令任意子树 T，宽度序列 seq(T) = \{l_0, l_1, ..., l_k\} 来描述这个子树高度为 i 时宽度为 l_i。一个必要条件是，合法的宽度序列 l 必须满足对所有 i > 0，有 l_i \geq l_{i-1} - 1。

有 seq(\text{leaf}) = \{0\}。假设某个节点 u 有两个子节点 v_L 和 v_R，它们的宽度序列分别为 P 和 Q。设 u 到 v_L,v_R 的边下界长度为 c_L,c_R，则在 P 和 Q 的后面分别加 c_L-1,c_R-1 个 0，得到新的宽度序列。

考虑所有叶子有相同的 x+y，在 u 的子树中，高度 i 的宽度至少为 P_i + Q_i + 1。将合并后的序列 S 计算成 S_i = P_i + Q_i + 1，再从前往后执行 chkmax(S_i,S_{i-1}-1) 的操作，最终再追加一个 0 表示 u。

缩颜色段后启发式合并即可做到 \mathcal O(n\log^2n) 的复杂度。

d1p4

考虑判定：操作顺序形如对 a 从小到大操作，每次取出 a 的所有最小值，那么至少有一个需要停留在这里，否则无解。剩下的位置进行 +1，直到全部操作完。

用一个递归判定的思路，从 [1,n] 开始操作，可以找出所有 x，使得所有跨越 x 的区间都是非法的。接下来认为 [1,n] 本身是合法的（事实上对于所有轮廓线分开做）

考虑刻画 ban 掉的 [l,r] 的矩形，每次考虑 \min 的所有取值，将删除的 \min 设为黑色，剩下的记为白色。如果一个 [l,r] 跨越了至少一个白色但是没跨越黑色那么就爆了。但是矩形数量依旧很爆，考虑让矩形带权：对于 ban 掉的矩形，取出所有相邻的黑点 x,y，加入 l\in[x+1,y-1],r\in[x+1,y-1]，权值为 1；对此时的相邻点加入 [a+1,b-1],[a+1,b-1]，权值为 -1。

前者总操作数正确，而后者可以等修改时再统计（权值是累加的），总共 \mathcal O(n) 个矩形加。查询 (l,r) 考虑这个点点权是否 >0，那么离线扫描线，用树状数组维护就是 \mathcal O(n\log n) 的。

d2p1

容易想到对半分，但是进一步很难做，考虑 6\leq n 的限制和较小的 Q，不难想到尽量均等地划分成 6 个集合 S_{1\sim 6}，对于所有 T\subseteq\{1,2,3,4,5,6\} 且 1\leq |T|\leq 3，将 Y 设为 \cup S_{T_i}，用这些信息就可以求出跨越集合之间的 X。

发现询问次数恰好是 \binom{6}{3}+\binom{6}{2}+6=41，并且可以满足 \sum|S_{T_i}|\leq\lceil\frac n 2\rceil+1。再考虑 x_{i,j},y_{i,j},z_{i,j,k} 分别设为 (i,j) 的二元集合，一个在 i 两个在 j，以及三个在 i,j,k 的，解出来和即可。

d2p2

问一个菊花但是每个花瓣都是 2 元链即可，每个 2 元链都可以实现比较大小。

特殊处理一下中心被选以及 n 奇数的 case，考虑利用一下二进制分组的结构。

d2p3

不妨设 l,r 双单调，可以求出 h\to h+1 必须落在 [L_h,R_h] 区间内，满足 L,R 双单调。转化为有 H 个右部点，每个点对应一个区间，向区间内所有左部点连边，代价为选中的左部点的 a 之和，现在要求恰好选中 k 个。

猜测：令答案存在的区间为 ans_x\sim ans_y，那么这部分是凸的，并且每个对应方案都是删一个红加一个蓝。

先考虑 0 个蓝色位置的答案，这是经典贪心：对于所有 a 排序，维护当前集合 S，如果 S\cup \{i\} 存在完美匹配那么加入 i。使用 Hall 定理判定：\forall |S|\leq |N(S)|，转化为 S 选一段区间 [l,r]，要求 preS_r-preS_{l}+1\leq idR_r-idL_{l}+1，移项后的限制是 \forall l\leq r 满足 preS_r-idR_r\leq preS_l-idL_l。线段树维护两者最值即可完成判定。

考虑 ans_x\to ans_y 的过程，会存在二元组集合 D，每对元素为一对红蓝节点，代表删一个红加一个蓝。由凸性，只需要求出 D 然后再对 \Delta 排序即为答案。

求 D：初始为 ans_x 对应的 S，按代价从小到大考虑当前蓝色元素 b，找到代价最大且已被插入的 r，将 r 替换为 b 且新的 S' 存在完美匹配。可行的 b 的替换范围是一段包含 r 的区间（考虑限制最严的 [l,r]），直接二分就是 \log^2 的。使用官方题解的 (,*,) 刻画可以是单 \log 的。

时间复杂度 \mathcal O(n\log n)\sim \mathcal O(n\log^2n)。

d2p4

操作形如对 x 开始的严格前缀最大值位置做分数 +1，考虑用单侧递归线段树维护这个标记。标记的方式也可以模仿单侧递归的过程，每次操作的复杂度同样是 \mathcal O(\log^2n)。

时间复杂度 \mathcal O(q\log^2n)。