自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 22:39:21，当前版本为作者最后更新于2022-08-07 17:17:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

原题目名：赛之河原的垒石人

如果立方体柱子互不相邻那么答案就是 $4\sum \limits_{i=1}^nz_i$。如何处理柱子有相邻的情况？

在堆叠立方体的时候即可去处理柱子相邻的情况。不妨设在这个无穷大平面上，每个点 $(x,y)$ 上立方体的高度是 $G[x][y]$。则对于当前的点 $(x,y)$ 以及所有四相邻的点 $(x',y')$ 以及高度 $G[x'][y']$，若 $G[x][y]<G[x'][y']$，则 $G[x][y]$ 的存在会让从平面到 $G[x][y]$ 这一高度上的侧面面积“无效”化，因而减掉这一部分面积，即 $2 \times \min(z,G[x'][y']-G[x][y])$。需要对 $z$ 取 $\min$ 是避免减去重叠部分过多。例如就堆叠一个方块，那显然就不必减掉相邻柱子高度差那么多的重叠面积。

而如何去维护 $G$ 数组呢？可以使用 map 套 map 解决，也可以将二维平面降维到一维（例如对于一个坐标 $(x,y)$，将其变成 $x \times 10^6+y$）后使用一个 map<long long,long long> 去解决。本题没有卡 unordered_map，但是你要是 unordered_map 套 unordered_map 会被卡死。

答案最大是多少？显然是所有柱子都不相邻且最高的时候产生，即 $4n\max(z_i)=1.2 \times 10^{19}$，需要开 unsigned long long 才能通过本题。

#include <iostream>
#include <map>
using namespace std;
const int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
map <int,map<int,long long>> G;
unsigned long long ans;
int main()
{
    int n;
    cin >> n;
    for (int i=1;i<=n;i++)
    {
        int x,y;
        long long z;
        cin >> x >> y >> z;
        for (int j=0;j<4;j++)
        {
            int nx=x+dx[j],ny=y+dy[j];
            if (G[nx][ny]>G[x][y])
                ans-=2ull*min(z,G[nx][ny]-G[x][y]);
        }
        G[x][y]+=z;
        ans+=4ull*z;
        cout << ans << endl;
    }
    return 0;
}