题解：P10318 [SHUPC 2024] 彭罗斯水槽

· · 题解

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

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

部分代码

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] << " ";
}

当然还有几个细节：

路过的各位请给个赞吧！