自动搬运

查看原文

来自洛谷，原作者为

	Loyal_Soldier 一只小菜蛙 | 一只爱玩PVZ杂交版的蛙 | 天生我菜必有用，千金散尽还复来 | 这个人很菜，请忽略他的红名 | 小号@kaikai_qwq

搬运于2025-08-24 23:15:02，当前版本为作者最后更新于2025-08-16 09:49:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置知识：线段树。

思路

很明显，第 $2$ 种操作肯定比第 $1$ 种更优，我们要尽可能多的进行第 $2$ 种操作。

那么，对于每个长度为 $k$ 的区间，需要将每个数减去区间中最小的数，最后再计算剩余每个数的和。

显然，区间修改和区间最小值，就是线段树。于是，可以用线段树维护区间最小值和区间修改，时间复杂度 $O(n \log n)$，可以通过。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int a[N], w[N * 4], lzy[N * 4];//w 数组维护区间最小值，lzy 数组是懒标记
int n, m, ans;
void pushup(int u)
{
	w[u] = min(w[u * 2], w[u * 2 + 1]);
}
void build(int u, int l, int r)
{
	if(l == r)
	{
		w[u] = a[l];
		return;
	}
	int mid = (l + r) / 2;
	build(u * 2, l, mid);
	build(u * 2 + 1, mid + 1, r);
	pushup(u);
}//建树
void maketag(int u, int x)
{
	w[u] -= x;
	lzy[u] += x;
}
void pushdown(int u)
{
	maketag(u * 2, lzy[u]);
	maketag(u * 2 + 1, lzy[u]);
	lzy[u] = 0;
}
bool In(int L, int R, int l, int r)
{
	return (L >= l) && (R <= r);
}
bool Outof(int L, int R, int l, int r)
{
	return (L > r) || (R < l);
}
int query(int u, int L, int R, int l, int r)
{
	if(In(L, R, l, r)) return w[u];
	else if(!Outof(L, R, l, r))
	{
		int mid = (L + R) / 2;
		pushdown(u);
		return min(query(u * 2, L, mid, l, r), query(u * 2 + 1, mid + 1, R, l, r));
	}
	else return INT_MAX;
}//查询区间最小值
int Query(int u, int L, int R, int p)
{
	if(L == R) return w[u];
	int mid = (L + R) / 2;
	pushdown(u);
	if(p <= mid) return Query(u * 2, L, mid, p);
	else return Query(u * 2 + 1, mid + 1, R, p);
}//查询 p 位置的值
void update(int u, int L, int R,int l, int r, int x)
{
	if(In(L, R, l, r)) maketag(u, x);
	else if(!Outof(L, R, l, r))
	{
		int mid = (L + R) / 2;
		pushdown(u);
		update(u * 2, L, mid, l, r, x);
		update(u * 2 + 1, mid + 1, R, l, r, x);
		pushup(u);
	}
}//区间修改
signed main()
{
	cin >> n >> m;
	for(int i = 1;i <= n;i ++) cin >> a[i];
	build(1, 1, n);
	for(int i = 1;i + m - 1 <= n;i ++)
	{
		int qwq = query(1, 1, n, i, i + m - 1);//查询区间最小值
		ans += qwq;//增加答案
		update(1, 1, n, i, i + m - 1, qwq);//区间修改 
	}
	for(int i = 1;i <= n;i ++) ans += Query(1, 1, n, i);//累加剩余的数
	cout << ans;
	return 0;
}