#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int n, m, q[N], tail = -1, head = 0, a[N];

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++) {
		while (tail >= head && a[i] <= a[q[tail]])
			--tail;
		q[++tail] = i;
		//i-j+1<=m   j>=i-m+1
		while (tail >= head && q[head] < i - m + 1)
			head++;
		if (i >= m)
			cout << a[q[head]] << " ";
	}
	cout << endl;
	tail = -1,head = 0;
	for(int i=1;i<=n;i++){
		while(tail>=head && a[i]>=a[q[tail]])--tail;
		q[++tail] = i;
		while(tail>=head && q[head]<i-m+1)head++;
		if(i>=m)cout<<a[q[head]]<<" ";
	}
	return 0;
}

好消息

/*
1 2 3 4 5 1 2 3 4 5
1 2 3 4 5 6 7 8 9 10
*/

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e6 + 5;
int n, a[N], sum[N], q[N], tail = -1, head = 0;
signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sum[i] = sum[i - 1] + a[i];
	}
	for (int i = n + 1; i <= 2 * n; i++) {
		sum[i] = sum[i - 1] + a[i - n];
	}
	//i   j~i的极小值  i-j+1==m
	int res = 0;
	for (int i = 1; i < 2 * n; i++) {
		while (tail >= head && sum[i] <= sum[q[tail]])
			tail--;
		q[++tail] = i;
		while (tail >= head && i - q[head] + 1 > n)
			head++;
		if (i >= n) {
			int j = i - n + 1;
			if (sum[q[head]] - sum[j - 1] >= 0)
				res++;
		}
	}
	cout << res << endl;
	return 0;
}

/*
f[i] = sum[i] - sum[j]
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 5;
int n, m, a[N], sum[N];
int q[N], tail = -1, head = 0;

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> sum[i];
		sum[i] += sum[i - 1];
	}
	//i-m<=j<i
	int res = -1e9;
	for (int i = 1; i <= n; i++) {
		while (tail >= head && sum[i - 1] <= sum[q[tail]])
			tail--;
		q[++tail] = i - 1;
		while (tail >= head && q[head] < i - m)
			head++;
		res = max(res, sum[i] - sum[q[head]]);
	}
	cout << res << endl;
	return 0;
}

琪露诺

/*
f[i]跳到i点的最大值
f[i] = f[j]+a[i]
i-R<=j<=i-L
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 4e5 + 5;
int n, L, R, a[N], f[N], q[N], tail = -1, head = 0;

signed main() {
	cin >> n >> L >> R;
	for (int i = 0; i <= n; i++) {
		cin >> a[i];
	}
	memset(f,0xcf,sizeof(f));
	f[0] = a[0];
	int res = -1e18;
	for (int i = L; i <= n + R; i++) {
		while (tail >= head && f[i - L] >= f[q[tail]])
			--tail;
		q[++tail] = i - L;
		while (tail >= head && q[head] < i - R)
			head++;
		f[i] = f[q[head]] + a[i];
		if (i >= n)
			res = max(res, f[i]);
	}
	cout << res << endl;

	return 0;
}