题解 P2794 【Facer和教官】

· · 题解

首先观察公式

cmp(i,j) =| ai - aj + bj - bi | + | ai - aj |

看到两个绝对值，左边一个绝对值加右边一个绝对值，是不是很像曼哈顿距离？

由于动态加点，这时候我们选择强上K-D Tree

普通的平面最近曼哈顿点对的估价函数我们是这样写的

max(minx-x,0)+max(x-maxx,0)+max(miny-y,0)+max(y-maxy,0)

同理，我们也需要对cmp函数进行正确的估价

一开始我是这么想的：

绝对值不等式：

|x|+|y|>=|x-y|

令

x=ai-aj+bj-bi,y=ai-aj

代入得

cmp(i,j)=|ai-aj+bj-bi|+|ai-aj|=|x|+|y|>=|x-y|

即

cmp(i,j)>=|ai-aj+bj-bi-(ai-aj)| cmp(i,j)>=|bj-bi|

然后估价函数可以这么写：

max(minb-b,0)+max(b-maxb,0)

然后提交一波

//50分代码 请勿模仿
#include<cstdio>
#include<algorithm>
using namespace std;
template<class type>inline const void read(type &in)
{
    in=0;char ch=getchar();bool fh=0;
    while (ch<48||ch>57)fh=ch=='-'?1:fh,ch=getchar();
    while (ch>47&&ch<58)in=(in<<3)+(in<<1)+(ch&15),ch=getchar();
    if (fh)in=-in;
}
const int K=2,N=1e5+10,M=1e5+10,INF=2147483647;
int n,m,f;
struct point
{
    int d[K];
    inline const bool operator<(const point &p)const
    {
        return d[f]<p.d[f];
    }
    inline const friend int cmp(const point &a,const point &b)
    {
        return abs(a.d[0]-b.d[0]+b.d[1]-a.d[1])+abs(a.d[0]-b.d[0]);
    }
}w[N+M];
template<int K>class KD_Tree
{
    static const double alpha=0.75;
    private:
        struct tree
        {
            int size;
            tree *son[2];
            point range,mx,mn;
            inline const void pushup()
            {
                size=son[0]->size+1+son[1]->size;
                for (int i=0;i<K;i++)
                    mx.d[i]=max(range.d[i],max(son[0]->mx.d[i],son[1]->mx.d[i])),
                    mn.d[i]=min(range.d[i],min(son[0]->mn.d[i],son[1]->mn.d[i]));
            }
            inline const bool unbalanced()
            {
                return son[0]->size>size*alpha||son[1]->size>size*alpha;
            }
            inline const int evalue(const point &x)
            {
                return max(mn.d[1]-x.d[1],0)+max(x.d[1]-mx.d[1],0);
            }
        }memory_pool[N+M],*recycle[N+M],*null,*tail,*root;
        int top,rnk,mn;
        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->range.d[i]=0,
                null->mx.d[i]=-INF,
                null->mn.d[i]=INF;
            null->size=top=0;
        }
        inline tree *spawn(const point &x)
        {
            tree *p=top?recycle[--top]:tail++;
            p->size=1;
            p->mn=p->mx=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]);
            w[++rnk]=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(w+l,w+mid,w+r+1);
            tree *p=spawn(w[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)
        {
            rnk=0;
            travel(p);
            p=build(1,rnk,0);
        }
        inline tree **add(tree *&p,const point &x,int d)
        {
            if (p==null)return p=spawn(x),&null;
            tree **bad=add(p->son[p->range.d[d]<x.d[d]],x,(d+1)%K);
            p->pushup();
            if (p->unbalanced())bad=&p;
            return bad;
        }
        inline const void query(tree *p,const point &x)
        {
            if (p==null)return;//printf("(%d,%d)\n",p->range.d[0],p->range.d[1]);
            mn=min(mn,cmp(p->range,x));
            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);//printf("%d %d %d\n",mn,f[0],f[1]);
            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);
        }
    public:
        inline KD_Tree(){init();}
        inline const void insert(const point &x)
        {
            tree **bad=add(root,x,0);
            if (*bad!=null)rebuild(*bad);
        }
        inline const int query(const point &x)
        {
            mn=INF;
            query(root,x);
            return mn;
        }
        inline const void build()
        {
            root=build(1,n,0);
        }
};
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(w[i].d[j]);
    kdt.build();
    while (m--)
    {
        int opt;point c;
        read(opt);
        for (int i=0;i<K;i++)read(c.d[i]);
        if (opt==1)kdt.insert(c);
        else printf("%d\n",kdt.query(c));
    }
    return 0;
}

就愉快的tle拿50分了

原因在于：这个估价函数太low了，正确性有保证但是无法获得合理高效的时效

然后我们再看一眼式子

cmp(i,j) =| ai - aj + bj - bi | + | ai - aj | cmp(i,j)=|(bj-ai)-(bi-ai)|+|ai-aj|

我*，这不就是裸的平面最近点对吗

把(b-a)当做第一维，a当做第二维,cmp(i,j)就是点i,j的曼哈顿距离

于是愉快地K-D Tree通过了此题

//100分代码
#include<cstdio>
#include<algorithm>
using std::abs;
using std::max;
using std::min;
using std::nth_element;
template<class type>inline const void read(type &in)
{
    in=0;char ch=getchar();bool f=0;
    while (ch<48||ch>57){if (ch=='-')f=1;ch=getchar();}
    while (ch>47&&ch<58)in=(in<<3)+(in<<1)+(ch&15),ch=getchar();
    if (f)in=-in;
}
const int K=2,N=1e5+10,M=1e5+10,INF=2147483647;
int n,m,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;
    }
}w[N+M];
template<int K>class KD_Tree
{
    static const double alpha=0.75;
    private:
        struct tree
        {
            int size;
            tree *son[2];
            point range,mx,mn;
            inline const void pushup()
            {
                size=son[0]->size+1+son[1]->size;
                for (int i=0;i<K;i++)
                    mx.d[i]=max(range.d[i],max(son[0]->mx.d[i],son[1]->mx.d[i])),
                    mn.d[i]=min(range.d[i],min(son[0]->mn.d[i],son[1]->mn.d[i]));
            }
            inline const bool unbalanced()
            {
                return son[0]->size>size*alpha||son[1]->size>size*alpha;
            }
            inline const int evalue(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;
            }
        }memory_pool[N+M],*recycle[N+M],*null,*tail,*root;
        int top,rnk,flag,mn;
        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 &x)
        {
            tree *p=top?recycle[--top]:tail++;
            p->size=1;
            p->mn=p->mx=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]);
            w[++rnk]=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(w+l,w+mid,w+r+1);
            tree *p=spawn(w[mid]);
            if (l==r)return p;
            p->son[0]=build(l,mid-1,d^1);
            p->son[1]=build(mid+1,r,d^1);
            p->pushup();
            return p;
        }
        inline const void rebuild(tree *&p,int d)
        {
            rnk=0;
            travel(p);
            p=build(1,rnk,d);
        }
        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);
            p->pushup();
            if (p->unbalanced())bad=&p,flag=d;
            return bad;
        }
        inline const void query(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]->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);
        }
    public:
        inline KD_Tree(){init();}
        inline const void insert(int x,int y)
        {
            tree **bad=insert(root,point(y-x,x),flag=0);
            if (*bad==null)return;
            rebuild(*bad,flag);
        }
        inline const int query(int x,int y)
        {
            mn=INF;
            query(root,point(y-x,x));
            return mn;
        }
};
KD_Tree<K>kdt;
int main()
{
    read(n);read(m);
    for (int x,y,i=1;i<=n;i++)read(x),read(y),kdt.insert(x,y);
    for (int opt,x,y;m--;)
        if (read(opt),read(x),read(y),opt==1)kdt.insert(x,y);
        else printf("%d\n",kdt.query(x,y));
    return 0;
}