CF702F T-Shirts 解题报告

· · 题解

先将所有 T-shirts 按照品质和价格排序，接下来问题变为 m 次询问给出初始值 b，对于 i\in [1,n]，依次执行：如果 b \geq c 执行 p \gets b -c，值域较大，可能需要使用一些经典的折半技巧。

做法 1，离线 O(n\log n\log w)

考虑离线，将所有人按拥有的钱升序排序，依次枚举所有 T-shirts，买了这件 T-shirt 的人一定是一个后缀，买了这件 T-shirt 的人可能会因为钱变少而发生了人之间顺序的改变，我们把这个改变的形态写出来：

两个人钱之间相对顺序的改变仅当一个人在 [0,c) 中，而另一个人原本在 [0,2c) 中，而此时后者的钱会减少 c，也就是说至少减去了一半，这意味着这种相对顺序的改变最多发生 O(n\log w) 次，所以我们可以暴力进行这种相对顺序的改变。

使用平衡树维护所有人之间的钱的顺序，每次将平衡树分成三部分，[0,c) 不改变，[c,2c) 直接暴力减去 c 插入到 [0,c) 之间，[2c,+\infty) 直接打上 -c 的标记。

时间复杂度 O(n\log n \log w)。

做法 2，在线 O(n\log n\log w)

对于大于 x 减 x 的问题往往可以考虑值域分层的思想，将值域按照 [2^{E},2^{E+1}) 分成 \log w 层次，因为我们直接模拟的话会浪费大量的时间在减去较小的 c_i 上，因此我们考虑将很小的 c_i 一起考虑。对于目前的 b 所在的层 E，我们将 \lceil\log_2 c_i\rceil < E （层更低）的物品一起考虑，并试图快速地跳过这些物品。

如果在继续枚举 i 的过程中发生了以下两种情况之一，那么 b 一定会进入到更低的层中：

前者显然成立，后者因为 b 和 c_i 在同层，b\gets b-c_i 后新的 b 的最高位一定减去了，所以一定去到了 E 更低的层。

出去这两种情况，就只剩下出现了一个层级更低切 b\geq c_i 的 c_i 的情况。

对于目前的位置 l，我们可以二分之后第一个出现的上方两种情况的位置 p，这说明我们完整的减去了所有 [l,p) 内的层比 E 更低的 c_i，可以直接减去。

因为在经过了 p 位置后一定会进入更低的层，所以总共只需寻找 O(\log w) 次这样的 p 并手动处理。

使用线段树维护区间内低于每个层级的 c_i 的和，以确定能否满足对于该区间内的低于 E 层的 a_i 都可以被减去。

同时也维护每个层级内不会减去一个同层的 c_i 的 b 的最大界，以确定是否会在该区间内减去一个同层的 c_i，由于不可能减去两次同层的数，该信息的维护是简单的。

在维护这些信息后容易把该二分丢到线段树上，调整信息合并的方式后也可以选择直接 ST 表二分，但是 ST 表二分的空间 2log 的，不太可取。

信息合并的方式与二分的过程可能有些细节，可以参考我的代码。

该做法时间复杂度 O(n\log n\log w)，常数很小。

这种值域分层的思想将在 CF1515I、P8522 中得到更进一步的运用。

做法 3，在线 O(n(\log n+\log w))

该做法由李欣隆老师在 WC2024 时讲述。

考虑直接回归最朴素的暴力，就直接 O(nw) 地 dp：f_{i,j} 表示从第 i 个位置开始，j 块钱买了几件 T-shirts，显然有转移 :

f_{i,j}=f_{i+1,j} (j< c_i) f_{i,j}=f_{i+1,j-{c_i}}+1 (j\geq c_i)

也就是说对于 f_{i} 数组，从 i+1 到 i 的改变就是前面的某一段复制，区间加一后拼接到后面，直接使用可持久化平衡树自拼接的技巧*可以做到 O(n(\log n+\log w))。

*：其实就是路径复制，像正常地平衡树拼接序列一样，复制自己的之后将合并路径上的节点复制作为新的，没有改变的儿子继续指向原本的即可。