[OI记录] IOI2026 集训队作业选做

日子将永远持续下去

我必定还能向前迈进

大家快来 push 我加训。

重新开始接触更加困难、舒适区之外的题目！

Cells Blocking

$\text{Difficulty : AT 2600 | (5)}$

$\text{Quality : A}$

$\text{Date: 2026/09/07}$

题意

给一个足够大的二维四连通网格，每个点可以是空地或者障碍，开始在左上角，只能向右/向下走。

问存在多少种在空地上再放置两个 block 的方案，使得左上角和右下角不连通。

$n,m\le 3000$。

Sol

如果只放置一个 Block，阻断左上角和右下角，方案数显然是所有路径的交集的大小。如何简要刻画这个“所有路径的交集”？

因为本题平面图的特征，两条路径在不存在交的情况下不可能互相穿过（上方路径一直在上方，下方路径一直在下方）所以，最靠上路径和最靠下路径的交集就等价于所有路径的交集，这个大小就是放置一个 block 阻断所有路径的方案数。

如何统计“放置两个 block 阻断所有路径“ 的方案数？

首先对于任何一条路径，我们一定都存在至少一个 block 在它上面，所以对于最靠上的路径我们枚举这个路径上 block 的位置（这条路径的长度是 $O(n+m)$ 的），在阻断了这个 block 后，查询”新的最靠上的路径“和”原本最靠下的路径“的交集大小即可，这两条路径的长度都是 $O(n+m)$ 的。

”新的最靠上的路径“可以通过找到和这个阻断的 block 的 $i+j$ 相同的下一个最靠上的 $(i,j)$，使得 $(1,1)\to (i,j)\to (n,m)$ 存在路径，然后推回 $(1,1),(n,m)$

时间复杂度 $O((n+m{)}^2)$。

Mindset

• 形式化、简化问题的简单版，然后快速统计
• ”一定存在，一定需要被覆盖“ 确定枚举范围
• 替代思想（处于同一层的一定互不依赖）

Excluded Min

$\text{Difficulty : AT 2800 | (5+)}$

$\text{Quality : S}$

$\text{Date: 2026/09/10}$

题意

对于一个集合 $S$，如果集合 $S$ 里面有至少两个 $x$，你可以操作其中一个 $x$ 变为 $x+1$ 或者 $x-1$，你想最大化 $\text{MEX}(S)$，这个值为 $f(S)$。

给出序列 $A$，每次给 $l,r$ 查询 $f(\{A_l\dots A_r\})$ 。

$n,q\le 5\times 10^5$

Sol

最大化 MEX 就是最大化一个满的前缀，容易注意到只要之前不是满的就一定会不断给它变小到第一个空。如果前缀是满的我们就将其变大，从小到大做这个操作，可以发现最大的 MEX 就是最大的 $x$ 满足 $<x$ 的数有 $\ge x$ 个，于是我们现在查询 $f(S)$ 变成查询 $\sum [a_i<x]\ge x$ 的最大 $x$。

如果我们想在线地维护出“区间内”类似 $\sum [a_i<x]$ 这样的“值域上的”、”无可减性的“信息往往是很困难的，而值域上“$<x$”，”最大的 $x$“，这种模式又在提醒我们去离线地按值域扫描。

考虑离线地从大到小扫描 $x$，维护每个询问区间内的小于 $x$ 的数的数量。在每个询问第一次满足小于 $x$ 的数有至少 $x$ 个的时候将其标记答案并删除。

现在我们想让 $x\leftarrow x-1$，假设 $a_i=x$ 考虑发生的变化，即所有包含 $i$ 的询问的个数要减去 $1$，减去后查询新的所有询问的最大值，如果 $\ge x$ 则标记它并删除。 如果直接做这会是一个矩形加，全局 $\max$，不能用简单的数据结构做掉。

但是本题的答案是具有单调性的！如果区间 $[l_1,r_1],[l_2,r_2]$ 满足 $l_1\le l_2\le r_2\le r_1$，那么 $[l_1,r_1]$ 的答案一定比 $[l_2,r_2]$ 的答案大，也就是说只有大区间被扫描到，然后删除后，小区间才可能被删除。因此目前可能被删除且还没有被删除的区间是互不相交的若干区间， $l$ 和 $r$ 分别单调，也就是说会被修改到的询问其实是一个区间，拿一棵线段树做区间加、全局 $\max$ 就行了！在一个区间被删除后激活所有新产生的不被任何区间包含的区间即可（其初始值可以用树状数组数）。

现在就只需要在一个区间 $[l_1,r_1]$ 被删除后找出所有新的不被任何区间包含的区间了（这些区间原本被 $[l_1,r_1]$ 包含）。

设在原本的互不包含的区间序列中 $[l_1,r_1]$ 的前一个区间为 $[l_0,r_0]$，后一个为 $[l_2,r_2]$，且 $l_1\le r_0,l_2\le r_1$。

我们尝试从左到右一个一个拿出所有互不包含的，如下图。

那么最靠左边的新区间就是 $l\ge l_1,r>r_0$ 的最小 $l$（需要满足 $l<l_2$)，可以通过按照 $l$ 排序后在线段树上二分找到，设它的右端点为 $r^{\prime }$ 然后我们接下来再去寻找下一个 $l\ge l^{\prime },r>r^{\prime }$，不断这样找下去就解决了。其实我们甚至并不需要要求 $l\ge l_1$，因为如果这个 $l<l_1$，它理应更早就被加进来了（它才是那个更不被包含的)。所以其实直接对 $r$ 排序建一个线段树，区间查就行了 $l$ 的最小值就行了。

时间复杂度 $O((n+q)\log (n+q))$

Mindset

• 离线扫描答案，在第一次可行时标记并删除询问。
• 观察答案的单调性，维护互不包含的区间。
• 线段树二分找类似前驱、后继的偏序