P3503 Blocks 题解

K8He · 2022-01-20 15:15:36 · 题解

P3503 Blocks 题解

更好的阅读体验

原题传送门

思路

首先我们可以发现，若 a_l \sim a_r 的平均值大于等于 k，则这个区间一定可以转化为都大于等于 k 的。我们就把这个问题化简成了“求最长的平均值大于等于 k 的子序列”。

再去化简，可以发现，如果我们把序列中的每一项都减去 k，再求前缀和 s，若 s_i-s_j\ge 0，则区间 [j,i] 一定满足条件。

那么我们考虑如何求这种区间。

不难发现，若 i<j 且 s_i<s_j，则选 i 当左端点比 j 更优，则选 j 当右端点比 i 更优。

那么我们去维护一个单调栈存可能最优的左端点，栈中的元素都满足：在栈中 j 在 i 之上且 s_i>s_j。（这里自己好好思考一下）

根据我们维护的单调栈的性质，我们可以发现：

• 一个元素越靠栈顶，可以和它在一起的右端点越多，但产生的区间越短。
• 如果一个右端点与栈里的一个元素产生的区间合法，则该右端点与该元素之上的元素一定也能构成合法区间。

那么我们再从最右边开始枚举右端点，去找最大区间。如果一个右端点与栈顶的左端点可以构成合法区间那就更新答案，并把栈顶弹出（因为再靠左的右端点就算满足条件也没有这个长了），继续看浮出来的新栈顶是否合法。

记得判断 s_i\ge 0 的情况。

代码

#include <bits/stdc++.h>
#define _for(i,a,b) for(int i=a;i<=b;++i)
#define for_(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
using namespace std;
const int N=1e5+10,inf=0x3f3f3f3f;
ll n,q,a[N],b[N],k,ans;
stack<ll>s1,s2;
int main(){
    scanf("%lld%lld",&n,&q);
    _for(i,1,n)scanf("%lld",&a[i]);
    while(q--){
        scanf("%lld",&k);
        ans=0;
        _for(i,1,n){
            b[i]=b[i-1]+a[i]-k;
            if(b[i]>=0)ans=max(ans,(ll)(i));
            if(s1.empty()||b[i]<b[s1.top()])s1.push(i);
        }for_(i,n,1){
            while(!s1.empty()&&b[i]-b[s1.top()]>=0){
                ans=max(ans,i-s1.top()),s1.pop();
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}