思路：
a[]存憤怒值；b[i]存以i結尾的，窗口里的最大值；c[i]存以i結尾的，窗口里面包含?的最大值。
（?為新大象的位置）
例：1 2 3 4 ? 5 6 7 8 9
則ans的計算公式=b3+b4+c4+c5+c6+b7+b8+b9;
b3為max[1 2 3];??b4為max[2 3 4];
c4為max[3 4 ?];?c5為max[4 ? 5];?c6為max[??5?6];
b7為max[5 6 7];?b8為max[6 7 8];?b9為max[7 8 9];
由此可以歸納得到一個公式：n個數，每個窗口長度為m，遍歷到i時，ans可以分成三段：①[b(m)+b(m+1)+...+b(i-1)] + ②[c(i-1)+c(i)+...+c(i+m-2)] + ③[b(i+m-1)+...+b(n)]
（求max[]使用單調隊列來求，求ans用前綴和）
ans=sumb[i-1]+sumc[i+m-2]-sumc[i-2]+sumb[n]-sumb[i+m-2]
但是還有ans某部分不存在的情況：
當i<=m時，此時①不存在，即ans=sumc[i+m-2]+sumb[n]-sumb[i+m-2]
若i>=n-m+2時，此時③不存在，，即ans=sumb[i-1]+sumc[n]-sumc[i-2]
當i>m&&i<n-m+2時，ans=sumb[i-1]+sumc[i+m-2]-sumc[i-2]+sumb[n]-sumb[i+m-2]
代碼：
?
#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 10;
int n, m, A, ans = 0;
int a[N], b[N], c[N];
int sumc[N], sumb[N];
void getmax(int n, int m)
{deque<int> q;for (int i = 1; i <= n; i++){if (!q.empty() && q.front() <= i - m)q.pop_front();while (!q.empty() && a[i] >= a[q.back()])q.pop_back();q.push_back(i);if (i >= m){b[i] = a[q.front()];sumb[i] = sumb[i - 1] + b[i];}}
}
void getmax2(int n, int m)
{deque<int> q;for (int i = 1; i <= n; i++){if (!q.empty() && q.front() <= i - m)q.pop_front();while (!q.empty() && a[i] >= a[q.back()])q.pop_back();q.push_back(i);if (i >= m){c[i] = max(A, a[q.front()]);sumc[i] = sumc[i - 1] + c[i];}}
}int main()
{cin >> n >> m >> A;for (int i = 1; i <= n; i++){cin >> a[i];}getmax(n, m); // 求b[]getmax2(n, m - 1); // 求c[]for (int i = 1; i <= n + 1; i++){if (i <= m){ans = max(ans, sumc[i + m - 2] + sumb[n] - sumb[i + m - 2]);}else if (i >= n - m + 2){ans = max(ans, sumb[i - 1] + sumc[n] - sumc[i - 2]);}else{ans = max(ans, sumb[i - 1] + sumc[i + m - 2] - sumc[i - 2] + sumb[n] - sumb[i + m - 2]);}}cout << ans;return 0;
}
)
