[国家集训队2011]stone解题报告

题目:

话说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分钟最多能取多少个石子。

分析:
先设想该题一个简单的版本:给出所有询问,问是否能够满足?

我们来看“任选石子”的确切含义:每个石子可以放进一个区间。
这是一个贪心问题:枚举每一颗石子,将它放进“包含它且右端最靠前”(并且未被填满的)那个区间。

这个贪心算法显然是对的,举个例子,假设这个石子的位置是10,而有两个区间[7,11]和[9,15],如果最优解中它在[9,15]中,会发生什么呢?如果在10时[7,11]仍未被填满,那么10后面的一些石子必然放入[7,11],在这里就是说11放进了[7,11]中,那么我们把11放进[9,15],而把10放进[7,11]必然不会变得更差。

形式化地,如果石子i没有填进“右端最靠前”的那个区间U,那么我们可以交换i和i之后放进U的某一颗石子j使得答案不会变差。而且j一定存在,因为U在i时未被填满。

但是这样好像仍然无法解决问题啊?(其实有一个比较逗的做法,对每个询问,都二分拿多少石子,用上述贪心算法进行可行性判定)。但是不要捉急,因为这个贪心算法可以导出一个结论:

条件无法满足当且仅当有i<=j使得S(i,j),其中T(i,j)表示所有包含于[i,j]的区间的值之和,S(i,j)表示i~j堆石子数量之和。

为什么呢?

充分性很好证明。可以发现,S(i,j)

必要性则需要用到贪心的过程。没有可行方案,那就意味着贪心在某一刻失败了——贪心失败时会是什么情形呢?对于某个区间U,没有足够的石子去填满U这个区间。那么,要么U要求的石子数多于U包含的石子数之和,要么就是和U相交的某个区间“不得不”占用了那些石子。因此我们可以一直向前推,直到某个区间V的起点处V,发现我们一路上积累的“要求石子数”多于包含的石子数。也就是说,设i=V的起点,j=U的终点,有S(i,j)
这一证明还有个额外意义。在本题中,任意两个区间是不会互相包含的,而[i,j]至少包含了一个区间,所以[i,j]不在任何区间内部(当然它本身有可能是一个区间,但这并不影响结论)。因此,我们可以把那个充要条件中的(i,j)加强为:不被任一区间严格包含的(i,j)。后面将会用蛋糕这一点。

然后我们再来分析一下S(i,j)和T(i,j)。S(i,j)=S[j]-S[i-1],其中S[k]表示A[1]+A[2]+…+A[k]。而T(i,j)呢?设左端点在1~k的区间权值和为TL[k],右端点在1~k的区间权值和为TR[k],那么T(i,j)=TR[j]-TL[i-1]。

可以发现,T(i,j)这一表达式的正确性基于“区间不会互相包含”的条件。因为区间不会包含,所以左端点在1~i-1的那些区间的右端点必然小于j。也就是说,TR[j]是所有右端点<=j的区间权值和,而TL[i-1]就是所有左端点<=j的区间权值和。所以T(i,j)=TR[j]-TL[i-1]

现在我们考虑怎么用这一结论去确定询问的答案。假设我们有了S,TR,TL三个数组,现在给出一个区间[x,y],求至多能在其中取出多少个?

显然,假设答案为t,那么相应更新TR,TL数组后,必须满足所有的T(i,j)<=S(i,j),即TR[j]-TL[i-1]<=S[j]-S[i-1],即(S[j]-TR[j])+(TL[i-1]-S[i-1])>=0,设前一项为f[j],后一项为g[i-1],也就意味着:对所有i=0.

那么,假设答案为t,f和g数组会得到怎样的更新呢?

显然,TR[y]~TR[N]都会加上t,故f[y]~f[N]都会减去t。同时,TL[x]~TL[N]都会加上t,即g[x]~g[N]都会减去t。

[国家集训队2011]stone解题报告


就像这样,两条竖线是x,y,图比较意识流,凑和着看吧……

现在我们看对于任意的(i,j),g[i]+f[j]发生了何种变化。
1:如果x<=i;y<=j,那么g[i]+f[j]并未改变,因为t和-t刚好抵消。
2:如果i
3:如果x<=i;j
4:如果i<=j,那么g[i]+f[j]的值减小了t。这很容易理解,因为换句话说,所有包含[x,y]的区间的T值都增加了t。

所以真正需要关注的就是条件4:在修改f,g数组后,对所有i<=j的(i,j),都必须满足g[i]+f[j]>=0.所以t的最大值就是本次询问之前所有这些g[i]+f[j]的最小值。用线段树维护f,g即可。

这样具体算法就出来了:对于第i个询问[x,y],查询f[y]~f[N]中最小值a,g[0]~g[x-1]中最小值a+b,那么本次最多拿的石子数t=min(K[i],a+b)。然后,将f[y]~f[N]的每个数都减去t,将g[x]~g[N]的每个数都加上t。

代码:

发表评论

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