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

$KD \ Tree$,顾名思义,是处理$k$维空间的一种树形数据结构,以下简称kdt

1.建树

kdt最常用且最好写的构造方法是中值建树,它是的实质是一个bst(二叉搜索树)

假设树根的深度是0,第i维坐标表示为d[i],那么对于第i层的某个的节点,将其管辖范围内的点按照第i%k维排序,取中位数当作它本身代表的点,在中位数左边的作其左子树,右边的作右子树

比如现在平面上有这么一坨点,我们要对其建一棵2dt

第一次我们找按照x坐标排序的中位数,八个点就找第四个,就是B,然后过B作y轴的平行线

把平面分割成了两个部分,左侧有ACF 右侧有DEGH

这时候B就是整个kdt的根节点,左子树是{A,C,F},右子树是{D,E,G,H},然后目前树长这样

圆圈节点代表已经确定建好的节点 方框是子树包含的点,但目前还没确定这些点的具体结构关系

然后我们在B分割后左侧区域找按y坐标排序的中位数,找到了点C,然后作一条x轴平行线,将B左侧分割成了上下两部分{A},{F},然后C就是B的直接左儿子,{A}作C的左子树,{F}作C的右子树,然后又因为{A},{F}只有一个点,所以成为了直接儿子,然后树长这样

然后同理我们可以确定B右子树的形态,最终把平面分割成这样子

某个区域内只有一个点的就懒得画线了

然后分的时候G的左侧是空的,所以它没有左儿子

最终我们建出来的树长这样

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.节点信息:

变量名爱叫啥叫啥

先定义一个结构体表示空间内一个点

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子树大小

如果这些点有点权,可以有什么子树点权最大最小值,点权和之类的玩意

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.初始化&建树代码

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.二维偏序与矩形

这是我们刚刚那棵树,现在我在上面画了每个节点的mn和mx信息,绿字左边的点代表mn,右边的代表mx

比如我们看E,它的mn是(10,4),mx(18,9)

然后我们以Emn(10,4)为左下角,Emx(18,9)为右上角绘制一个矩形,这个青色矩形就是E这棵子树所代表的矩形,它恰好包住了E这棵子树内的所有点

2dt每个子树能代表一个矩形,3dt每个子树就能代表一个长方体,以此类推..

6.查询

首先最基础的操作是矩形数点,查左下角为点a,右上角为点b的矩形中有多少个已知点

那么当我们访问到2dt的某个节点的时候,这个子树代表的矩形和询问矩形有几种关系:

(1)查询矩形完全包含子树代表矩形

比如这样

青色(被覆盖成绿色)的矩形(就是子树E代表的矩形)被黄色的矩形完全包住

回忆一下我们线段树如何判断查询区间[L,R]完全包含节点区间[l,r]:

if (l>=L&&r<=R)return size;

然后变成矩形之后,子树矩形左下角(l1,r1),右上角(l2,r2)在询问矩形左下角(L1,R1),右上角(L2,R2)中的情况就是:

if (l1>=L1&&r1<=R1&&l2>=L2&&r2<=R2)return size;

广泛性更强地,k维空间的包含即:

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)查询矩形与子树矩形没有交集

就像这样

同理:

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,每个节点代表了空间内一个点,所以在走儿子之前还要先看一下自己这个点是不是在矩形中:

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;
}

然后矩形数点就像这样

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的时候多加一句话:

mx.w=max(range.w,max(son[0]->mx.w,son[1]->mx.w));

然后能够写出基础查询写法:

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这个题,我这么写最高91分,直到我写成这样:

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)单点修改

从根往下依着顺序找就好了,回溯记得更新

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树常数就非常大,所以我们一般进行标记永久化,比如要矩形加,最后查每个数的值

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,然后跑个平面最远点对最后输出堆顶即可