P11983

第一想法是逐位确定，但是位与位之间的割裂难以提出复杂度优秀的做法。转换视角：从大往小考虑所有数 $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$ 则说明 $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})$。