一、AcWing 254. 天使玩偶 洛谷：P4169
曼哈顿距离最近点：

Ayu在七年前曾经收到过一个天使玩偶，当时她把它当做时间囊埋在了地下。

而七年后的今天，Ayu却忘了她把天使玩偶埋在了哪里，所以她决定仅凭一点模糊的记忆来寻找它。

我们把Ayu生活的小镇看做一个二维平面直角坐标系，而Ayu会不定时的记起可能在某个点(x,y)埋下了天使玩偶。

或者Ayu会询问你，假如她在(x,y)，那么她离最近的天使玩偶可能埋下的地方有多远。

因为Ayu只会沿着平行坐标轴的方向来行动，所以在这个问题里我们定义两个点之间的距离为曼哈顿距离：

dist(A,B)=|Ax−Bx|+|Ay−By|
其中Ax表示点A的横坐标，其余类似。

输入格式
第一行包含两个整数n和m，在刚开始时，Ayu已经知道有n个点可能埋着天使玩偶，接下来Ayu要进行m次操作。

接下来n行，每行两个非负整数xi,yi，表示初始n个点的坐标。

再接下来m行，每行三个非负整数 t,x,y 。

如果t=1，表示Ayu又回忆起了一个可能埋着玩偶的点(x,y)。

如果t=2，表示Ayu询问如果她在坐标(x,y)，那么在已经回忆出的点里，离她最近的那个点有多远。

输出格式
对于每个t=2的询问，在单独的一行内输出该询问的结果。

数据范围
n,m≤5∗105,坐标范围为 0~1e6。

输入样例：
2 3
1 1
2 3
2 1 2
1 3 3
2 4 2
输出样例：
1
2

好吧，洛谷上吸着氧过了，AcWing TLE
据说这玩意随机数据下能达到nlogn。
可是感觉能到 nsqrt（n）的复杂度。
也可能是我选择轴点的姿势不大对。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=1000100;
const double alpha=0.75;
const int inf=0x3f3f3f3f;
struct Point
{
    int x[2];
}po[maxn];
struct node
{
    int p[2];
    int lc,rc;
    int mi[2],ma[2];
    int si;
}t[maxn];

int n,m,root,cnt,sum;
int res[2],ans;
int hui[maxn],top;
int nowd;
int dd,*pp;

bool cmp(const Point &a,const Point &b)
{
    return a.x[nowd]<b.x[nowd];
}

bool balance(int q)
{
    return (double)t[t[q].lc].si<=t[q].si*alpha&&(double)t[t[q].rc].si<=t[q].si*alpha;
}

int newnode(int k)
{
    int p=0;
    if(top) p=hui[top--];
    else p=++cnt;
    t[p].si=t[p].lc=t[p].rc=0;
    t[p].mi[0]=t[p].ma[0]=t[p].p[0]=po[k].x[0];
    t[p].mi[1]=t[p].ma[1]=t[p].p[1]=po[k].x[1];
    return p;
}

void  pushup(int p)
{
    int lc=t[p].lc,rc=t[p].rc;
    for(int i=0;i<2;i++)
    {
        if(lc) t[p].mi[i]=min(t[p].mi[i],t[lc].mi[i]),t[p].ma[i]=max(t[p].ma[i],t[lc].ma[i]);
        if(rc) t[p].mi[i]=min(t[p].mi[i],t[rc].mi[i]),t[p].ma[i]=max(t[p].ma[i],t[rc].ma[i]);
    }
    t[p].si=t[lc].si+t[rc].si+1;
}

int build(int l,int r,int d)
{
    if(l>r) return 0;
    int mid=(l+r)>>1;
    nowd=d;
    nth_element(po+l,po+mid,po+r+1,cmp);
    int p=newnode(mid);
    t[p].lc=build(l,mid-1,d^1);
    t[p].rc=build(mid+1,r,d^1);
    pushup(p);
    return p;
}

void _insert(int &p,int k,int d)
{
    if(!p)
    {
        pp=NULL;
        p=newnode(k);
        return ;
    }
    if(po[k].x[d]<t[p].p[d])
        _insert(t[p].lc,k,d^1);
    else _insert(t[p].rc,k,d^1);
    pushup(p);
    if(!balance(p)) pp=&p,dd=d;
}


void dfs(int p)
{
    if(t[p].lc) dfs(t[p].lc);
    ++sum;
    po[sum].x[0]=t[p].p[0],po[sum].x[1]=t[p].p[1];
    hui[++top]=p;
    if(t[p].rc) dfs(t[p].rc);
}

void rebuild(void)
{
    sum=0;
    dfs(*pp);
    (*pp)=build(1,sum,dd);
}

void _insert(int k)
{
    _insert(root,k,0);
    if(pp!=NULL) rebuild();
}

inline int dis(int p)
{
    return abs(t[p].p[0]-res[0])+abs(t[p].p[1]-res[1]);
}

inline int di(int p)
{
    int ans=0;
    for(int i=0;i<2;i++)
        ans+=max(t[p].mi[i]-res[i],0)+max(res[i]-t[p].ma[i],0);
    return ans;
}

void ask(int p)
{
    if(!p) return ;
    if(dis(p)<dis(ans)) ans=p;
    int dl=inf,dr=inf;
    if(t[p].lc) dl=di(t[p].lc);
    if(t[p].rc) dr=di(t[p].rc);
    if(dl<dr)
    {
        if(dl<dis(ans))
            ask(t[p].lc);
        if(dr<dis(ans))
            ask(t[p].rc);
    }
    else
    {
        if(dr<dis(ans))
            ask(t[p].rc);
        if(dl<dis(ans))
            ask(t[p].lc);
    }
}

int main(void)
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&po[i].x[0],&po[i].x[1]);
    root=build(1,n,0);
    int op;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&op,&res[0],&res[1]);
        if(op==1)
        {
            n++;
            po[n].x[0]=res[0],po[n].x[1]=res[1];
            _insert(n);
        }
        else
        {
            ans=1;
            ask(root);
            printf("%d\n",dis(ans));
        }
    }
    return 0;
}

别的应用以后再补上吧。