浅谈偏序问题与K-D Tree
zhengrunzhe
2019-10-15 16:47:01
## 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
![](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}$
```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*算法,计算一个点到矩形的最近/远距离
![](https://cdn.luogu.com.cn/upload/image_hosting/1vvlj3sn.png)
如图,需要分类讨论,以矩形的两组对边为平行线组分割成九个区域,看图意会一下,第一行是最小,第二行是最大
综合一下,我们可以设计估价函数
```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,然后跑个平面最远点对最后输出堆顶即可