暴力三维树状数组求曼哈顿距离求最值——牛客多校第八场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[10];

int main(){
    for(int i=0;i<10;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==1){//更新 
            bit[0].update(x,y,z,x+y+z);
            bit[1].update(x,y,h-z+1,x+y-z);
            bit[2].update(x,m-y+1,z,x-y+z);
            bit[3].update(n-x+1,y,z,-x+y+z);
            bit[4].update(x,m-y+1,h-z+1,x-y-z);
            bit[5].update(n-x+1,y,h-z+1,-x+y-z);
            bit[6].update(n-x+1,m-y+1,z,-x-y+z);
            bit[7].update(n-x+1,m-y+1,h-z+1,-x-y-z); 
        }
        else {
            int ans=0x3f3f3f3f;
            update(ans,x+y+z-bit[0].query(x,y,z));
            update(ans,x+y-z-bit[1].query(x,y,h-z+1));
            update(ans,x-y+z-bit[2].query(x,m-y+1,z));
            update(ans,-x+y+z-bit[3].query(n-x+1,y,z));
            update(ans,x-y-z-bit[4].query(x,m-y+1,h-z+1));
            update(ans,-x+y-z-bit[5].query(n-x+1,y,h-z+1));
            update(ans,-x-y+z-bit[6].query(n-x+1,m-y+1,z));
            update(ans,-x-y-z-bit[7].query(n-x+1,m-y+1,h-z+1));
            cout<<ans<<'
';
        }
    }
}