P11983

lsj2009 · 2025-08-26 19:58:34 · 题解

第一想法是逐位确定，但是位与位之间的割裂难以提出复杂度优秀的做法。转换视角：从大往小考虑所有数 x，找到一个字典序最小的下标集合 S，然后将 i\in S 的 b_i 赋成 x 并满足存在解。判断性问题即区间选点问题，判断最少选择点数（记为 c）是否不大于 x 在 a 中出现次数（记为 c_x）。考察 S 的形式，最开始肯定是不断取当前未选取位置中第一个，直到 c>c_x，回退这一步，然后再会被迫选取一些零散的点。c 每次操作后至多增加一，则选取完一个未选点序列的前缀后有 c=c_x，随后加入零散点需满足 c 不发生变化。

如何求出该前缀？显然可以二分，但是实际上在 S 内的点和二分 check 的 S 大小可能完全不在同一级别，复杂度退化到平方及以上。如何保证复杂度正确？先找到最小的 k 使得选取前 2^k 个位置不合法，如此 2^k 和 S 中极长前缀大小 d 是同一级别，接下来在 [2^{k-1},2^k) 内二分即可。找 k 复杂度是 T(k)=T(k-1)+\mathcal{O}(k2^k)=\mathcal{O}(k2^k) 的，后面是 \log{d}\times(d\log{d}) 的，不过可以事先将 2^k 个区间排好序，如此每次 check 顺次拉出，复杂度优化到 d\log{d}+\log{d}\times d。这一部分均摊总复杂度 \mathcal{O}(n\log{n})。

接下来考虑零散点的加入。将区间按左端点从大到小/右端点从小到大排序求出 l_i/r_i 表示选取的第 i 个点坐标下/上界，感受一下 [l_i,r_i] 中所有数都是可以取到的，且 [l_i,r_i] 两两不交即 r_i<l_{i+1}（其实不太会说明啊）。这样子每次新加入一个区间 [L_k,R_k]，其与 [l_1,r_1],[l_2,r_2],\cdots,[l_c,r_c] 的位置关系只有四种：

1. 与所有 [l_i,r_i] 无交。
2. 包含某个 [l_i,r_i]。
3. 仅与某个 [l_i,r_i] 有交。
4. 和 [l_i,r_i],[l_{i+1},r_{i+1}] 有交。

如果是情况 1 则说明 k 不能被加入；情况 2 说明其不会对 l/r 序列产生任何影响；情况 3 思考一下发现就是将 [l_i,r_i] 向 [L_k,R_k] 取交；情况 4 并不会直接对 l_i/r_{i+1} 产生影响，因为上下界仍然是可以达到的，但是若在未来某个时刻 [l_i,r_i] 和 [L_k,R_k] 无交那么就会对 r_{i+1} 产生影响，在 r_i 上打个 tag 即可（形如若 r_i<L_k 则对 r_{i+1} 进行修改，用 priority_queue 维护，需要注意的是，最开始的 d 个区间也需要考虑这种情况），另一侧同理。

当然我们需要保证考虑的 k 不能是情况 1 或者至少和情况 2/3/4 是同级的。这很简单，我们在每次 [l_i,r_i] 更新时求出编号最小的和他有交的未被选择的区间即可（同样用 priority_queue 维护），分讨 l_i\le L\le r_i 和 l_i\le R\le r_i 两种情况即可（对于 2 类区间则不必考虑编号的优先性，同样容易处理），开个线段树维护。

复杂度 \mathcal{O}(n\log{n})。