赛之河原的垒石人

· · 题解

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

如果立方体柱子互不相邻那么答案就是 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;
}