BZOJ1135: [POI2009]Lyz

题目大意：初始时滑冰俱乐部有1到n号的溜冰鞋各k双。已知x号脚的人可以穿x到x+d的溜冰鞋。 有m次操作，每次包含两个数ri，xi代表来了xi个ri号脚的人。xi为负，则代表走了这么多人。 对于每次操作，输出溜冰鞋是否足够。

首先—— 每次二分图匹配显然是爆炸的

所以有这么一个东西—— Hall定理：对于一个二分图，设左边有n$n$个点，右边有m$m$个点，则左边n$n$个点能完全匹配的充要条件是：对于1<=i<=n$1<=i<=n$,左面任意i个点，都至少有i个右面的点与它相连

然后—— 我们肯定不能一一枚举所有的情况，这样是2人数$2^{人数}$的 我们考虑只挑一些有用的情况来算(也就是最差情况)，我们可以把所有的人想象成一个1~n的序列，每个位置存人数。假设我们选的不是脚的型号在连续的一段区间的人的话，分两种情况讨论： 1.这些人对应的鞋的可选型号范围是连续的。那么我们不妨再选上中间没有选到的人，这样人数变多了，而范围不会扩大，这样选到的情况一定更劣的。所以我们无需计算最开始选择的那种方案 2.不是连续的。那就更加好办了，我们只需要计算每段连续的部分就行了。这种情况合法当且仅当每段连续的区间都合法。

于是—— 综上所述我们只需要判定每个连续的人形成的段是否满足Hall定理即可 设我们选择的是脚在[l,r]$[l,r]$区间内的人，a[i]$a[i]$代表型号为i$i$的有多少人。 想满足Hall定理，则对于任意的l,r$l,r$我们必须满足这个式子： ∑i=lra[i]<=(r−l+1+d)∗k$/sum/limits_{i=l}^{r}a[i]<=(r-l+1+d)*k$ 操作和询问是O(m)$O(m)$的，大约是50W，每次枚举端点+查询+修改是O(n2logn)$O(n^2logn)$的，时间复杂度还是接受不了 于是我们把式子换一种形式写出来 ∑i=lr(a[i]−k)<=d∗k$/sum/limits_{i=l}^{r}(a[i]-k)<=d*k$ d∗k$d*k$是一个定值，现在相当于询问把每个a[i]−k$a[i]-k$之后查询最大连续和并检验其是否小于等于d∗k$d*k$ 那么这件事情就可以用线段树来维护了，需要支持单点修改，最开始的时候把所有的a[i]$a[i]$都设为−k$-k$就好了