Description：

$n$ 个位置，每个位置容量为 $k$ 。 $m$ 个任务，每个任务要占据一个位置 $f_i$ ，且要满足 $1\leqslant f_i\leqslant lim_i$ 。支持 $q$ 次动态添加任务，查询合法的 $k$ 的最小值。

$1\leqslant n\leqslant 10^5,1\leqslant m\leqslant 10^5$

Solution：

首先可以直接二分图匹配做，但是会TLE，根据二分图的 $HALL$ 定理我们可以得出 $sum[i]\leqslant i\times k$ ，其中 $sum[i]=\sum_x [f_x\leqslant i]$ ，那么对于每个位置都必须满足 $k\geqslant \big\lceil\frac{sum[i]}i\big\rceil$ ，发现这个几乎不能用数据结构维护，那么我们可以考虑分块，最后的每一次添加都可以看成是对前缀和进行了一个后缀 $[v,n]$ 加一的操作，那么对于 $v$ 所在的块先不管维护什么反正我们可以暴力重构，考虑给一个区间整体加 $tag$ ，那么每个数的变化是： $$ \Big\lceil\frac{sum[i]+tag}i\Big\rceil=\Big\lceil tag\times\frac1i+\frac{sum[i]}i\Big\rceil $$ 那么每个位置 $i$ 可以看成是一个斜率为 $\frac 1i$ ，截距为 $\frac{sum[i]}i$ 的直线， $tag$ 也就是 $x$ 坐标单调递增，那么我们可以用单调栈对每个块求出凸包，然后每次打 $tag$ 就可以让点在凸包上向右移动就可以找到最小值了。

Code：

没有代码