省选联考 2025《推箱子》：单调位移压缩

本节目标

从无限数轴上的碰撞过程，推出一个单调数列的区间赋值问题；证明截止时刻贪心、推动区间和花费公式，并用线段树在 $O(n\log n)$ 内判定可行性。

前置知识与课前自测

前置：交换论证、单调序列、线段树区间赋值/区间和。

严格递增的整数位置 $p_i$ 经过哪个简单变换后只需“非降”？
推箱子 $i$ 向右时，哪些箱子必须一起动？
两个要求的截止时刻分别为 $t_i<t_j$，为什么先满足 $j$ 不会比先满足 $i$ 更优？

答案

1. $x_i=p_i-i$；因为 $p_{i+1}\ge p_i+1$，故 $x_{i+1}\ge x_i$。 2. 对所有连续的 $j\ge i$，若它的当前归一化位置小于 $b_i-i$，就必须被推到该值。 3. 较早截止的箱子在较晚时刻前必须已固定；把两段操作交换为早截止者在前，不增加总移动量，且不破坏后者。

问题动机

直接模拟时，一个箱子可能推动长链，而长链在后续又被多次访问，最坏 $O(n^2)$。很多实现会维护“连续箱子段”，但还可以再往前走一步：减去箱子编号后，“连续”就是“数值相等”。

步步式引导

1. 把严格位置序列变成非降序列

设当前位置为 $p_i$，定义

$$ x_i=p_i-i. $$

箱子不能重合等价于 $x_1\le x_2\le\cdots\le x_n$。两个相邻箱子相距恰好 1，等价于它们的 $x$ 相等。

目标位置同样定义 $c_i=b_i-i$。由于 $b_i$ 严格递增，$c_i$ 也非降。

2. 一次推动其实是一次区间赋值

若 $x_i<c_i$，箱子 $i$ 向右移。当它遇到 $i+1$时必须推动后者；继续传递，直到第一个 $x_j\ge c_i$ 的箱子为止。因此若

$$ r=\max{j\ge i:x_j<c_i}, $$

这次最小推动恰为把 $x_i\ldots x_r$ 全部赋为 $c_i$。花费是

$$ ci(r-i+1)-\sum{j=i}^{r}x_j. $$

若 $x_i>c_i$，完全对称：找最左的 $l$ 使 $x_l\ldots x_i>c_i$，赋为 $c_i$，花费为

$$ \sum_{j=l}^{i}x_j-c_i(i-l+1). $$

停顿：为什么不需同时推动 $i$ 左边与它连成一段的箱子？

展开

向右移动会与左侧箱子分开，不会挤压左侧。因此区间必须从 $i$ 开始，而不是从 $x_i$ 相等块的左端开始。这也是连续段实现中需要先分裂的原因。

3. 为什么按截止时间排序

对两个相邻处理的要求 $i,j$，且 $t_i\le t_j$。若方案先让 $j$ 到位，再让 $i$ 到位，把“让 $i$ 到位所必须的推动”提到前面：

箱子的相对次序不变，而 $b$ 也严格递增，因此 $i$ 的目标不会跨过 $j$ 的目标。
一次推动产生的位置是满足顺序约束的最小改动。先做较早要求，不会产生额外往返。
$i$ 在 $t_i$ 之后不得再移动；排序后，后续推动因目标序的单调性不会跨过已固定箱子。

通过不断交换逆序对，存在一个按 $t$ 非降处理的最优方案。

核心知识

一棵线段树维护当前非降数列 $x$：

区间和：计算推动花费。
区间赋值：完成一次推动。
单点查询：得到当前 $x_i$。
找从 $i$ 开始第一个 $x_j\ge c_i$ ，或到 $i$ 为止最后一个 $x_j\le c_i$。

由于整个数列始终非降，边界查找可在线段树上向左/向右优先下降，无需在外层再套二分。

精选例题：推箱子

来源信息、题意与范围

洛谷-P11833 推箱子，省选联考 2025，提高+/省选−。
每组 $n\le2\times10^5$，$1\le a_i,b_i\le10^9$，$0\le t_i\le10^{16}$，$a,b$ 均严格递增；$T\le6$。
每单位时间只能把一个箱子移动一格，不能重合；箱子 $i$ 从时刻 $t_i$ 起必须一直位于 $b_i$。

Hint 1：处理顺序

按 `t_i` 从小到大，每次只做使当前箱子到位的最少操作。

Hint 2：坐标变换

令 `x_i=pos_i-i`，碰在一起的箱子对应相等的 `x`。

Hint 3：向右推

找到最大 `r` 使 `x_r < b_i-i`，把 `[i,r]` 赋成 `b_i-i`。

Hint 4：数据结构

非降序列上的边界查找+区间和+区间赋值，一棵 Lazy Segment Tree 足够。

Observations

截止时间把问题变成单机调度式的前缀可行性：处理完前 $q$ 个要求后，累计最小移动数必须不超过第 $q$ 个截止时刻。
原坐标中的“推动一条紧挨链”不好表示；减去编号后，它变成“将一段小于/大于阈值的数赋为阈值”。这改变了维护对象。
只要起点与边界正确，区间赋值自动保持非降不变量；无需维护显式碰撞关系。
花费是区间赋值前后数组和之差，所以求和不是附带需求，而是从“每移一格花一时间”直接推出的势能差。

Editorial 与正确性证明

按 $(t_i,i)$ 排序。归纳假设已经用最少时间满足了前缀要求，且当前 $x$ 非降。处理 $i$ 时：

$x_i=c_i$ 无需操作。
$x_i<c_i$ 时，任何合法方案都必须把每个 $j\in[i,r]$ 推到至少 $b_i+(j-i)$，即 $x_j\ge c_i$。因此上述和式是不可突破的下界。把这一段全部赋成 $c_i$ 恰好达到下界，又不多移任何箱子。
$x_i>c_i$ 对称。

因而每一步都在给定已处理前缀后取到最小新增时间。交换论证又保证某个全局最优方案可按截止时间排序，所以累计时间就是满足每个截止前缀的最少时间。若它超过 $t_i$，任何方案都不可行；否则在操作间插入等待即可对齐真实时刻。

每个要求做常数次线段树操作，时间 $O(n\log n)$，空间 $O(n)$。

实现指南

boxes = sort by (deadline, index)
x[i] = initial[i] - i
elapsed = 0
for box i in boxes:
    c = target[i] - i
    if x[i] < c:
        r = first position >= i with x[r] >= c, minus one
        elapsed += c * length(i,r) - range_sum(i,r)
        range_assign(i,r,c)
    elif x[i] > c:
        l = last position <= i with x[l] <= c, plus one
        elapsed += range_sum(l,i) - c * length(l,i)
        range_assign(l,i,c)
    if elapsed > deadline[i]: return No
return Yes

完整 C++17 附件

边界注意：

输入首行是测试点编号 $c$ 和数据组数 $T$，不是 $n$。
截止时间至 $10^{16}$，累计时间与区间和用 64 位。
向右时边界条件是第一个 $x\ge c$，不应把已等于 $c$ 的箱子再计入花费。
在判为 No 后仍要正确消费当组输入；附件先读入整组再求解。
附件已与 $n\le4$、截止时间至 8 的小状态 BFS 对拍：BFS 枚举每一时刻移哪个箱子或等待。

扩展与联系

也可用 ODT/平衡树维护相等 $x$ 的连续段；每次先在 $i$ 分裂，再向推动方向合并。线段树版的复杂度证明更直接。
$x_i=p_i-i$ 是把“严格递增整数序列”换成“非降序列”的常用离散几何转化，在排队、防碰撞调度和最小位移中常见。
若目标 $b_i$ 不严格递增，可能根本没有无碰撞最终状态，交换论证与后续不会推动已固定箱子的性质都会失效。

总结与自检

为什么两个相等 $x$ 对应原坐标中紧挨的箱子？
向右推动的区间为什么从 $i$ 而非当前相等段的左端开始？
区间和之差为什么恰好是单位移动数？
如何用一个三箱子例子检查左推的不等号？

课后训练建议

先手算样例第二组的 $x$ 序列，记录三次处理后的区间赋值。
30 分钟内只写 $O(n^2)$ 数组模拟，先与时间 BFS 对拍；确认贪心后再换线段树。
复盘时不要只记“维护连续段”，应能复述“减去编号后，碰撞链变成区间赋值”。

09-省选2025推箱子与单调位移压缩.md 7.8 KB Постоянная ссылка История Исходник