【Hall 定理 | 维护凸包】P15948 [JOI Final 2026] 面包师 / Baker

Hall 定理 + 李超线段树

对于一个询问 $(A,B)$，将顾客作为左部点，面包做出的时间 $B+iA$ 为右部点，连边的条件为 $T\le B+iA\le T+L$，变为二分图最大匹配问题。

考虑 Hall 定理，由连边的规则可知 $N(S)$ 必然为 $B+iA$ 的一个前缀，因此 $N(S)$ 大小只与 $\underset{j\in S}{max}j$ 有关。设对于当前询问，受影响的顾客为 $[l,r]$。

$$|S|-\underset{T\subseteq S}{max}(|T|-|N(T)|)=r-l+1-\underset{i\in [l,r]}{max}(i-l+1-\lfloor \frac{T_i+L-B}{A}\rfloor )$$

即

$$r-\underset{i\in [l,r]}{max}(i-\lfloor \frac{T_i+L-B}{A}\rfloor )$$

对于 $max$ 内有一个向下取整除法，处理方法为提出外围，由负号变为向上取整。

$$r-\lceil \frac{\underset{i\in [l,r]}{max}(iA-T_i)+L-B}{A}\rceil$$

使用线段树套动态开点李超线段树可以实现区间维护一次函数 $(i,T_i)$ 最值，时间复杂度为 $O((M+Q){\log }^{2}M)$。

可撤销栈模拟队列维护凸包

除了从一次函数角度考虑这个 $max$，还可以从凸包角度考虑这个 $max$。

设已知量 $X=i$，$Y=-T_i$，我们要最大化 $C=XA+Y$，即 $Y=-XA+C$，相当于一条斜率为 $-A$ 的直线有多个点坐标 $(X,Y)$ 可供选择，求截距最大的方案，易知可被选择的点集构成上凸包。

如果没有区间的限制，使用单调栈维护凸包即可，有区间的难点在于维护凸包的操作难以从头部删除点。

因此可以使用两个单调栈模拟队列，设队头对应的栈为 $\mathrm{out}$，队尾对应的栈为 $\mathrm{in}$，每次加入新数时往 $\mathrm{in}$ 里丢，弹出队头就是 $\mathrm{out}$ 的栈顶，相当于要撤销 ${\mathrm{out}}_{\mathrm{top}}$ 入栈的这一步操作，就是把被丢掉的点加回来，使用一个 vector 数组记录每次入栈丢掉了哪些点即可。当 $\mathrm{out}$ 被删空时，将 $\mathrm{in}$ 的所有点倒入 $\mathrm{out}$。

对于一个点，他一共在两个栈中被操作了 $8$ 次，故时间复杂度为 $O(M+Q\log M)$。