Description

這天，SJY顯得無聊。在家自己玩。在一個棋盤上，有N個黑色棋子。他每次要么放到棋盤上一個黑色棋子，要么放上一個白色棋子，如果是白色棋子，他會找出距離這個白色棋子最近的黑色棋子。此處的距離是 曼哈頓距離 即(|x1-x2|+|y1-y2|) 。現(xiàn)在給出N<=500000個初始棋子。和M<=500000個操作。對于每個白色棋子，輸出距離這個白色棋子最近的黑色棋子的距離。同一個格子可能有多個棋子。

Input

第一行兩個數(shù) N M 以后M行，每行3個數(shù) 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可以過

?

這個HINT太神仙了。。。

yy一下KD-tree插入操作，順著訪問一遍有孩子是空的就插進(jìn)去

這樣做不是會把樹的結(jié)構(gòu)都給破壞掉嗎？？那就得暴力重構(gòu)

沒重構(gòu)也擦邊卡過美滋滋

//MT_LI
#include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; struct KDT{int lc,rc,d[2],mn[2],mx[2]; }tr[1100000]; void update(int x) {int lc=tr[x].lc,rc=tr[x].rc;if(lc){tr[x].mn[0]=min(tr[x].mn[0],tr[lc].mn[0]);tr[x].mn[1]=min(tr[x].mn[1],tr[lc].mn[1]);tr[x].mx[0]=max(tr[x].mx[0],tr[lc].mx[0]);tr[x].mx[1]=max(tr[x].mx[1],tr[lc].mx[1]);}if(rc){tr[x].mn[0]=min(tr[x].mn[0],tr[rc].mn[0]);tr[x].mn[1]=min(tr[x].mn[1],tr[rc].mn[1]);tr[x].mx[0]=max(tr[x].mx[0],tr[rc].mx[0]);tr[x].mx[1]=max(tr[x].mx[1],tr[rc].mx[1]);} } int cmpd; bool cmp(KDT a,KDT b){return a.d[cmpd]<b.d[cmpd] || a.d[cmpd]==b.d[cmpd]&&a.d[cmpd^1]<b.d[cmpd^1];} int bt(int l,int r,int d) {int mid=(l+r)/2,now;now=mid;cmpd=d;nth_element(tr+l,tr+mid,tr+r+1,cmp);tr[now].mx[0]=tr[now].mn[0]=tr[now].d[0];tr[now].mx[1]=tr[now].mn[1]=tr[now].d[1];if(l<mid)tr[now].lc=bt(l,mid-1,d^1);if(mid<r)tr[now].rc=bt(mid+1,r,d^1);update(now);return now; } int n,root; int nowx,nowy; int minn; int dismin(int now,int x,int y) {int d=0;if(x<tr[now].mn[0])d+=tr[now].mn[0]-x;if(x>tr[now].mx[0])d+=x-tr[now].mx[0];if(y<tr[now].mn[1])d+=tr[now].mn[1]-y;if(y>tr[now].mx[1])d+=y-tr[now].mx[1];return d; } void findmin(int now) {int dl=1<<30,dr=1<<30;int d=abs(tr[now].d[0]-nowx)+abs(tr[now].d[1]-nowy);minn=min(minn,d);if(tr[now].lc)dl=dismin(tr[now].lc,nowx,nowy);if(tr[now].rc)dr=dismin(tr[now].rc,nowx,nowy);if(dl<dr){if(dl<minn)findmin(tr[now].lc);if(dr<minn)findmin(tr[now].rc);}else{if(dr<minn)findmin(tr[now].rc);if(dl<minn)findmin(tr[now].lc);} } void ins(int now) {int p=root;while(1){if(tr[p].mx[0]<tr[now].mx[0])tr[p].mx[0]=tr[now].mx[0];if(tr[p].mx[1]<tr[now].mx[1])tr[p].mx[1]=tr[now].mx[1];if(tr[p].mn[0]>tr[now].mn[0])tr[p].mn[0]=tr[now].mn[0];if(tr[p].mn[1]>tr[now].mn[1])tr[p].mn[1]=tr[now].mn[1];if(tr[now].d[cmpd]<tr[p].d[cmpd]){if(tr[p].lc==0){tr[p].lc=now;return ;}else p=tr[p].lc;}else{if(tr[p].rc==0){tr[p].rc=now;return ;}else p=tr[p].rc;}cmpd^=1;} } int m; int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d%d",&tr[i].d[0],&tr[i].d[1]);root=bt(1,n,0);for(int i=1;i<=m;i++){int op;scanf("%d",&op);if(op==2){scanf("%d%d",&nowx,&nowy);minn=1<<30;findmin(root);printf("%d\n",minn);}else{n++;scanf("%d%d",&tr[n].d[0],&tr[n].d[1]);tr[n].mx[0]=tr[n].mn[0]=tr[n].d[0];tr[n].mx[1]=tr[n].mn[1]=tr[n].d[1];cmpd=0;ins(n);}}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/MT-LI/p/9761173.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ2648: SJY摆棋子的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。