BZOJ2648SJY摆棋子

题目传送门

分析：

就一KD树板题。。。

这里其实可以先建树在直接暴力加点，然后查询就好了。。。

但是这样的做法BZOJ能过，洛谷上会T（应该是第11号点是后来加的hack数据（难受））

所以考虑离线，然后在每个黑子上打是否已添加的标记。。。

很有道理2333

但是BZOJ上T了，洛谷上过了

呵呵呵。。。呵呵呵呵。。。。哈哈哈哈

然后就有神仙说沿用一下替罪羊树的思想，过于畸形的子树直接拍扁重构

那这样左旋右旋也可以呗。。。。

然后还有神仙会CDQ分治，貌似也挺有道理的。。。

我前两种都写了一下。。。其实差不多吧，都很好写。。。

#include
#include
#include
#include
#include
#include
#define maxn 1000005
#define INF 0x3f3f3f3f
using namespace std;
inline int getint()
{
int num=0,flag=1;char c;
while((c=getchar())<&＃39;0&＃39;||c>&＃39;9&＃39;)if(c==&＃39;-&＃39;)flag=-1;
while(c>=&＃39;0&＃39;&&c<=&＃39;9&＃39;)num=num*10+c-48,c=getchar();
return num*flag;
}
int n,m,rt;
struct node{
int x[2];
}P[maxn];
struct pt{
node p;
int lc,rc;
int mx[2],mn[2];
}a[maxn];
int ans,cur;
inline bool cmp0(node x,node y){return x.x[0]inline bool cmp1(node x,node y){return x.x[1]inline void pushup(int x,int y)
{
a[x].mx[0]=max(a[x].mx[0],a[y].mx[0]);
a[x].mx[1]=max(a[x].mx[1],a[y].mx[1]);
a[x].mn[0]=min(a[x].mn[0],a[y].mn[0]);
a[x].mn[1]=min(a[x].mn[1],a[y].mn[1]);
}
inline void build(int &now,int l,int r,int k)
{
int mid=now=(l+r)>>1;
if(k)nth_element(P+l+1,P+mid+1,P+r+1,cmp1);
else nth_element(P+l+1,P+mid+1,P+r+1,cmp0);
a[now].p=P[mid];
a[now].mn[0]=a[now].mx[0]=P[mid].x[0];
a[now].mn[1]=a[now].mx[1]=P[mid].x[1];
if(l if(r>now)build(a[now].rc,mid+1,r,k^1),pushup(now,a[now].rc);
}
inline int getdis(node x,node y)
{return abs(x.x[0]-y.x[0])+abs(x.x[1]-y.x[1]);}
inline int msr(int now,node p)
{
if(!now)return INF;
int tmp1=(a[now].mn[0]<=p.x[0]&&a[now].mx[0]>=p.x[0])?0:min(abs(p.x[0]-a[now].mn[0]),abs(p.x[0]-a[now].mx[0]));
int tmp2=(a[now].mn[1]<=p.x[1]&&a[now].mx[1]>=p.x[1])?0:min(abs(p.x[1]-a[now].mn[1]),abs(p.x[1]-a[now].mx[1]));
return tmp1+tmp2;
}
inline void insert(int &now,node p,int k)
{
if(!now)
{
now=++cur,a[now].p=p;
a[now].mn[0]=a[now].mx[0]=p.x[0];
a[now].mn[1]=a[now].mx[1]=p.x[1];
return;
}
if(p.x[k]<=a[now].p.x[k])insert(a[now].lc,p,k^1),pushup(now,a[now].lc);
else insert(a[now].rc,p,k^1),pushup(now,a[now].rc);
}
inline void query(int rt,node p)
{
int tmp=getdis(p,a[rt].p);
if(tmp int tmp1=msr(a[rt].lc,p),tmp2=msr(a[rt].rc,p);
if(tmp1 {
if(a[rt].lc&&tmp1 if(a[rt].rc&&tmp2 }
else
{
if(a[rt].rc&&tmp2 if(a[rt].lc&&tmp1 }
}
int main()
{
n=cur=getint(),m=getint();
for(int i=1;i<=n;i++)
P[i].x[0]=getint(),P[i].x[1]=getint();
build(rt,1,n,0);
for(int i=1;i<=m;i++)
{
int op=getint();
node tmp;tmp.x[0]=getint(),tmp.x[1]=getint();
if(op==1)insert(rt,tmp,0);
else ans=INF,query(rt,tmp),printf("%d\n",ans);
}
}