百奇派对

将剩余赠送者和接收者分别按编号排序，并匹配相同排名的人。初始时每个人与自己匹配，因此合法。维护匹配始终合法，且每个匹配接收者的编号不超过赠送者原来的编号。

对赠送者$i$，设匹配接收者为$x$，前一个剩余接收者为$y$，若不存在则令$y=0$。若$L_i>y$，称$i$为受阻赠送者。第一个赠送者始终受阻。选择最右边的受阻赠送者$i$。

回复$j$满足$j\geq L_i>y$，所以不会在$x$左边。删除$i$和后，它们之间的赠送者的匹配各向左移动一个接收者。右边没有受阻赠送者，因此移动后仍满足下界。接收者编号变小，也保持满足上界。匹配继续合法，从而对于交互器的任何选择，每轮都能成功。

为每个剩余赠送者维护

$$D_i=\operatorname{rank}_{\rm giver}(i)-\#\{\text{剩余接收者 }j<L_i\}-1,$$

排名从1开始。合法匹配保证$D_i\geq0$，受阻赠送者恰好满足$D_i=0$。删除赠送者$i$与接收者后，恰好将且的赠送者的减1。因为的赠送者必然在右边，两个排名变化相互抵消。

按赠送者原始编号分为大小为$B$的块。每块按$L_i$排序，用懒标记线段树维护前缀减1和最小值。对选中赠送者所在的块，下放懒标记、直接更新并重建。对其右边的完整块，更新满足$L_k\leq j$的前缀。维护最小值为0的块的集合，即可找到最右边的0。

时间复杂度为$O(N(B+(N/B)\log B))$，空间复杂度为$O(N)$。实现取$B=1024$。当时，可直接用数组维护有序匹配，得到算法。当时，可用两个使用状态位掩码，枚举交互器所有回复进行极小极大搜索。

Solution written by GPT6.1