BZOJ氪金无极限。。。

其实这两道是同一题。

附上2648的题面：

Description

这天，SJY显得无聊。在家自己玩。

在一个棋盘上，有N个黑色棋子。

他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。

此处的距离是 曼哈顿距离 即(|x1-x2|+|y1-y2|) 。

现在给出N<=500000个初始棋子。和M<=500000个操作。

对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。

同一个格子可能有多个棋子。

Input

第一行两个数 N M

以后M行，每行3个数 t x y

如果t=1 那么放下一个黑色棋子

如果t=2 那么放下一个白色棋子

Output

对于每个T=2 输出一个最小距离

Sample Input

2 3

1 1

2 3

2 1 2

1 3 3

2 4 2

Sample Output

1

2

---

题解Here!

没有插入操作，就无脑$K-D\ Tree$即可。

有了插入操作怎么办呢？

我们可以类比于平衡树，查找要插入的点应该在什么位置。

然后插入就好。

但是很容易就会发现这玩意会形成一条链。

复杂度笋干爆炸。。。

怎么办呢？

$K-D\ Tree$一大缺点就是建好的树不能再动。

暴力重建？

复杂度依然$GG$。。。

等一下！不能每次都暴力重建，那我就偶尔几次暴力重建就是了？

对，这种方法已经被成功运用到替罪羊树中。

设$\alpha=0.75$，当前在$x$处。

假如$x$的左右子树中有一颗子树的大小$>x\text{的子树大小}\times\alpha$，说明该子树已经极其不平衡。

我们需要对其进行暴力拍平重建。

拍平代码的话，大概长这个样子：

void pia(int rt,int num){    if(a[rt].lson)pia(a[rt].lson,num);    point[num+a[a[rt].lson].size+1]=a[rt].point;    recycle[++top]=rt;    if(a[rt].rson)pia(a[rt].rson,num+a[a[rt].lson].size+1);}

重建的话，和最开始的建树过程相同。

这样，插入操作就解决了。

期望复杂度$O(\text{能过})$。

附代码：

#include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 1000010#define MAX (1LL<<30)#define Alpha 0.75using namespace std;int n,m,root,ans,size=0;int top=0,recycle[MAXN];bool sort_flag=false;struct Point{    int x,y;    friend bool operator <(const Point &p,const Point &q){        if(sort_flag)return p.y
          
           '9'){if(c=='-')w=-1;c=getchar();}    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}    return date*w;}inline int get_dis(const Point &p,const Point &q){    return abs(p.x-q.x)+abs(p.y-q.y);}inline int newnode(const Point &p){    int rt;    if(top)rt=recycle[top--];    else rt=++size;    a[rt].point=p;    a[rt].maxx=a[rt].minx=p.x;    a[rt].maxy=a[rt].miny=p.y;    a[rt].lson=a[rt].rson=0;    a[rt].size=1;    return rt;}inline void pushup(int rt){    int lson=a[rt].lson,rson=a[rt].rson;    a[rt].size=a[lson].size+a[rson].size+1;    a[rt].maxx=max(a[rt].maxx,max(a[lson].maxx,a[rson].maxx));    a[rt].maxy=max(a[rt].maxy,max(a[lson].maxy,a[rson].maxy));    a[rt].minx=min(a[rt].minx,min(a[lson].minx,a[rson].minx));    a[rt].miny=min(a[rt].miny,min(a[lson].miny,a[rson].miny));}void buildtree(int l,int r,int &rt,int flag){    int mid=l+r>>1;    sort_flag=flag;    nth_element(point+l,point+mid,point+r+1);    rt=newnode(point[mid]);    if(l