题解 P3564 【[POI2014]BAR-Salad Bar】

· · 题解

传送门

我是来帮楼下加藤大佬写题解的……全世界都没找到加藤大佬写法的说明……很难受……

首先我们把p看成1，j看成-1，一个区间满足条件就意味着这个区间的所有前缀和都大于等于0，所有后缀和都大于等于0

我们记录一下前缀和，所有前缀和大于等于0就是sum[i]-sum[l-1]\geq 0，所有后缀和都大于等于0就意味着sum[n]-sum[i-1]\geq sum[n]-sum[r]，即sum[i-1]\leq sum[r]，然后因为sum[r]\geq sum[l-1]已经在第一个条件里满足了，所以合起来就是sum[i]\geq sum[l-1]，sum[r]\geq sum[i]。用人话说，一个区间满足条件，那么这个区间内的sum都不小于sum[l-1]且sum[r]是这个区间中最大的数

于是我们定义to[i]，意思是[i,to[i]]中的所有数都大于等于sum[i]，且sum[to[i]]为这个区间中最大的数，to[i]为所有满足条件的数中最靠右的。那么我们就可以枚举左端点i，如果s[i]==j这个左端点肯定不行，否则这个左端点能匹配的最大的右端点就是to[i-1]

现在的问题就是怎么求出to[i]了，我们一开始先把所有的to[i]都赋值为i，这样到时候可以少讨论一些边界情况。

首先，如果sum[i+1]<sum[i]，即s[i+1]为p，那么to[i]只能等于i，因为它的下一个就小于它了。所以我们只考虑讨论s[i+1]为j的情况

我们考虑从后往前做，定义nxt[i]为它后面的第一个与它sum相等的位置，记录一个指针las，表示每一次的to[i]，现在做到了i，那么las应该是指在to[i+1]的位置。

那么转移会有两种情况

1.to[i]=to[i+1]，那么直接转移即可 2.to[i]变大。比如图中，k的位置才是to[i] 我们发现，在本题中，相邻两个数的值最多只会相差1，于是若是存在如图2的情况，那么必然存在nxt[i]。不难证明[i+1,nxt[i]-1]区间内的数肯定同时大于sum[i]或同时小于sum[i]，如果全都小于那么有sum[i+1]<sum[i]，我们之前已经处理掉了。所以[i+1,nxt[i]-1]之间的数必然全都大于sum[i]。因为to[nxt[i]]已经求出来了，如果sum[to[nxt[i]]]\geq sum[las]，我们可以把[i,nxt[i]-1]这一段给接上去，那么新的区间[i,to[nxt[i]]]肯定还是满足条件的，且不难证明不存在比它更优的。这种情况下我们让las指向to[nxt[i]]并更新to[i]即可。

只要处理出[0,n-1]的所有的to[i]就可以了，最后的答案就是max\{to[i-1]-i+1\}(s[i]==p)，时间复杂度O(n)

代码看楼下加藤大佬的好了