自动搬运

查看原文

来自洛谷，原作者为

	szh_AK_all S挂分挂到被洛谷7级勾卡线|I can do all things

搬运于2025-08-24 22:55:38，当前版本为作者最后更新于2024-05-06 13:08:02，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

双倍经验

为什么楼下题解写的那么麻烦，我来一篇简单易懂的题解。

首先由于桶是环形排列的，所以为了方便起见，将原序列复制一遍，这样便将环展开了。

部分代码

int n;
cin >> n;
for (int i = 1; i <= n; i++)
	cin >> a[i];
for (int i = n + 1; i <= n + n; i++)
	a[i] = a[i - n];

接下来定义两个数组 $l,r$，其中 $l_i$ 表示左边第一个牛奶量比 $a_i$ 小的桶的位置，$r_i$ 表示右边第一个牛奶量不比 $a_i$ 大的桶的（这样定义的用处见下文可知，并且这样定义容易求出 $l,r$ 数组）。

考虑如何求得 $l$ 数组。

对于边界情况，即 $i=1$ 时，显然，由于 $i$ 左边没有桶了，所以 $l_i=0$；那么对于 $i>1$ 的情况，首先可以得到如下暴力代码：

for (int i = 2; i <= n; i++) {
  for (int j = i - 1; j >= 1; j--) {
    	if (a[j] < a[i]) {
          l[i] = j;
          break;
        }
  }
}

那么这种暴力方法的时间输在了哪里呢？假设桶的牛奶量序列为 1 10000000 100000000 4 3 2，那么在求答案过程中，第 $2,3$ 个位置会经过多次，但是显然，凭借肉眼观察也能得知，第 $2,3$ 个位置的桶的牛奶量太大了，对 $l$ 数组不会有贡献。

如上的例子便启发我们，可以尽量避开一些对答案不会有影响的位置。假设目前考虑到了第 $i-1$ 个位置的桶的牛奶量是否小于第 $i$ 个位置的桶的牛奶量，则分为两种情况：一、$a_{i-1}<a_{i}$，则直接更新 $l_i$ 即可；二、$a_{i-1}\ge a_{i}$，则开始考虑避开一些对答案不会有影响的位置。

反过头来看看 $l$ 的定义：$l_i$ 表示左边第一个牛奶量比 $a_i$ 小的桶的位置，那这是不是代表第 $i-1$ 至第 $l_i+1$ 个位置的桶的牛奶量都是不小于第 $i$ 个位置的桶的牛奶量？显然是的，又因为 $a_{i-1}\ge a_i$，所以 $a_k\ge a_i(i-1\ge k\ge a_{i-1})$，也就是说，第 $i-1$ 至第 $l_i+1$ 个位置的桶对答案没有影响。那么可以一个个跳 $j$，若 $a_j<a_i$，则更新 $l_i$；否则，$j=l_j$。

求得 $r$ 数组的方法是类似的。

复杂度是均摊的。

部分代码：

l[1] = 0;
for (int i = 2; i <= n + n; i++) {
	int x = i - 1;
	while (a[x] >= a[i] && x != 0)
		x = l[x];
	l[i] = x;
}//预处理左边第一个比a[i]小的
r[n + n] = n + n + 1;
for (int i = n + n - 1; i >= 1; i--) {
	int x = i + 1;
	while (a[x] > a[i] && x != 0 && x != n + n + 1)
		x = r[x];
	r[i] = x;
}//预处理右边第一个不比a[i]大的

接下来便是真正求答案的时刻了。

可以依次枚举每个位置对总答案产生的贡献，先来看个例子（也就是样例一）。

其中，黑色箭头指的是当前所考虑的 $i$ 为 $6$，黄色箭头指的是 $l_i=2$，蓝色箭头指的是 $r_i=7$，那么，可以发现，仅有绿色区域的牛奶会在第 $r_i$ 个位置损失，且这个绿色区域恰好是个矩形。那么，根据绿色区域的贡献，在第 $1$ 秒，牛奶会损失 $1$（也就是矩形的宽），在第 $2$ 秒牛奶会再损失 $1$，直到第 $4$（也就是矩形的长）秒，牛奶一直会损失 $1$。所以可以归纳出做法：

假设牛奶损失的值为其贡献值，则在计算每一秒所有桶的牛奶量总和时也就是用牛奶起初的总量减去这一秒牛奶的总贡献值。那么对于绿色区域，在第 $1$ 至第 $4$ 秒，牛奶的总贡献值会逐渐增加一，这正好可以用二阶差分来处理。下面列出表格，方便观察差分数组（设 $c$ 为矩形的长，$k$ 为矩形的宽）。 | 数组/下标 | $1$ | $2$ | $\dots$ | $c$ | $c+1$ | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | |总贡献值变化数组 |$+k$ | $+2k$ | $\dots$ | $+ck$ | $+ck$ | | 差分 $1$ | $+k$ | $+k$ |$+k$ | $+k$| $+0$| |差分 $2$| $+k$ | $+0$| $+0$ |$+0$ | $-k$|

这样看便很直观了。

考虑如何求 $c,k$。

可以发现，矩形的长为 $r_i-l_i-1$（范围是 $l_i+1$ 至 $r_i-1$），那么宽呢（也可以看成是高）？观察图片可知，在绿色区域上方的 $3$ 格牛奶并不会在 $r_i$ 这个位置损失，也就是说，这个绿色区域的左右两边的高度应该是相同的（正好印证了绿色区域是个矩形），而绿色区域的宽则要最大化左右两边相同的高度（因为牛奶可以损失便一定会损失）。

再来思考下 $l$ 数组的特性，在第 $l_i+1$ 至第 $i-1$ 个位置的桶的牛奶量不小与 $a_i$，而因为绿色区域的左边部分在 $l_i$ 的右上角，所以这也就代表了绿色区域的最低部分的高度高于 $a_{l_i}$；同理，对于 $r$ 数组，可以得知绿色区域的最低部分的高度高于 $a_{r_i}$。由于 $a_i$ 是在 $a_{l_{i}+1,l_{i}+2,\dots r_i-1}$ 中最小的，所以这代表绿色区域的最高部分不超过 $a_i$，由此，可以算出 $k$。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[200005];
int l[200005], r[200005];
int ans[200005];

signed main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = n + 1; i <= n + n; i++)
		a[i] = a[i - n];
	l[1] = 0;
	for (int i = 2; i <= n + n; i++) {
		int x = i - 1;
		while (a[x] >= a[i] && x != 0)
			x = l[x];
		l[i] = x;
	}//预处理左边第一个比a[i]小的
	r[n + n] = n + n + 1;
	for (int i = n + n - 1; i >= 1; i--) {
		int x = i + 1;
		while (a[x] > a[i] && x != 0 && x != n + n + 1)
			x = r[x];
		r[i] = x;
	}//预处理右边第一个不比a[i]大的
	int tmp = 0;
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i] < a[tmp] || tmp == 0)
			tmp = i;
		sum += a[i];
	}//找到高度最小的
	for (int i = tmp + 1; i <= tmp + n; i++) {
		if (a[i] == a[tmp])
			continue;
		//长方形的长：r[i]-l[i]-1；长方形的宽：a[i]-max(a[l[i]]+1,a[r[i]]+1)+1
		int chang = r[i] - l[i] - 1, kuan = a[i] - max(a[l[i]] + 1, a[r[i]] + 1) + 1;
		ans[1] += kuan;
		ans[chang + 1] -= kuan;
	}
	for (int i = 1; i <= n; i++)
		ans[i] += ans[i - 1];
	for (int i = 1; i <= n; i++)
		ans[i] += ans[i - 1];
	for (int i = 1; i <= n; i++)
		cout << sum - ans[i] << " ";
}

当然还有几个细节：

• 由于要计算每个桶的贡献，所以应从长度为 $2n$ 的序列中截取长度为 $n$ 的子段。设子段的左端点是 $left$，右端点是 $left+n-1$，则应让 $a_{left-1}$ 最小，也代表着 $a_{left+n-1}$ 最小。使得遇到的 $r_i\le left\le 2n(a_i\ne a_{left-1})$，做到不错算贡献值。

• 若 $a_i=a_{left-1}$，则直接跳过该点。

路过的各位请给个赞吧！