浅谈偏序问题与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 $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.节点信息： ~~变量名爱叫啥叫啥~~ 先定义一个结构体表示空间内一个点 ```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.二维偏序与矩形  这是我们刚刚那棵树，现在我在上面画了每个节点的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]： ```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)查询矩形与子树矩形没有交集 就像这样  同理： ```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}$ ```cpp 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*算法，计算一个点到矩形的最近/远距离  如图，需要分类讨论，以矩形的两组对边为平行线组分割成九个区域，看图意会一下，第一行是最小，第二行是最大 综合一下，我们可以设计估价函数 ```cpp 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; } ``` 然后我们在树上搜索的时候，子树的最小估价不比当前搜过的答案小，那整个子树就没有意义了，剪枝掉。左右儿子哪个估价更小就先走哪边 ```cpp 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); } ``` 类似地，欧氏距离只需要加个平方就好了 ```cpp 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$，设计失衡函数 ```cpp inline const bool unbalanced() { return son[0]->size>size*alpha||son[1]->size>size*alpha; } ``` 每次插入后找到最浅的失衡节点，然后暴力拍扁，也许需要开个垃圾桶回收 ```cpp 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)的矩形了，高维同理 [平面最近点对](https://www.luogu.org/problem/P1429) ```cpp #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摆棋子](https://www.luogu.org/problem/P4169) ```cpp #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 贪婪大陆](https://www.luogu.org/problem/P2184) [题解](https://www.luogu.org/blog/van/solution-p2184) [TATT](https://www.luogu.org/problem/P3769) 排序降维，将第一维从小到大排序，容易写出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即可 ```cpp #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远点对](https://www.luogu.org/problem/P4357) 用个大根堆存答案，一开始塞2k个0，然后跑个平面最远点对最后输出堆顶即可