洛谷 P4169 【Violet】天使玩偶/SJY摆棋子 题解

洛谷 P4169 【Violet】天使玩偶/SJY摆棋子 题解

2020-3-22 xiaoh

题意

给定一个二维平面,平面上初始有$n$个点$(1\leq n\leq 3\times10^5)$,接下来有$m$个操作$(1\leq m\leq 3\times10^5)$,每个操作有以下两种可能:

$1.$在平面上加入一个点;

$2.$查询平面上到指定坐标曼哈顿距离最近的点的距离.

题解

这道题有两种做法.第一种显然可以考虑采用$CDQ$分治,但是听说常数大的离谱你要卡半天常在吸氧才能过,所以笔者没有写,第二种则是K-D Tree.也就是笔者所用的做法(其实这道题作为K-D Tree的模板也挺不错的).

首先考虑如何维护K-D Tree:

首先,对于插入操作,我们直接按照划分的位置暴力往下找直到空节点就可以了.

对于查询操作,在每个点上维护横/纵坐标的最小/大值,然后算出可能的最小距离.每查询到一个点时,先用该点更新答案,然后计算出两个儿子的期望最小的距离,然后先遍历期望较小的那个儿子,若期望大于答案则跳过.

对于维护K-D Tree的平衡性,由于K-D Tree的特殊性,我们没有办法用单旋或分裂这些常见的平衡树做法进行处理.我们考虑采用替罪羊的思想来进行维护.在插入后每遍历一个节点,若某个节点的某个儿子的大小超过它自身的一个比例时,就将这棵子树拍扁之后二分重建.这样可以用比较优异的时间复杂度来进行维护.

由于替罪羊树的证明长得及其恶心,所以这个利用替罪羊树的思想的K-D Tree的复杂度会有一点点诡异,正常情况下查询的复杂度是$O(\sqrt n)$的,那么我们不妨设我们进行了$x$次$Rebuild$,每次$Rebuild$的子树的期望大小为$y$,则复杂度为$O(n\log^2 n+n\sqrt n+xy\log^2 y)$,具体$x$和$y$是多少笔者也不知道,反正常数比较紧,笔者各种花式卡常还开了$O2$才把最后两个点过去.

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=300010;
const double alpha=0.75;
const int inf=999999999;
int n,m;
int rt=0;
int tot=0;
struct node{
    int l,r;
    int p[2];
    int sz;
    int minn[2],maxn[2];
}f[MAXN*2];
int tmp[MAXN*2];
inline int max(register int a,register int b)//听说这么写会快一点?
{
	return (a>b)? a:b;
}
inline int min(register int a,register int b)
{
	return (a<b)? a:b;
}
inline int New(register int x,register int y)//新建一个节点并初始化
{
    tot++;
    f[tot].p[0]=f[tot].minn[0]=f[tot].maxn[0]=x;
    f[tot].p[1]=f[tot].minn[1]=f[tot].maxn[1]=y;
    f[tot].sz=1;
    return tot;
}
inline bool cmp1(register int a,register int b)//给数组按横坐标排序
{
    return f[a].p[0]<f[b].p[0];
}
inline bool cmp2(register int a,register int b)//给数组按纵坐标
{
    return f[a].p[1]<f[b].p[1];
}
inline void pushup(register int p)//整合信息
{
    f[p].sz=f[f[p].l].sz+f[f[p].r].sz+1;
	{
		register int i=0;
    	f[p].minn[i]=min(f[p].p[i],min(f[f[p].l].minn[i],f[f[p].r].minn[i]));
    	f[p].maxn[i]=max(f[p].p[i],max(f[f[p].l].maxn[i],f[f[p].r].maxn[i]));
	}
	{
		register int i=1;
    	f[p].minn[i]=min(f[p].p[i],min(f[f[p].l].minn[i],f[f[p].r].minn[i]));
    	f[p].maxn[i]=max(f[p].p[i],max(f[f[p].l].maxn[i],f[f[p].r].maxn[i]));
	}
}
int build(int l,int r,bool x)//建树/重建子树
{
    if(l>=r) return 0;
    int mid=(l+r)>>1;
    x? stable_sort(tmp+l,tmp+r,cmp1):stable_sort(tmp+l,tmp+r,cmp2);
    f[tmp[mid]].l=build(l,mid,!x),f[tmp[mid]].r=build(mid+1,r,!x);
    pushup(tmp[mid]);
    return tmp[mid];
}
void flatten(register int p,int &cnt)//拍扁子树
{
    if(!p) return;
    flatten(f[p].l,cnt);
    tmp[cnt++]=p;
    flatten(f[p].r,cnt);
}
inline void Rebuild(register int &p,register bool x)//重建函数
{
    int cnt=0;
    flatten(p,cnt);
    p=build(0,cnt,x);
}
inline bool canRbu(register int p)//判断是否可重建
{
    return max(f[f[p].l].sz,f[f[p].r].sz)>f[p].sz*alpha;
}
void insert(register int &p,register int x,register int y,bool d)//插入节点
{
    if(!p)
    {
        p=New(x,y);
        return;
    }
    if(d) x<f[p].p[0]? insert(f[p].l,x,y,d^1):insert(f[p].r,x,y,d^1);//听说三目会快一点?
    else y<f[p].p[1]? insert(f[p].l,x,y,d^1):insert(f[p].r,x,y,d^1);
    if(canRbu(p)) Rebuild(p,d);
	pushup(p);//千万别忘了pushup
}
struct node2{//用来存点的结构体
    int p[2];
};
inline int getmin(register int p,node2 x)//求期望最短距离
{
    register int ret=0;
    for(register int i=0;i<2;i++) ret+=max(x.p[i]-f[p].maxn[i],0)+max(f[p].minn[i]-x.p[i],0);
    return ret;
}
inline int dis(register node2 x,register node2 y)//求两点间的距离
{
    return abs(x.p[0]-y.p[0])+abs(x.p[1]-y.p[1]);
}
int ans=inf;
void query(register int p,node2 x)//查询
{
    if(!p) return;
    ans=min(ans,dis((node2){f[p].p[0],f[p].p[1]},x));//更新答案
    int d1=getmin(f[p].l,x);
    int d2=getmin(f[p].r,x);
    if(d1<=d2)//先找期望小的儿子
    {
        if(d1<ans) query(f[p].l,x);
        if(d2<ans) query(f[p].r,x);
    }
    else
    {
        if(d2<ans) query(f[p].r,x);
        if(d1<ans) query(f[p].l,x);
    }
}
int main()
{
    f[0].minn[0]=f[0].minn[1]=inf;
    f[0].maxn[0]=f[0].maxn[1]=0;
    read(n),read(m);
    for(register int i=1;i<=n;i++)
    {
        int x,y;
        read(x),read(y);
        tmp[i-1]=New(x,y);
    }
    rt=build(0,n,1);
    for(register int i=1;i<=m;i++)
    {
        int op,x,y;
        read(op),read(x),read(y);
        if(op==1) insert(rt,x,y,1);
        else
        {
            ans=inf;
            query(rt,{x,y});
            printf("%d\n",ans);
        }
    }
	return 0;
}

后记

写$cmp$函数时一定要注意,sort(a+p,a+q)所传入的需要比较的$x$,$y$本身就是数组元素,而非$a[x]$和$a[y]$,笔者因此自闭了$1h+\dots$