2019牛客多校第八场 Distance

题意

三维空间中，两种操作，意思标记一个点，二是询问一个点，要求输出询问点与标记点的最小曼哈顿距离

题解1

分块Orz
先假设所有询问都在标记之后，那么我们一边 bfs 就可以求出答案
我们将操作每 $\sqrt{q}$q ​ 分成一块来处理
分为两类，标记和询问
当前块的标记操作先不标记，等整块的询问结束后再统一标记
每块，先 bfs 求出一个答案，复杂度 $nmh$nmh， 但这个并不是正确的答案，因为在这一块内有一些的询问之前要标记的点没有算，于是块内两两暴力就行了，复杂度 $q$q
总复杂度 $q\sqrt{q}$qq ​
太骚了，Orz

题解2

把 $n\times m\times h\le 10^5$n×m×h≤105 看成 $n,m,h\le 10^5$n,m,h≤105也是醉了。。。
最小曼哈顿距离 $\mid x-x^{\prime }\mid +\mid y-y^{\prime }\mid +\mid z-z^{\prime }\mid$∣x−x′∣+∣y−y′∣+∣z−z′∣
去绝对值后有8种情况
$(x+y+z)-(x^{\prime }+y^{\prime }+z)x\>x^{\prime },y\>y^{\prime },z\>z^{\prime }$(x+y+z)−(x′+y′+z)   x>x′,y>y′,z>z′
$(x+y-z)-(x^{\prime }+y^{\prime }-z)x\&gt;x^{\prime },y\&gt;y^{\prime },z\&lt;z^{\prime }$(x+y−z)−(x′+y′−z)   x>x′,y>y′,z<z′
$(x-y+z)-(x^{\prime }-y^{\prime }+z)x\&gt;x^{\prime },y\&lt;y^{\prime },z\&gt;z^{\prime }$(x−y+z)−(x′−y′+z)   x>x′,y<y′,z>z′
$(x-y-z)-(x^{\prime }-y^{\prime }-z)x\&gt;x^{\prime },y\&lt;y^{\prime },z\&lt;z^{\prime }$(x−y−z)−(x′−y′−z)   x>x′,y<y′,z<z′
$(-x+y+z)-(-x^{\prime }+y^{\prime }+z)x\&lt;x^{\prime },y\&gt;y^{\prime },z\&gt;z^{\prime }$(−x+y+z)−(−x′+y′+z)   x<x′,y>y′,z>z′
$(-x+y-z)-(-x^{\prime }+y^{\prime }-z)x\&lt;x^{\prime },y\&gt;y^{\prime },z\&lt;z^{\prime }$(−x+y−z)−(−x′+y′−z)   x<x′,y>y′,z<z′
$(-x-y+z)-(-x^{\prime }-y^{\prime }+z)x\&lt;x^{\prime },y\&lt;y^{\prime },z\&gt;z^{\prime }$(−x−y+z)−(−x′−y′+z)   x<x′,y<y′,z>z′
$(-x-y-z)-(-x^{\prime }-y^{\prime }-z)x\&lt;x^{\prime },y\&lt;y^{\prime },z\&lt;z^{\prime }$(−x−y−z)−(−x′−y′−z)   x<x′,y<y′,z<z′
建立8个树状数组，维护各种情况的最值就好了

代码

#include<bits/stdc++.h>
#define N 100010
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi 3.141592653589793
#define mod 998244353
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y) 
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef pair<int,int> pp;

int n,m,h,T;

struct BIT{
    int d[N];
    void init(){memset(d,128,sizeof d);}
    inline int f(int i,int j,int k){
        return (i-1)*m*h+(j-1)*h+k;
    } 
    inline void getmax(int &a,int b){
        if (b>a) a=b;
    }
    inline void updata(int x,int y,int z,int w){
        for(int i=x;i<=n;i+=i&-i)
            for(int j=y;j<=m;j+=j&-j)
                for(int k=z;k<=h;k+=k&-k) 
                    getmax(d[f(i,j,k)],w);
    }
    inline int sum(int x,int y,int z){
        int res=-INF;
        for (int i=x;i>0;i-=i&-i)
            for(int j=y;j>0;j-=j&-j)
                for(int k=z;k>0;k-=k&-k)
                    getmax(res,d[f(i,j,k)]);
        return res;
    }
}t[8];

int main(int argc, char const *argv[])
{
    for(int i=0;i<8;i++) t[i].init();
    sccc(n,m,h);sc(T);
    for(int i=1;i<=T;i++){
        int op,x,y,z;scc(op,x);scc(y,z);
        if (op==1){
            t[0].updata(x,y,z,x+y+z);
            t[1].updata(x,y,h-z+1,x+y-z);
            t[2].updata(x,m-y+1,z,x-y+z);
            t[3].updata(x,m-y+1,h-z+1,x-y-z);
            t[4].updata(n-x+1,y,z,-x+y+z);
            t[5].updata(n-x+1,y,h-z+1,-x+y-z);
            t[6].updata(n-x+1,m-y+1,z,-x-y+z);
            t[7].updata(n-x+1,m-y+1,h-z+1,-x-y-z);
        }else{
            int ans=INF;
            ans=min(ans,x+y+z-t[0].sum(x,y,z));
            ans=min(ans,x+y-z-t[1].sum(x,y,h-z+1));
            ans=min(ans,x-y+z-t[2].sum(x,m-y+1,z));
            ans=min(ans,x-y-z-t[3].sum(x,m-y+1,h-z+1));
            ans=min(ans,-x+y+z-t[4].sum(n-x+1,y,z));
            ans=min(ans,-x+y-z-t[5].sum(n-x+1,y,h-z+1));
            ans=min(ans,-x-y+z-t[6].sum(n-x+1,m-y+1,z));
            ans=min(ans,-x-y-z-t[7].sum(n-x+1,m-y+1,h-z+1));
            printf("%d\n",ans);
        }
    }
    return 0;
}