维护一个满平面（每个整点都需要维护信息）的情况下，经测试似乎 KDT 比四分树略快（5%？）。

正题：

维护一个满平面（每个整点都需要维护信息）。

此人看到用时为他 1/10 的标程之后，盯着四分树陷入了沉思，并十分好奇这种东西怎么卡常。

struct ST{
    ll mx[N<<5],add[N<<5];
    int s[N<<5][4],size;
    void _add(int x,ll z){
        mx[x]+=z;
        add[x]+=z;
    }
    void pushdown(int x){
        if(add[x]){
            _add(s[x][0],add[x]);
            if(s[x][1]) _add(s[x][1],add[x]);
            if(s[x][2]){
                _add(s[x][2],add[x]);
                if(s[x][3]) _add(s[x][3],add[x]);
            }
            add[x]=0;
        }
    }
    void build(int p=1,int l0=0,int r0=lex,int l1=0,int r1=ley){
        s[p][0]=s[p][1]=s[p][2]=s[p][3]=add[p]=0;
        if(l0==r0&&l1==r1){
            mx[p]=b[l0][l1];
            return;
        }
        int mdx=(l0+r0)>>1,mdy=(l1+r1)>>1;
        build(s[p][0]=++size,l0,mdx,l1,mdy);
        if(l1!=r1) build(s[p][1]=++size,l0,mdx,mdy+1,r1);
        if(l0!=r0){
            build(s[p][2]=++size,mdx+1,r0,l1,mdy);
            if(l1!=r1) build(s[p][3]=++size,mdx+1,r0,mdy+1,r1);
        }
        mx[p]=max(max(mx[s[p][0]],mx[s[p][1]]),max(mx[s[p][2]],mx[s[p][3]]));
    }
    ll get(int x0,int y0,int x1,int y1,int c,int p=1,int l0=0,int r0=lex,int l1=0,int r1=ley){
        if(x0<=l0&&r0<=y0&&x1<=l1&&r1<=y1){
            _add(p,c);
            return(mx[p]-c);
        }
        pushdown(p);
        int mdx=(l0+r0)>>1,mdy=(l1+r1)>>1;
        ll re=0;
        if(x0<=mdx&&x1<=mdy) re=get(x0,y0,x1,y1,c,s[p][0],l0,mdx,l1,mdy);
        if(x0<=mdx&&y1>mdy&&s[p][1]) cmax(re,get(x0,y0,x1,y1,c,s[p][1],l0,mdx,mdy+1,r1));
        if(y0>mdx&&x1<=mdy&&s[p][2]) cmax(re,get(x0,y0,x1,y1,c,s[p][2],mdx+1,r0,l1,mdy));
        if(y0>mdx&&y1>mdy&&s[p][3]) cmax(re,get(x0,y0,x1,y1,c,s[p][3],mdx+1,r0,mdy+1,r1));
        mx[p]=max(max(mx[s[p][0]],mx[s[p][1]]),max(mx[s[p][2]],mx[s[p][3]]));
        return(re);
    }
}t;