是模拟赛的T2喔。

今天的文章：霍尔定理其二

在我的洛谷博客中获得更好的阅读体验，谢谢喵。

思路都对的，线段树写错了，我好高兴。

对着想了一个小时，啥思路都没有，然后忽然发现可以看作是一个二分图完美匹配，而且这个二分图匹配还挺特殊的。

考虑这样的二分图：左边是 个点代表人数，右边是 个点代表房子，然后可以根据题意连一下边，然后存在每个人都满意的方案就等价于存在一个完美匹配，然后它等价于霍尔定理的某个形式。

（详见 霍尔定理其一

那我们显然的贪心思路是让左边点尽量多右边点尽量少，显然选连续的最划算，否则可以凑成连续的，我们设当前喜欢 的哥们有 个，那么一个区间的代价很容易计算:

左边：

右边：

然后你要让你俩玩意差最大，可以先把右边的 提出来，然后一个很经典的操作是给线段树上每个点赋值一个 ，然后再把 放上去，就变成了一个线段树求最大子段和的问题。

然后直接维护就行了。

但是我不会写线段树维护最大子段和，难过喵。