暴力三维树状数组求曼哈顿距离求最值——牛客多校第八场D

涉及的知识点挺多，但是大多是套路

1.求曼哈顿距离的最值一般对所有情况进行讨论

2.三维树状数组用来求前缀最大值

/*

有一个三维坐标系(x,y,z),取值范围为[1,n],[1,m],[1,h],有两种操作

1.在三维坐标系上更新一个点(x1,y1,z1)

2.给定一个点(x2,y2,z2),问在坐标系上离该点Manhattan距离最短的点

    即最小的 |x2-x1|+|y2-y1|+|z2-z1|

令 f=|x2-x1|+|y2-y1|+|z2-z1|,那么可以讨论去绝对值后f的八种情况

f0=(x2+y2+z2)-(x1+y1+z1),x2>=x1,y2>=y1,z2>=z1

f1=(x2+y2-z2)-(x1+y1-z1),x2>=x1,y2>=y1,x2<x1

...

    考虑如何求每种情况的最小值

    由于 x2+y2+z2 的值是固定的，只需要求出最大的符合条件的 x1+y1+z1即可，发现 x1<=x2 && y1<=y2 && z1<=z2这个条件刚好可以用三维树状数组来维护(求前缀最大值，单点更新)

    同理 八种情况都可以用八颗三维树状数组来维护

    另外 考虑 f1的条件 需要将 x1>x2转换成 n-x1+1<=n-x2+1 然后更新的是x1+y1-z1，查询的结果是最大的 x1+y1-z1

    其他情况同理

    (由于n*m*h<=1e5,所以用一个三维转一维的方式来存储)

*/

#include<bits/stdc++.h>

using namespace std;

#define maxn 300005

void update(int &a,int b){a=min(a,b);}

void Max(int &a,int b){a=max(a,b);}

int n,m,h,q;

struct Bit{

    int b[maxn];

    void init(){memset(b,-0x3f,sizeof b);}

    inline int id(int x,int y,int z){return x*m*h+y*h+z;}

    inline int lowbit(int x){return x&-x;}

    void update(int x,int y,int z,int val){//在[x,y,z]出更新值val

        for(int i=x;i<=n;i+=lowbit(i))

            for(int j=y;j<=m;j+=lowbit(j))

                for(int k=z;k<=h;k+=lowbit(k))

                    Max(b[id(i,j,k)],val);

    }

    int query(int x,int y,int z){//查询<=x,<=y,<=z的最大值

        int res=-0x3f3f3f3f;

        for(int i=x;i;i-=lowbit(i))

            for(int j=y;j;j-=lowbit(j))

                for(int k=z;k;k-=lowbit(k))

                    Max(res,b[id(i,j,k)]);

        return res;

    }

}bit[];

int main(){

    for(int i=;i<;i++)

        bit[i].init();

    cin>>n>>m>>h>>q;

    int x,y,z,op;

    while(q--){

        scanf("%d%d%d%d",&op,&x,&y,&z);

        if(op==){//更新

            bit[].update(x,y,z,x+y+z);

            bit[].update(x,y,h-z+,x+y-z);

            bit[].update(x,m-y+,z,x-y+z);

            bit[].update(n-x+,y,z,-x+y+z);

            bit[].update(x,m-y+,h-z+,x-y-z);

            bit[].update(n-x+,y,h-z+,-x+y-z);

            bit[].update(n-x+,m-y+,z,-x-y+z);

            bit[].update(n-x+,m-y+,h-z+,-x-y-z);

        }

        else {

            int ans=0x3f3f3f3f;

            update(ans,x+y+z-bit[].query(x,y,z));

            update(ans,x+y-z-bit[].query(x,y,h-z+));

            update(ans,x-y+z-bit[].query(x,m-y+,z));

            update(ans,-x+y+z-bit[].query(n-x+,y,z));

            update(ans,x-y-z-bit[].query(x,m-y+,h-z+));

            update(ans,-x+y-z-bit[].query(n-x+,y,h-z+));

            update(ans,-x-y+z-bit[].query(n-x+,m-y+,z));

            update(ans,-x-y-z-bit[].query(n-x+,m-y+,h-z+));

            cout<<ans<<'\n';

        }

    }

}