一眼题，但这个 $k$ 迷惑了我很久。
由于我初始的思路没考虑 $x<0$，所以我们先默认 $x>0$。
考虑任意一个是最优答案的最大子段和，如果它的长度 $<k$ 那么它的每个元素一定都加上了 $x$，如果它的长度 $>k$，那么它的 $k$ 个元素一定加上了 $x$，剩余的一定减去了 $x$。
小于 $k$ 怎么搞都行，而如果长度大于 $k$，我们可以把 $k$ 个加 $x$ 的移到这个子段的最前面加这样显然不会有影响。
然后枚举这个答案的左端点之后，将左端点右边 $k$ 个都加上 $x$，剩余的都减去 $x$。
该过程可以用线段树维护，时间复杂度为 $O(n\log n)$，但是样例最后一个没过，还以为假了。随便猜了个 $x \to -x$ ，$k\to n-k$ 便过了样例然后一遍过了。
代码：
#include <bits/stdc++.h> #define int long long #define For(i, a, b) for (int i = (a); i <= (b); i ++) #define foR(i, a, b) for (int i = (a); i >= (b); i --) using namespace std; int n, k, x, ans = 0; int c[200005]; struct S {int lmx, rmx, sum, mx;}a[800005]; void merge (S &a, S b, S c) { a.lmx = max (b.lmx, b.sum + c.lmx); a.rmx = max (c.rmx, c.sum + b.rmx); a.mx = max (max (b.mx, c.mx), b.rmx + c.lmx); a.sum = b.sum + c.sum; } void build (int l, int r, int k) { if (l == r) { a[k].lmx = a[k].rmx = a[k].sum = a[k].mx = c[l]; return; } int mid = l + r >> 1; build (l, mid, k << 1); build (mid + 1, r, k << 1 | 1); merge (a[k], a[k << 1], a[k << 1 | 1]); } void update (int l, int r, int k, int x, int y) { if (l == r) { a[k].lmx += y; a[k].rmx += y; a[k].sum += y; a[k].mx += y; return; } int mid = l + r >> 1; if (x <= mid) update (l, mid, k << 1, x, y); else update (mid + 1, r, k << 1 | 1, x, y); merge (a[k], a[k << 1], a[k << 1 | 1]); } void solve () { cin >> n >> k >> x; if (x < 0) { x = -x; k = n - k; } ans = 0; For (i, 1, n) { cin >> c[i]; if (i <= k) c[i] += x; else c[i] -= x; } build (1, n, 1); For (i, 1, n - k + 1) { if (i - 1) { update (1, n, 1, i - 1, -2 * x); update (1, n, 1, i + k - 1, 2 * x); } ans = max (ans, a[1].mx); } cout << ans << '\n'; } signed main () { int _ = 1; cin >> _; while (_ --) { solve (); cout << '\n'; } return 0; }