注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2648/2716]SJY摆棋子  

2015-04-23 21:48:58|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2648: SJY摆棋子

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 999  Solved: 319
[Submit][Status][Discuss]

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

HINT

kdtree可以过

Source

Solution

kdtree第一题 
kdtree中每个点维护一个域,就是它子树内的xy范围,构成一个矩形。构造的时候跟splay差不多。
插入貌似可以不用重量平衡,直接插就行了虽然会被卡233。
询问的时候估一个下界,因为是曼哈顿最近,距离即为该点到平面域的最短距离,在域内为0。
然后暴力查找就行了233

Code

/**************************************************************
    Problem: 2648
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:7632 ms
    Memory:37704 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
int n,m,op,x,y,i,dd,rt,ans;
struct T{int d[2],s[2],x[2],y[2];}t[1<<20];
struct P{int d[2];}a[1<<19];
bool operator<(const P&a,const P&b){return a.d[dd]<b.d[dd]||a.d[dd]==b.d[dd]&&a.d[dd^1]<b.d[dd^1];}
char B[1<<15],*S=B,*T=B,ch;int aa,bb;
#define isd(c) (c>='0'&&c<='9')
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int F(){
    while(ch=getc(),!isd(ch)&&ch!='-');ch=='-'?aa=bb=0:(aa=ch-'0',bb=1);
    while(ch=getc(),isd(ch))aa=aa*10+ch-'0';return bb?aa:-aa;
}
#define abs(x) (x>0?x:-(x))
#define max(a,b) (a>b?a:b)
#define cmax(a,b) (a<b?a=b:a)
#define cmin(a,b) (a>b?a=b:a)
#define ls t[now].s[0]
#define rs t[now].s[1]
void mt(int f,int x){
    cmin(t[f].x[0],t[x].x[0]),cmax(t[f].x[1],t[x].x[1]);
    cmin(t[f].y[0],t[x].y[0]),cmax(t[f].y[1],t[x].y[1]);
}
int bt(int l,int r,int d){
    dd=d;int now=l+r>>1;
    std::nth_element(a+l,a+now,a+r+1);
    t[now].d[0]=t[now].x[0]=t[now].x[1]=a[now].d[0];
    t[now].d[1]=t[now].y[0]=t[now].y[1]=a[now].d[1];
    if(l<now)ls=bt(l,now-1,d^1),mt(now,ls);
    if(now<r)rs=bt(now+1,r,d^1),mt(now,rs);
    return now;
}
int gd(int p){
    return max(t[p].x[0]-x,0)+max(x-t[p].x[1],0)+max(t[p].y[0]-y,0)+max(y-t[p].y[1],0);
}
void ins(int n){
    for(int p=rt,dd=0;p;dd^=1){
        mt(p,n);int&nx=t[p].s[t[n].d[dd]>=t[p].d[dd]];
        if(nx==0){nx=n;return;}else p=nx;
    }
}
void query(int now){
    int d[2]={1<<30,1<<30},d0=abs(t[now].d[0]-x)+abs(t[now].d[1]-y),p;
    if(ls)d[0]=gd(ls);if(rs)d[1]=gd(rs);p=d[0]>=d[1];cmin(ans,d0);
    if(d[p]<ans)query(t[now].s[p]);
    if(d[p^1]<ans)query(t[now].s[p^1]);
}
int main(){
    for(n=F(),m=F(),i=1;i<=n;i++)a[i]=(P){F(),F()};
    for(rt=bt(1,n,0);m--;){
        op=F(),x=F(),y=F();
        if(op==1){++n;
            t[n].d[0]=t[n].x[0]=t[n].x[1]=x;
            t[n].d[1]=t[n].y[0]=t[n].y[1]=y;
            ins(n);
        }
        else{
            ans=1<<30;query(rt);printf("%d\n",ans);
        }
    }
}
  评论这张
 
阅读(52)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018