Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 1135: [POI2009]Lyz

题目链接

传送门

Description

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

Input

n m k d ( 1≤n≤200,000 , 1≤m≤500,000 , 1≤k≤10^9 , 0≤d≤n ) ri xi ( 1≤i≤m, 1≤ri≤n-d , |xi|≤10^9 )

Output

对于每个操作,输出一行,TAK表示够 NIE表示不够。

Sample Input

4 4 2 1

1 3

2 3

3 3

2 -1

Sample Output

TAK

TAK

NIE

TAK

题解

首先
二分图匹配炸不死你
所以考虑其他的东西
所以有这么一个东西——
Hall定理:对于一个二分图,设左边有n个点,右边有m个点,则左边n个点能完全匹配的充要条件是:对于1<=i<=n,左面任意i个点,都至少有i个右面的点与它相连
这东西挺好
然而我们肯定不能枚举所有的情况啊 不然时间复杂度是2^人数的
接下来是精髓
我们考虑只挑一些有用的情况来算(也就是最差情况),我们可以把所有的人想象成一个1~n的序列,每个位置存人数。假设我们选的不是脚的型号在连续的一段区间的人的话,分两种情况讨论:
1.这些人对应的鞋的可选型号范围是连续的。那么我们不妨再选上中间没有选到的人,这样人数变多了,而范围不会扩大,这样选到的情况一定更劣的。所以我们无需计算最开始选择的那种方案
2.不是连续的。那就更加好办了,我们只需要计算每段连续的部分就行了。这种情况合法当且仅当每段连续的区间都合法。
然后我们一总结
发现这样的话每次判断我们只需要判断一个区间
然后区间问题怎么办
线 段 树
500000爆炸怎么办
优 化
我们可以把推出来的式子进行优化
然后就很愉♂悦

代码

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏