bzoj2138

题意: 话说Nan在海边等人，预计还要等上M分钟。为了打发时间，他玩起了石子。 Nan搬来了N堆石子，编号为1到N，每堆包含Ai颗石子。每1分钟，Nan会在编号在[Li,Ri]之间的石堆中挑出任意Ki颗扔向大海（好疼的玩法），如果[Li,Ri]剩下石子不够Ki颗，则取尽量地多。为了保留扔石子的新鲜感，Nan保证任意两个区间[Li,Ri]和[Lj,Rj] ，不会存在Li<=Lj & Rj<=Ri的情况，即任意两段区间不存在包含关系。可是，如果选择不当，可能无法扔出最多的石子，这时NN就会不高兴了。所以他希望制定一个计划，他告诉你他m分钟打算扔的区间[Li,Ri]以及Ki。现在他想你告诉他，在满足前i-1分钟都取到你回答的颗数的情况下，第i分钟最多能取多少个石子。 100% N<=40000 M<=N 1<=L[i]<=R[i]<=N A[i]<=500

题解： 它让我想起了这道题[POI2009]Lyz。。 将线段按左端点排序后，再按时间处理。现在时刻处理的是从左到右第k条线段。 想知道在当前线段放入x石子后有没有完美匹配，考虑用hall定理判定。 hall定理是一个子集，这题中显然可以贪心的取连续的一段线段。 s[i]表示石子前缀和，h[i]表示从左到右前i条线段已经放了多少石子，l[i]，r[i]表示从左到右第i条线段左右端点 那么有完美匹配的条件就是x<=min(s[r[j]]-s[l[i]-1]-(h[j]-h[i-1]))(i<=k,j>=k) 化简后变为min((s[r[j]]-h[j])-(s[l[i]-1]-h[i-1])) 设s[r[j]]-h[j]=aj,s[l[i]-1]-h[i-1]=bi，这是只与i，j相关的两个量 那就是min(aj-bi) 显然可以由min(aj)-max(bi)得到 区间min(a)和max(b)容易用线段树维护 得到当前时刻答案x后，h[k..m]会改变，去线段树上对a，b打打标记就好