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;
}