60分单调队列悬关求调
查看原帖
60分单调队列悬关求调
1156735
coduck12345楼主2024/12/31 22:07
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,q[500005],q1[500005];
long long a[500005];
signed main(){
	cin>>n>>k;
	k++;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]=a[i]+a[i-1];
	}
	long long l=1,r=0,l1=1,r1=0,ans=0;
	for(int i=1;i<=n;i++){
		if(l<=r&&q[l]==i-k){
			l++;
		}
		while(l<=r&&a[i]<a[q[r]]){
			r--; 
		}
		q[++r]=i;
		if(l1<=r1&&q1[l1]<=i-k){
			l1++;
		}
		while(l1<=r1&&a[i]>a[q1[r1]]){
			r1--;
		}
		q1[++r1]=i;
		if(i>=k){
			ans=max(1ll*ans,a[q1[l1]]-a[q[l]]);
		}
	}
	cout<<ans;
	return 0;
} 
2024/12/31 22:07
加载中...