「Codeforces 1197D」Yet Another Subarray Problem

Description

给定长度为 $n$ 的数组 $\{a\}$ 和 $m,k$，定义子区间 $[l,r]$ 的价值为 $\sum\limits_{i = l}^{r}a_i - k\left \lceil \frac{r-l+1}{m} \right \rceil$，空区间的价值为 $0$，求所有子区间的价值最大是多少。

$(1 \leq n \leq 3 \times 10^5,1 \leq m \leq 10,1 \leq k \leq 10^9,-10^9 \leq a_i \leq 10^9)$

Source

[Luogu]CF1197D

[Codeforces]1197D

Solution

很容易发现一个性质：若我们所选子区间的左端点为 $l$，则可以把 $a_l,a_{l + m},a_{l + 2m},\ldots$ 的值全部减去 $k$，因为每当选到这些数时 $\left \lceil \frac{r-l+1}{m} \right \rceil$ 的值会增加 $1$（总和减去 $1$ 个 $k$）。而 $m$ 的数据范围很小，我们不妨枚举 $x = [0,m)$，对于 $1 \sim n$ 中的某个数 $i$，如果 $i \bmod m$ 的值为 $x$，就把 $a_i$ 减去 $k$ 。接着枚举左端点 $l =x + ym\ (y \in {\rm Z})$，计算左端点在该位置上的最大价值，判断能否更新答案即可。怎么求最大价值呢？我们只需要维护前缀和 $pre_i = \sum\limits_{j=1}^i a_j$ 以及后缀 $\max$ 值 $maxn_i = \max\limits_{j = i}^n pre_j$，最大价值即为 $maxn_l - pre_{l - 1}$ 。时间复杂度为 $O(nm)$ 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
 
template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}
 
template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}
 
const int MAXN = 3e5;
const LL INF = 1e16;
int n, m, k, a[MAXN + 5];
LL ans, pre[MAXN + 5], maxn[MAXN + 5];
 
inline LL solve(int x) {
    for (int i = 1; i <= n; ++i) {
        pre[i] = pre[i - 1] + a[i];//预处理前缀和 
        if (i % m == x) pre[i] -= k;//从第 x 个数开始，每隔 m 个数就要减去 k 
    }
    for (int i = n; i; --i) maxn[i] = max(maxn[i + 1], pre[i]);
    //预处理后缀 max 值 
    LL res = 0;
    for (int i = x; i <= n; i += m) {//枚举左端点 
        if (!i) continue;//l = 0 时不合法，跳过
        res = max(res, maxn[i] - pre[i - 1]);//求最大值 
    }
    return res;
}
 
int main() {
    read(n), read(m), read(k);
    for (int i = 1; i <= n; ++i) read(a[i]);
    maxn[n + 1] = -INF;//可能有负数，所以要初始化为 -∞
    for (int i = 0; i < m; ++i) ans = max(ans, solve(i));
    write(ans);
    putchar('\n');
    return 0;
}