题解 CF1197D 【Yet Another Subarray Problem】
Heartlessly
2019-07-23 18:34:58
## 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)$
## 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
```cpp
#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;
}
```