首页 > 代码库 > bzoj2648SJY摆棋子
bzoj2648SJY摆棋子
bzoj2648SJY摆棋子
bzoj2716[Violet 3]天使玩偶
题意:
棋盘上有n个棋子,现在有m个操作,一种是加棋子,一种是查询离某个点最近的棋子。n,m≤500000。
题解:
先将已有的棋子建kd树,然后加棋子就直接向kd树插入节点。因为本题数据弱,所以直接插节点不会T,如果是一些数据比较强的题目,需要在插入一定量节点后重构整棵树。
代码:
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 500010 6 #define INF 0x3fffffff 7 using namespace std; 8 9 inline int read(){10 char ch=getchar(); int f=1,x=0;11 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}12 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();13 return f*x;14 }15 int n,m,f,rt,ans;16 struct p{int pos[2]; bool operator < (const p &a)const{return pos[f]<a.pos[f];}}ps[maxn];17 struct nd{p pos; int mx[2],mn[2],lc,rc;}nds[maxn*2];18 int dis(p a,p b){return abs(a.pos[0]-b.pos[0])+abs(a.pos[1]-b.pos[1]);}19 void update(int x){20 inc(i,0,1){21 if(nds[x].lc)22 nds[x].mx[i]=max(nds[x].mx[i],nds[nds[x].lc].mx[i]),23 nds[x].mn[i]=min(nds[x].mn[i],nds[nds[x].lc].mn[i]);24 if(nds[x].rc)25 nds[x].mx[i]=max(nds[x].mx[i],nds[nds[x].rc].mx[i]),26 nds[x].mn[i]=min(nds[x].mn[i],nds[nds[x].rc].mn[i]);27 }28 }29 int build(int l,int r,int now){30 f=now; int mid=(l+r)>>1; nth_element(ps+l,ps+mid,ps+r+1);31 inc(i,0,1)nds[mid].mx[i]=nds[mid].mn[i]=ps[mid].pos[i]; nds[mid].pos=ps[mid];32 if(l<mid)nds[mid].lc=build(l,mid-1,now^1); if(mid<r)nds[mid].rc=build(mid+1,r,now^1);33 update(mid); return mid;34 }35 void insert(int &x,p a,int now){36 if(!x){x=++n; inc(i,0,1)nds[x].mx[i]=nds[x].mn[i]=a.pos[i]; nds[x].pos=a; return;}37 f=now; if(a<nds[x].pos)insert(nds[x].lc,a,now^1);else insert(nds[x].rc,a,now^1); update(x);38 }39 int get(int x,p a){40 int q=0; inc(i,0,1)q+=max(a.pos[i]-nds[x].mx[i],0),q+=max(nds[x].mn[i]-a.pos[i],0); return q;41 }42 void query(int x,p a){43 ans=min(ans,dis(a,nds[x].pos)); int dl=INF-1,dr=INF-1;44 if(nds[x].lc)dl=get(nds[x].lc,a); if(nds[x].rc)dr=get(nds[x].rc,a);45 if(dl<dr){46 if(ans>dl)query(nds[x].lc,a); if(ans>dr)query(nds[x].rc,a);47 }else{48 if(ans>dr)query(nds[x].rc,a); if(ans>dl)query(nds[x].lc,a);49 }50 }51 int main(){52 n=read(); m=read(); inc(i,1,n)ps[i].pos[0]=read(),ps[i].pos[1]=read(); rt=build(1,n,0);53 inc(i,1,m){54 int t=read(),x=read(),y=read();55 if(t==1)insert(rt,(p){x,y},0);else ans=INF,query(rt,(p){x,y}),printf("%d\n",ans);56 }57 return 0;58 }
20160906
bzoj2648SJY摆棋子
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。