浅谈偏序问题与K-D Tree

· · 个人记录

I.偏序问题

我们在我们要处理的信息上，加以若干不等式的限制

1.逆序对

比如我们通常做的逆序对，实质就是二维偏序

ans=\sum _{i=1} ^n {\sum _{j=1} ^{i-1}1\ (a[j]>a[i])}

对于每一个i，就是看有多少个j满足：

j<i\ ,\ a[j]>a[i]

那么这个不等式组中有两个维度，一个是j<i，对下标的限制，还有一维是a[j]>a[i]，是对值的限制

那么这个玩意就叫个二维偏序

处理这个玩意的方法有很多，归并排序这里不讲

有种权值线段数组/线段树/平衡树的方法，当然，选择树状数组最简单

由于树状数组处理前缀和只需要跑一次，而区间和要跑两次，所以我们把这个偏序式子反过来变成j>i \ , \ a[j]<a[i]会好做一点

对于第一维j>i，我们从for一遍i从n扫到1，开个数据结构存之前扫过的信息就满足的第一维

对于第二维a[j]<a[i]，在权值树状数组中查询[-inf,a[i])的和记入答案即可，然后把a[i]插入权值树状数组中(a[i]的权值+1)

大部分题目的值域都比较大，一般要先离散化(如果写平衡树就不用了)

一般二维偏序问题

因为逆序对这个玩意其中一维是j<i，这个玩意因为是对下标的限制，所以for一遍扫即可

当其中一维不是下标的时候，每个位置有两个权值a[],b[]，一般式子可以写成

la<=a[i]<=ra,lb<=b[i]<=rb

其中[la,ra]是该询问对a值域的限制,[lb,rb]同理

然后通常可能每个位置还会伴随着一个权值c[]

这个权值不参与偏序的限制，只作为答案的贡献

比如求和的就是：\sum c[i],(la<=a[i]<=ra,lb<=b[i]<=rb)

或者可以改成求最大值：\max \left \{c[i] \right \}.......

这种玩意如果是静态的，通常可以先按照某一维排序，然后该维按位置扫的时候它就是单调的

比如我a[j]<a[i],b[j]>b[i]，可以按照a从小到大排序，然后就变成了j<i,b[j]>b[i]，然后就变成逆序对了

高维偏序

通常三维偏序可以排序降维成二维偏序，然而一般的树状数组/线段树/平衡树是无法直接处理二维偏序问题的，这时候我们就需要高级数据结构了

处理偏序问题的利器：K-D Tree,cdq分治，主席树，树套树，四分树(二维线段树)，二/高维bit，甚至你还能莫队+值域分块

其实二维偏序可以想象成一个矩形的限制，所以又称矩形数点，但我喜欢叫二维偏序因为听起来b格比较高，对于a<=x<=b,c<=y<=d的限制，就可以想象成以(a,c)为左下角，以(b,d)为右上角的矩形

三维偏序就能想象成长方体，四维就想象不过来了…

II.K-D Tree

### 1.建树 kdt最常用且最好写的构造方法是中值建树，它是的实质是一个bst(二叉搜索树) 假设树根的深度是0，第i维坐标表示为d[i]，那么对于第i层的某个的节点，将其管辖范围内的点按照第i%k维排序，取中位数当作它本身代表的点，在中位数左边的作其左子树，右边的作右子树 比如现在平面上有这么一坨点，我们要对其建一棵2dt ![](https://cdn.luogu.com.cn/upload/image_hosting/bcoy8wb8.png) 第一次我们找按照x坐标排序的中位数，八个点就找第四个，就是B，然后过B作y轴的平行线 ![](https://cdn.luogu.com.cn/upload/image_hosting/88mhqwrc.png) 把平面分割成了两个部分，左侧有ACF 右侧有DEGH 这时候B就是整个kdt的根节点，左子树是{A,C,F}，右子树是{D,E,G,H}，然后目前树长这样 ![](https://cdn.luogu.com.cn/upload/image_hosting/m2ns2psd.png) 圆圈节点代表已经确定建好的节点 方框是子树包含的点，但目前还没确定这些点的具体结构关系 ![](https://cdn.luogu.com.cn/upload/image_hosting/si6kt1yd.png) 然后我们在B分割后左侧区域找按y坐标排序的中位数，找到了点C，然后作一条x轴平行线，将B左侧分割成了上下两部分{A},{F}，然后C就是B的直接左儿子，{A}作C的左子树，{F}作C的右子树，然后又因为{A},{F}只有一个点，所以成为了直接儿子，然后树长这样 ![](https://cdn.luogu.com.cn/upload/image_hosting/1e33azcy.png) 然后同理我们可以确定B右子树的形态，最终把平面分割成这样子 ![](https://cdn.luogu.com.cn/upload/image_hosting/w1llwu2s.png) 某个区域内只有一个点的就懒得画线了 然后分的时候G的左侧是空的，所以它没有左儿子 最终我们建出来的树长这样 ![](https://cdn.luogu.com.cn/upload/image_hosting/90i7xzir.png) ### 2.基础性质： #### (1)显然树高O(log n) #### (2)对于深度为t的节点p，其左子树的所有节点代表的点q的q.d[t%k]<=p.d[t%k]，右子树q.d[t%k]>=p.d[t%k] #### (3)每个树节点对应着空间中的唯一节点，所以空间复杂度O(n) ### 3.节点信息： ~~变量名爱叫啥叫啥~~ 先定义一个结构体表示空间内一个点 ```cpp int f; struct point { int d[k]; //int w;表示权值信息 如果需要的话 inline const point(int x=0,int y=0){d[0]=x;d[1]=y;} inline const bool operator<(const point &p)const { if (d[f]^p.d[f])return d[f]<p.d[f]; for (int i=0;i<K;i++) if (i^f&&d[i]^p.d[i]) return d[i]<p.d[i]; } /*大多时候用不到 inline const bool operator==(const point &p)const { for (int i=0;i<K;i++) if (d[i]^p.d[i]) return 0; return 1; } */ }; ``` f表示当前建树的时候按照第f维排序 #### (1)point range: 该节点代表的空间的点 #### (2)point mn,mx: mn.d[i]代表子树内第i维坐标的最小值,mx同理 **其实kdt上每个子树代表着一个k维空间，比如2dt就是平面上的几个矩形，mn就是矩形的左下角，mx就是矩形的右上角** #### (3)tree *son[2]: 我喜欢写指针，所以定义成了指针类型，代表着该节点的左(0)右(1)儿子 #### (4)权值信息 比如可以是size子树大小 如果这些点有点权，可以有什么子树点权最大最小值，点权和之类的玩意 ```cpp struct tree { int size; tree *son[2]; point range,mn,mx; inline const void pushup() { size=son[0]->size+1+son[1]->size; //以维护size为例 for (int i=0;i<k;i++) mn.d[i]=min(range.d[i],min(son[0]->mn.d[i],son[1]->mn.d[i])), mx.d[i]=max(range.d[i],max(son[0]->mx.d[i],son[1]->mx.d[i])); } }memory_pool[N],*tail,*null,*root; ``` ### 4.初始化&建树代码 ```cpp inline const void init()//初始化 { tail=memory_pool; null=tail++; root=null->son[0]=null->son[1]=null; for (int i=0;i<k;i++)null->mx.d[i]=-inf,null->mn.d[i]=inf; } inline tree *spawn(const point &p)//新建一个节点 { tree *p=tail++; p->size=1; p->range=p->mx=p->mn=x; p->son[0]=p->son[1]=null; return p; } inline tree *build(int l,int r,int d)//d代表当前按第d维排序 { if (l>r)return null; int mid=l+r>>1;f=d; nth_element(a+l,a+mid,a+r+1); //需要algorithm，可以在单次O(n)时间内找出中位数放在mid并把小的放mid左边大的放mid右边 tree *p=spawn(a[mid]); if (l==r)return p; p->son[0]=build(l,mid-1,(d+1)%k); p->son[1]=build(mid+1,r,(d+1)%k); p->pushup(); return p; } ``` 注意到我们每次都使用了个nth_element()函数，调用一次是O(n)的，但是我们kdt树高是log，同一层排序的区域合起来是一个n，log层就是nlogn，所以建树的时间复杂度是$O(n \ log \ n)$的 ### 5.二维偏序与矩形 ![](https://cdn.luogu.com.cn/upload/image_hosting/o6e6oj0o.png) 这是我们刚刚那棵树，现在我在上面画了每个节点的mn和mx信息，绿字左边的点代表mn，右边的代表mx ![](https://cdn.luogu.com.cn/upload/image_hosting/rlqn1p6e.png) 比如我们看E，它的mn是(10,4),mx(18,9) 然后我们以Emn(10,4)为左下角，Emx(18,9)为右上角绘制一个矩形，这个青色矩形就是E这棵子树所代表的矩形，它恰好包住了E这棵子树内的所有点 2dt每个子树能代表一个矩形，3dt每个子树就能代表一个长方体，以此类推.. ### 6.查询 首先最基础的操作是**矩形数点**，查左下角为点a,右上角为点b的矩形中有多少个已知点 那么当我们访问到2dt的某个节点的时候，这个子树代表的矩形和询问矩形有几种关系： #### (1)查询矩形完全包含子树代表矩形 比如这样 ![](https://cdn.luogu.com.cn/upload/image_hosting/eyabw50v.png) 青色(被覆盖成绿色)的矩形(就是子树E代表的矩形)被黄色的矩形完全包住 回忆一下我们线段树如何判断查询区间[L,R]完全包含节点区间[l,r]： ```cpp if (l>=L&&r<=R)return size; ``` 然后变成矩形之后，子树矩形左下角(l1,r1),右上角(l2,r2)在询问矩形左下角(L1,R1),右上角(L2,R2)中的情况就是： ```cpp if (l1>=L1&&r1<=R1&&l2>=L2&&r2<=R2)return size; ``` 广泛性更强地，k维空间的包含即： ```cpp inline const bool in(const point &lower,const point &upper) { for (int i=0;i<k;i++) if (!(mn.d[i]>=lower.d[i]&&mx.d[i]<=upper.d[i])) return 0; return 1; } ``` #### (2)查询矩形与子树矩形没有交集 就像这样 ![](https://cdn.luogu.com.cn/upload/image_hosting/yjlojwag.png) 同理： ```cpp inline const bool out(const point &lower,const point &upper) { for (int i=0;i<k;i++) if (mn.d[i]>upper.d[i]||mx.d[i]<lower.d[i]) return 1; return 0; } ``` #### (3)查询矩形与子树矩形有交集但没有包含关系 类似线段树，这时候我们需要去访问这个点的左右儿子了 但是由于线段树的非叶节点没有自身信息，而kdt本质是bst，每个节点代表了空间内一个点，所以在走儿子之前还要先看一下自己这个点是不是在矩形中: ```cpp inline const bool at(const point &lower,const point &upper) { for (int i=0;i<k;i++) if (!(range.d[i]>=lower.d[i]&&range.d[i]<=upper.d[i])) return 0; return 1; } ``` 然后矩形数点就像这样 ```cpp inline const int query(tree *p,const point &x,const point &y) { if (p==null)return 0; if (p->out(x,y))return 0; if (p->in(x,y))return p->size; return p->at(x,y)+query(p->son[0],x,y)+query(p->son[1],x,y); } ``` ### 6.查询小优化 如果按照上面那样求矩形内点权的极值，可能会有点小问题，以最大值为例 我们把mx的点权作为其子树内的点权最大值，也就是pushup的时候多加一句话： ```cpp mx.w=max(range.w,max(son[0]->mx.w,son[1]->mx.w)); ``` 然后能够写出基础查询写法： ```cpp inline const int query(tree *p,const point &x,const point &y) { if (p==null)return -inf; if (p->out(x,y))return -inf; if (p->in(x,y))return p->mx.w; return max(p->at(x,y)?p->range.w:-inf,max(query(p->son[0],x,y),query(p->son[1],x,y))); } ``` 这样子容易被卡常，比如[TATT](https://www.luogu.org/problem/P3769)这个题，我这么写最高91分，直到我写成这样： ```cpp int mx; inline const void query(tree *p,const point &x,const point &y) { if (p==null)return; if (p->mx.w<=mx)return; //如果这个子树的点权最大值比当前搜过的最大值还要小的话，那就没有必要继续走这棵子树了 if (p->out(x,y))return; if (p->in(x,y))return mx=p->mx.w,void(); //前面那个剪枝保证了子树最大值比当前答案要大，直接覆盖 if (p->at(x,y))mx=max(mx,p->range.w); query(p->son[0],x,y);query(p->son[1],x,y); } ``` ### 7.权值修改 #### (1)单点修改 从根往下依着顺序找就好了，回溯记得更新 ```cpp inline const void modify(tree *p,const point &x,int y,int d) { if (p->range==x)return p->range.w=y,p->pushup(); f=d;modify(p->son[p->range<x],x,y,(d+1)%k); p->pushup(); } ``` #### (2)范围修改 按照查询的格式 查询范围与当前范围没有交集返回空 查询范围包含当前范围打上修改标记并返回 单点包含就只改自己的然后pushup一下 然后一波pushdown往左右儿子走 然后因为本来kd树常数就非常大，所以我们一般进行标记永久化，比如要矩形加，最后查每个数的值 ```cpp inline const void add(tree *p,const point &x,const point &y,const int &w) { if (p==null)return; if (p->out(x,y))return; if (p->in(x,y))return p->add+=w,void(); if (p->at(x,y))p->range.w+=w; add(p->son[0],x,y,w);add(p->son[1],x,y,w); } inline const void check(tree *p,ll add) { if (p==null)return; ans[p->range.id]=p->range.w+(add+=p->add); check(p->son[0],add);check(p->son[1],add); } ``` 把根下来的所有标记累下来加上自己即可 ### 8.复杂度 #### 空间复杂度:O(n) #### 时间复杂度: 建树$O(n\ log \ n)

插入(后面会讲怎么做)O(n \ log \ n)

单次查询O(n^{\frac {k-1}{k}})

例如：当k=2时，即处理平面问题的时候，就是O(\sqrt n)

III. KD树与近邻/远离问题

经典运用:

求一个点到所有已知点中的最短距离

这个距离可以是曼哈顿距离，也可以是欧几里得距离，以平面为例

平面曼哈顿距离:|x1-x2|+|y1-y2|

平面欧氏距离:\sqrt{(x1-x2)^2+(y1-y2)^2}

以小及大：

k维曼哈顿距离:\sum_{i=0} ^{k-1}|a.d[i]-b.d[i]|

k维欧氏距离:\sqrt{\sum_{i=0} ^{k-1}(a.d[i]-b.d[i])^2}

inline const friend int manhattan(const point &a,const point &b)
{
    int dis=0;
    for (int i=0;i<k;i++)
        dis+=abs(a.d[i]-b.d[i]);
    return dis;
}
inline const friend int sqr_euclid(const point &a,const point &b)
{
    int dis=0;
    for (int i=0;i<k;i++)
        dis+=sqr(a.d[i]-b.d[i]);//sqr(x)表示x的平方，为了避免开根号的精度误差，先用平方算，输出再开根
    return 0;
}

那么我们如何查询一个点q到所有已知点的最小距离呢？以曼哈顿距离为例

最暴力地我们肯定要遍历整棵树一遍遍比较距离，显然一次O(n)

我们考虑如何去优化这个暴力，比如我们走到哪一棵子树之后发现这整棵子树都不可能成为答案，我们可以去剪枝，一个子树代表了一个矩形，我们可以设计一个估价函数，类似A*算法，计算一个点到矩形的最近/远距离

如图，需要分类讨论，以矩形的两组对边为平行线组分割成九个区域，看图意会一下，第一行是最小，第二行是最大

综合一下，我们可以设计估价函数

inline const int fmin(const point &x)
{
    int f=0;
    for (int i=0;i<k;i++)
        f+=max(mn.d[i]-x.d[i],0)+max(x.d[i]-mx.d[i],0);
    return f;
}
inline const int fmax(const point &x)
{
    int f=0;
    for (int i=0;i<k;i++)
        f+=max(abs(mn.d[i]-x.d[i]),abs(mx.d[i]-x.d[i]));
    return f;
}

然后我们在树上搜索的时候，子树的最小估价不比当前搜过的答案小，那整个子树就没有意义了，剪枝掉。左右儿子哪个估价更小就先走哪边

int mn,mx;
inline const void querymin(tree *p,const point &x)
{
    mn=min(mn,manhattan(p->range,x));
    int f[2]={inf,inf};
    if (p->son[0]!=null)f[0]=p->son[0]->fmin(x);
    if (p->son[1]!=null)f[1]=p->son[1]->fmin(x);
    bool t=f[0]>=f[1];
    if (f[t]<mn)querymin(p->son[t],x);t^=1;
    if (f[t]<mn)querymin(p->son[t],x);
}
inline const void querymax(tree *p,const point &x)
{
    mx=max(mx,manhattan(p->range,x));
    int f[2]={-inf,-inf};
    if (p->son[0]!=null)f[0]=p->son[0]->fmax(x);
    if (p->son[1]!=null)f[1]=p->son[1]->fmax(x);
    bool t=f[0]<=f[1];
    if (f[t]>mx)querymin(p->son[t],x);t^=1;
    if (f[t]>mx)querymin(p->son[t],x);
}

类似地，欧氏距离只需要加个平方就好了

inline const int fmin(const point &x)
{
    int f=0;
    for (int i=0;i<k;i++)
        f+=sqr(max(mn.d[i]-x.d[i],0))+sqr(max(x.d[i]-mx.d[i],0));
    return f;
}
inline const int fmax(const point &x)
{
    int f=0;
    for (int i=0;i<k;i++)
        f+=max(sqr(mn.d[i]-x.d[i]),sqr(mx.d[i]-x.d[i]));
    return f;
}

IV.动态K-DTree

如果我要在kd树插入一个新点，类似bst，容易形成一条长链导致复杂度退化

而如果我用旋转平衡树的方式旋转kd树，显然不太可行，因为kdt的不同深度的排序规则有所不同

这时候我们就想到了替罪羊树，引入平衡因子\alpha，设计失衡函数

inline const bool unbalanced()
{
    return son[0]->size>size*alpha||son[1]->size>size*alpha;
}

每次插入后找到最浅的失衡节点，然后暴力拍扁，也许需要开个垃圾桶回收

point a[N]; //回收的点
tree *recycle[N]; //垃圾桶，装载回收的内存
int top,cnt,flag; //代表垃圾桶大小，回收了多少个点，重构子树根的深度
inline tree *spawn(const point &x)
{
    tree *p=top?recycle[--top]:tail++;
    p->size=1;
    p->mx=p->mn=p->range=x;
    p->son[0]=p->son[1]=null;
    return p;
}
inline const void travel(tree *p)
{
    if (p==null)return;
    travel(p->son[0]);
    a[++cnt]=p->range;recycle[top++]=p;
    travel(p->son[1]);
}
inline tree *build(int l,int r,int d)
{
    if (l>r)return null;
    int mid=l+r>>1;f=d;
    nth_element(a+l,a+mid,a+r+1);
    tree *p=spawn(a[mid]);
    if (l==r)return p;
    p->son[0]=build(l,mid-1,(d+1)%k);
    p->son[1]=build(mid+1,r,(d+1)%k);
    p->pushup();
    return p;
}
inline const void rebuild(tree *&p,int d)
{
    cnt=0;
    travel(p);
    p=build(1,cnt,0);
}
inline tree **insert(tree *&p,const point &x,int d)
{
    if (p==null)return p=spawn(x),&null;
    f=d;tree **bad=insert(p->son[p->range<x],x,(d+1)%k);
    p->pushup();
    if (p->unbalanced())bad=&p,flag=d;
    return bad;
}
public:
inline const void insert(int x,int y)
{
    tree **bad=insert(root,point(x,y),flag=0);
    if (*bad==null)return;
    rebuild(*bad,flag);
}

V.模板题代码&简单偏序题目分析

推出了偏序式子，就可以用kdt实现

二维偏序出来第一维的限制是[l1,r1],第二维的限制是[l2,r2]，就可以在kdt上查左下角(l1,l2)右上角(r1,r2)的矩形了，高维同理

平面最近点对

#include<map>
#include<cmath>
#include<cfloat>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef double dbl;
const int N=2e5+10,K=2;
int n;
bool f;
map<pair<dbl,dbl>,int>m;
dbl ans=DBL_MAX;
inline const dbl sqr(dbl x)
{
    return x*x;
}
struct point
{
    dbl d[K];
    inline const bool operator<(const point &p)const
    {
        return d[f]<p.d[f];
    }
    inline const bool operator==(const point &p)const
    {
        for (int i=0;i<K;i++)
            if (p.d[i]!=d[i])
                return 0;
        return 1;
    }
    inline const friend dbl sqr_euclid(const point &a,const point &b)
    {
        dbl dis=0;
        for (int i=0;i<K;i++)
            dis+=sqr(a.d[i]-b.d[i]);
        return dis;
    }
}a[N];
template<int K>class KD_Tree
{
    private:
        struct tree
        {
            tree *son[2];
            point range,mn,mx;
            inline const void pushup()
            {
                for (int i=0;i<K;i++)
                    mn.d[i]=min(range.d[i],min(son[0]->mn.d[i],son[1]->mn.d[i])),
                    mx.d[i]=max(range.d[i],max(son[0]->mx.d[i],son[1]->mx.d[i]));
            }
            inline const dbl fmin(const point &x)
            {
                dbl f=0.0;
                for (int i=0;i<K;i++)
                    f+=pow(max(mn.d[i]-x.d[i],0.0),2.0)+pow(max(0.0,x.d[i]-mx.d[i]),2.0);
                return f;
            }
        }memory_pool[N],*tail,*null,*root;
        inline const void init()
        {
            tail=memory_pool;
            null=tail++;
            null->son[0]=null->son[1]=null;
            for (int i=0;i<K;i++)
                null->mn.d[i]=DBL_MAX,
                null->mx.d[i]=DBL_MIN;
            root=null;
        }
        inline tree *spawn(const point &x)
        {
            tree *p=tail++;
            p->range=p->mn=p->mx=x;
            p->son[0]=p->son[1]=null;
            return p;
        }
        inline const void querymin(tree *p,const point &x)
        {
            ans=min(ans,x==p->range?DBL_MAX:sqr_euclid(x,p->range));
            dbl d[2]={DBL_MAX,DBL_MAX}; //因为查询的点是树中的点，如果搜到它自己了必将影响答案为0，特判一下
            if (p->son[0]!=null)d[0]=p->son[0]->fmin(x);
            if (p->son[1]!=null)d[1]=p->son[1]->fmin(x);
            bool t=d[0]>=d[1];
            if (d[t]<mn)querymin(p->son[t],x);t^=1;
            if (d[t]<mn)querymin(p->son[t],x);
        }
        inline tree *build(int l,int r,bool d)
        {
            if (l>r)return null;
            int mid=l+r>>1;f=d;
            nth_element(a+l,a+mid,a+r+1);
            tree *p=spawn(a[mid]);
            if (l==r)return p;
            p->son[0]=build(l,mid-1,(d+1)%K);
            p->son[1]=build(mid+1,r,(d+1)%K);
            return p->pushup(),p;
        }
    public:
        inline KD_Tree(){init();}
        inline const void build()
        {
            root=build(1,n,0);
        }
        inline const void query(const point &x)
        {
            querymin(root,x);
        }
};
KD_Tree<K>kdt;
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&a[i].d[0],&a[i].d[1]);
        if (++m[make_pair(a[i].d[0],a[i].d[1])]>1)return puts("0.0000"),0; //有点重合直接输出0
    }
    kdt.build();
    for (int i=1;i<=n;i++)kdt.query(a[i]);
    printf("%.4lf\n",sqrt(ans)); //最后记得把方开回去
    return 0;
}

动态插入最近曼哈顿 P4169 [Violet]天使玩偶/SJY摆棋子

#include<cstdio>
#include<algorithm>
using std::nth_element;
template<class type>inline const void read(type &in)
{
    in=0;char ch=getchar();bool fh=0;
    while (ch<48||ch>57){if (ch=='-')fh=1;ch=getchar();}
    while (ch>47&&ch<58)in=(in<<3)+(in<<1)+(ch&15),ch=getchar();
    if (fh)in=-in;
}
template<class type>inline const void write(type out)
{
    if (out>9)write(out/10);
    putchar(out%10+48);
}
template<class type>inline const void writeln(type out)
{
    if (out<0)out=-out,putchar('-');
    write(out);
    putchar('\n');
}
template<class type>inline const type max(const type &a,const type &b)
{
    return a>b?a:b;
}
template<class type>inline const type min(const type &a,const type &b)
{
    return a<b?a:b;
}
const int N=6e5+10,K=2,inf=2147483647;
int n,m;
bool f;
struct point
{
    int d[K];
    inline point(int x=0,int y=0){d[0]=x;d[1]=y;}
    inline const bool operator<(const point &p)const
    {
        return d[f]<p.d[f];
    }
    inline const friend int manhattan(const point &a,const point &b)
    {
        int dis=0;
        for (int i=0;i<K;i++)dis+=abs(a.d[i]-b.d[i]);
        return dis;
    }
}a[N];
template<int k>class KD_Tree
{
    private:
        static const double alpha=0.5;
        struct tree
        {
            int size;
            tree *son[2];
            point range,mn,mx;
            inline const void pushup()
            {
                size=son[0]->size+1+son[1]->size;
                for (int i=0;i<k;i++)
                    mn.d[i]=min(range.d[i],min(son[0]->mn.d[i],son[1]->mn.d[i])),
                    mx.d[i]=max(range.d[i],max(son[0]->mx.d[i],son[1]->mx.d[i]));
            }
            inline const int evalue(const point &p)
            {
                int f=0;
                for (int i=0;i<k;i++)f+=max(mn.d[i]-p.d[i],0)+max(p.d[i]-mx.d[i],0);
                return f;
            }
            inline const bool unbalanced()
            {
                return son[0]->size>size*alpha||son[1]->size>size*alpha;
            }
        }memory_pool[N],*tail,*null,*recycle[N],*root;
        int top,flag,cnt,mn;
        inline const void init()
        {
            top=0;
            tail=memory_pool;
            null=tail++;
            null->son[0]=null->son[1]=null;
            for (int i=0;i<k;i++)
                null->mn.d[i]=inf,
                null->mx.d[i]=-inf;
            root=null;
        }
        inline tree *spawn(const point &x)
        {
            tree *p=top?recycle[--top]:tail++;
            p->son[0]=p->son[1]=null;
            p->range=p->mn=p->mx=x;
            p->size=1;
            return p;
        }
        inline const void travel(tree *p)
        {
            if (p==null)return;
            travel(p->son[0]);
            a[++cnt]=p->range;
            recycle[top++]=p;
            travel(p->son[1]);
        }
        inline tree *build(int l,int r,int d)
        {
            if (l>r)return null;
            int mid=l+r>>1;f=d;
            nth_element(a+l,a+mid,a+r+1);
            tree *p=spawn(a[mid]);
            if (l==r)return p;
            p->son[0]=build(l,mid-1,(d+1)%k);
            p->son[1]=build(mid+1,r,(d+1)%k);
            p->pushup();
            return p;
        }
        inline const void rebuild(tree *&p,int d)
        {
            cnt=0;
            travel(p);
            p=build(1,cnt,d);
        }
        inline const void query(tree *p,const point &x)
        {
            mn=min(mn,manhattan(x,p->range));
            int f[2]={inf,inf};
            if (p->son[0]!=null)f[0]=p->son[0]->evalue(x);
            if (p->son[1]!=null)f[1]=p->son[1]->evalue(x);
            bool t=f[0]>=f[1];
            if (f[t]<mn)query(p->son[t],x);t^=1;
            if (f[t]<mn)query(p->son[t],x);
        }
        inline tree **insert(tree *&p,const point &x,int d)
        {
            if (p==null)return p=spawn(x),&null;
            tree **bad=insert(p->son[p->range.d[d]<x.d[d]],x,(d+1)%k);
            p->pushup();
            if (p->unbalanced())bad=&p,flag=d;
            return bad;
        }
    public:
        inline const void build()
        {
            init();
            root=build(1,n,0);
        }
        inline const int query(int x,int y)
        {
            mn=inf;
            query(root,point(x,y));
            return mn;
        }
        inline const void insert(int x,int y)
        {
            tree **bad=insert(root,point(x,y),flag=0);
            if (*bad==null)return;
            rebuild(*bad,flag);
        }
};
KD_Tree<K>kdt;
int main()
{
    read(n);read(m);
    for (int i=1;i<=n;i++)
        for (int j=0;j<K;j++)
            read(a[i].d[j]);
    kdt.build();
    for (int opt,x,y;m--;)
        if (read(opt),read(x),read(y),opt&1)kdt.insert(x,y);
        else writeln(kdt.query(x,y));
    return 0;
}

P2184 贪婪大陆 题解

TATT

排序降维，将第一维从小到大排序，容易写出dp方程

f[i]=\max _{j<i} \left \{f[j] \right \}(b[j]<=b[i],c[j]<=c[i],d[j]<=d[i])

然后这是一个四维偏序求最大值，从头开始扫，即满足了第一维j<i，剩下三维上动态kdt即可

#include<cstdio>
#include<algorithm>
#define reg register
const int N=5e4+10,INF=1e9+10;
const short K=4;
template<class type>inline const type max(reg const type &a,reg const type &b)
{
    return a>b?a:b;
}
template<class type>inline const type min(reg const type &a,reg const type &b)
{
    return a<b?a:b;
}
template<class type>inline const void read(reg type &in)
{
    in=0;reg char ch=getchar();reg bool fh=0;
    while (ch<48||ch>57){if (ch=='-')fh=1;ch=getchar();}
    while (ch>47&&ch<58)in=(in<<3)+(in<<1)+(ch&15),ch=getchar();
    if (fh)in=-in;
}
short f;
int n,ans,flag;
struct point
{
    int d[K],w;
    inline point(int x=0,int y=0,int z=0){d[0]=x;d[1]=y;d[2]=z;}
    inline const bool operator<(reg const point &p)const
    {
        if (d[f]^p.d[f])return d[f]<p.d[f];
        for (reg short i=0;i<K-flag;i++)
            if (d[i]^p.d[i])
                return d[i]<p.d[i];
        return 0;
    }
}a[N];
template<short K>class kD_Tree
{
    private:
        const static double alpha=0.75;
        struct tree
        {
            int size,mxw;
            tree *son[2];
            point range,mn,mx;
            inline const void pushup()
            {
                size=son[0]->size+1+son[1]->size;
                mx.w=max(max(son[0]->mx.w,son[1]->mx.w),range.w);
                for (reg short i=0;i<K;i++)
                    mn.d[i]=min(range.d[i],min(son[0]->mn.d[i],son[1]->mn.d[i])),
                    mx.d[i]=max(range.d[i],max(son[0]->mx.d[i],son[1]->mx.d[i]));
            }
            inline const bool unbalanced()
            {
                return son[0]->size>size*alpha||son[1]->size>size*alpha;
            }
            inline const bool in(reg const point &a,reg const point &b)
            {
                for (reg short i=0;i<K;i++)
                    if (a.d[i]>mn.d[i]||b.d[i]<mx.d[i])
                        return 0;
                return 1;
            }
            inline const bool out(reg const point &a,reg const point &b)
            {
                for (reg short i=0;i<K;i++)
                    if (a.d[i]>mx.d[i]||b.d[i]<mn.d[i])
                        return 1;
                return 0;
            }
            inline const bool at(reg const point &a,reg const point &b)
            {
                for (reg short i=0;i<K;i++)
                    if (range.d[i]<a.d[i]||range.d[i]>b.d[i])
                        return 0;
                return 1;
            }
        }memory_pool[N],*tail,*null,*root,*recycle[N];
        int top,flag,rnk,mx;
        point b[N];
        inline const void init()
        {
            tail=memory_pool;
            null=tail++;
            root=null->son[0]=null->son[1]=null;
            for (reg short i=0;i<K;i++)null->mn.d[i]=INF,null->mx.d[i]=-INF;      
        }
        inline tree *spawn(reg const point &x)
        {
            reg tree *p=top?recycle[--top]:tail++;
            p->son[0]=p->son[1]=null;
            p->range=p->mn=p->mx=x;
            p->size=1;
            return p;
        }
        inline const void travel(reg tree *p)
        {
            if (p==null)return;
            travel(p->son[0]);
            b[++rnk]=p->range;
            recycle[top++]=p;
            travel(p->son[1]);
        }
        inline tree *build(reg int l,reg int r,reg short d)
        {
            if (l>r)return null;
            reg int mid=l+r>>1;f=d;
            std::nth_element(b+l,b+mid,b+r+1);
            tree *p=spawn(b[mid]);
            if (l==r)return p;
            p->son[0]=build(l,mid-1,(d+1)%K);
            p->son[1]=build(mid+1,r,(d+1)%K);
            return p->pushup(),p;
        }
        inline const void rebuild(reg tree *&p,reg int d)
        {
            rnk=0;
            travel(p);
            p=build(1,rnk,d);
        }
        inline const void query(reg tree *p,reg const point &a,reg const point &b)
        {
            if (p==null)return;
            if (p->mx.w<=mx)return;
            if (p->out(a,b))return;
            if (p->in(a,b))return mx=p->mx.w,void();
            if (p->at(a,b))mx=max(p->range.w,mx);
            query(p->son[0],a,b);query(p->son[1],a,b);
        }
        inline tree **insert(reg tree *&p,reg const point &x,reg short d)
        {
            if (p==null)return p=spawn(x),&null;
            tree **bad=insert(p->son[p->range.d[d]<x.d[d]],x,(d+1)%K);
            p->pushup();
            if (p->unbalanced())bad=&p,flag=d;
            return bad;
        }
    public:
        inline kD_Tree(){init();}
        inline const int query(reg const point &up)
        {
            mx=0;query(root,point(-INF,-INF,-INF),up);return mx;
        }
        inline const void insert(reg const point &p)
        {
            reg tree **bad=insert(root,p,flag=0);
            if (*bad==null)return;
            rebuild(*bad,flag);
        }
};
kD_Tree<K-1>kdt;
int main()
{
    read(n);
    for (reg int i=1;i<=n;i++)
        for (reg short j=0;j<K;j++)
            read(a[i].d[j]);
    std::sort(a+1,a+n+1);flag=1;
    for (reg int i=1;i<=n;i++)
        for (reg short j=0;j<K-1;j++)
            a[i].d[j]=a[i].d[j+1];
    for (reg int i=1;i<=n;i++)
        ans=max(ans,a[i].w=kdt.query(a[i])+1),
        kdt.insert(a[i]);
    printf("%d\n",ans);
    return 0;
}

P4357 [CQOI2016]K远点对

用个大根堆存答案，一开始塞2k个0，然后跑个平面最远点对最后输出堆顶即可