「K-D Tree 膜板」「BZOJ2648」SJY摆棋子
这天，sjy显得无聊。在家自己玩。在一个棋盘上，有 n 个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是 曼哈顿距离 即 |x1−x2|+|y1−y2| 。现在给出 n≤500000 个初始棋子。和 m≤500000个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。
input第一行两个数 n,m
以后 m 行，每行3个数 txy
如果 t=1 那么放下一个黑色棋子
如果 t=2 那么放下一个白色棋子
output对于每个 t=2 输出一个最小距离
sample input2 31 12 32 1 21 3 32 4 2sample output
12hintkdtree 可以过
题解k-d tree 膜板题
这里用的是替罪羊式加点，效率更高。
my code/************************************************************** problem: 2648 user: infinityedge language: c++ result: accepted time:17728 ms memory:48180 kb****************************************************************/#include #include #include #include #include #include #define inf 0x3f3f3f3f#define eps 1e-10using namespace std;typedef long long ll;const ll mod = 1e9 + 7;int abs(int x){ return x > 0 ? x : -x;}struct point{ int x, y; point(){} point(int _x, int _y){ x = _x; y = _y; }}a[500005];int cmpx(point a, point b){ return a.x < b.x;}int cmpy(point a, point b){ return a.y < b.y;}struct node{ int x, y, siz, dt; int dx, dy, ux, uy; int lc, rc, fa;};struct kdtree{ node d[1000005]; int sz, rt, lst, tot; queue q; int newnode(){ if(!q.empty()){ int ret = q.front(); q.pop(); return lst = ret; } return lst = ++sz; } void pushup(int k){ d[k].dx = d[k].ux = d[k].x; d[k].dy = d[k].uy = d[k].y; d[k].siz = 1; if(d[k].lc){ d[k].dx = min(d[k].dx, d[d[k].lc].dx); d[k].dy = min(d[k].dy, d[d[k].lc].dy); d[k].ux = max(d[k].ux, d[d[k].lc].ux); d[k].uy = max(d[k].uy, d[d[k].lc].uy); d[k].siz += d[d[k].lc].siz; } if(d[k].rc){ d[k].dx = min(d[k].dx, d[d[k].rc].dx); d[k].dy = min(d[k].dy, d[d[k].rc].dy); d[k].ux = max(d[k].ux, d[d[k].rc].ux); d[k].uy = max(d[k].uy, d[d[k].rc].uy); d[k].siz += d[d[k].lc].siz; } } void build(int &k, int l, int r, int flag, int fa){ if(l > r) return; k = newnode(); d[k].fa = fa; d[k].dt = flag; // printf(%d %d %d\n, k, l, r); if(l == r){ d[k].x = d[k].dx = d[k].ux = a[l].x; d[k].y = d[k].dy = d[k].uy = a[l].y; return; } int mid = (l + r) >> 1; if(flag) nth_element(a + l, a + mid, a + r, cmpx); else nth_element(a + l, a + mid, a + r, cmpy); d[k].x = a[mid].x; d[k].y = a[mid].y; build(d[k].lc, l, mid - 1, flag ^ 1, k); build(d[k].rc, mid + 1, r, flag ^ 1, k); pushup(k); } int judge(int k){ if((d[d[k].lc].siz + 1) * 0.8 > d[k].siz + 1) return 1; if((d[d[k].lc].siz + 1) * 0.8 > d[k].siz + 1) return 1; return 0; } void dfs(int k){ q.push(k); a[++tot] = point(d[k].x, d[k].y); if(d[k].lc) dfs(d[k].lc); if(d[k].rc) dfs(d[k].rc); } void rebuild(int k){ tot = 0; if(k == rt){ dfs(k); build(rt, 1, tot, 0, 0); return; } int f = d[k].fa, wh = (d[f].rc == k); dfs(k); if(wh) build(d[f].rc, 1, tot, 0, d[f].dt ^ 1); else build(d[f].lc, 1, tot, 0, d[f].dt ^ 1); } void ins(int k, int x, int y, int flag){ if(flag){ if(x <= d[k].x){ if(d[k].lc == 0){ a[1] = point(x, y); build(d[k].lc, 1, 1, flag ^ 1, k); }else ins(d[k].lc, x, y, flag ^ 1); }else{ if(d[k].rc == 0){ a[1] = point(x, y); build(d[k].rc, 1, 1, flag ^ 1, k); }else ins(d[k].rc, x, y, flag ^ 1); } }else{ if(y <= d[k].y){ if(d[k].lc == 0){ a[1] = point(x, y); build(d[k].lc, 1, 1, flag ^ 1, k); }else ins(d[k].lc, x, y, flag ^ 1); }else{ if(d[k].rc == 0){ a[1] = point(x, y); build(d[k].rc, 1, 1, flag ^ 1, k); }else ins(d[k].rc, x, y, flag ^ 1); } } pushup(k); } void ins(int x, int y){ ins(rt, x, y, 0); x = lst; int tmp = 0; while(x != 0){ if(judge(x)) tmp = x; x = d[x].fa; } if(tmp != 0){ rebuild(x); } } int ans; int get(int k, int x, int y){ int ret = 0; ret += max(0, d[k].dx - x); ret += max(0, d[k].dy - y); ret += max(0, x - d[k].ux); ret += max(0, y - d[k].uy); return ret; } void query(int k, int x, int y){ // printf(%d %d %d\n, rt, d[k].x, d[k].y); ans = min(ans, abs(d[k].x - x) + abs(d[k].y - y)); int dl = inf, dr = inf; if(d[k].lc) dl = get(d[k].lc, x, y); if(d[k].rc) dr = get(d[k].rc, x, y); if(dl < dr){ if(dl < ans) query(d[k].lc, x, y); if(dr < ans) query(d[k].rc, x, y); }else{ if(dr < ans) query(d[k].rc, x, y); if(dl < ans) query(d[k].lc, x, y); } } int query(int x, int y){ ans = inf; query(rt, x, y); return ans; }}kdt;int n, m;int main(){ //freopen(test.in, r, stdin); //freopen(test.out, w, stdout); scanf(%d%d, &n, &m); for(int i = 1; i <= n; i ++){ int x, y; scanf(%d%d, &x, &y); a[i] = point(x, y); } kdt.build(kdt.rt, 1, n, 0, 0); for(int i = 1; i <= m; i ++){ int opt, x, y; scanf(%d%d%d, &opt, &x, &y); if(opt == 1){ kdt.ins(x, y); }else{ printf(%d\n, kdt.query(x, y)); } } return 0;}
浅谈电动单座调节阀的保养
上海科学院激光探测技术研究中心研发的激光雷达进入多家企业
智慧灯杆的信息管理平台架构及应用介绍
刘庆峰:让民众有对大数据和人工智能的获得感
高温熔体压力传感器
「K-D Tree 膜板」「BZOJ2648」SJY摆棋子
智能家居系统的组成
Snapchat宣布与个性化表情符号背后的Bitmoji建立合作关系
5G的发展将对物联网领域产生革命性的影响
微软安卓版 OneDrive 更新：支持三星 Motion Photos 与 8K 视频回放
未来智慧城市将有多智能，主要集中体现在那几个方面
提高人工智能道德水平的9个步骤
功率放大器的工作原理是什么
波音737MAX飞机正在接受审查将不可能在11月前进行测试飞行
如果你的周围没有5G信号，你会满城市找5G信号吗？
三星欲推出Mini LED背光电视，或将由大陆和台湾LED厂商生产
物联网的以后会是怎样的
低烟无卤阻燃控制电缆型号_低烟无卤阻燃控制电缆规格表
W波段机场异物检测FOD雷达毫米波前端解决方案
降低时序报告中逻辑延迟的方法
input第一行两个数 n,m
以后 m 行，每行3个数 txy
如果 t=1 那么放下一个黑色棋子
如果 t=2 那么放下一个白色棋子
output对于每个 t=2 输出一个最小距离
sample input2 31 12 32 1 21 3 32 4 2sample output
12hintkdtree 可以过
题解k-d tree 膜板题
这里用的是替罪羊式加点，效率更高。
my code/************************************************************** problem: 2648 user: infinityedge language: c++ result: accepted time:17728 ms memory:48180 kb****************************************************************/#include #include #include #include #include #include #define inf 0x3f3f3f3f#define eps 1e-10using namespace std;typedef long long ll;const ll mod = 1e9 + 7;int abs(int x){ return x > 0 ? x : -x;}struct point{ int x, y; point(){} point(int _x, int _y){ x = _x; y = _y; }}a[500005];int cmpx(point a, point b){ return a.x < b.x;}int cmpy(point a, point b){ return a.y < b.y;}struct node{ int x, y, siz, dt; int dx, dy, ux, uy; int lc, rc, fa;};struct kdtree{ node d[1000005]; int sz, rt, lst, tot; queue q; int newnode(){ if(!q.empty()){ int ret = q.front(); q.pop(); return lst = ret; } return lst = ++sz; } void pushup(int k){ d[k].dx = d[k].ux = d[k].x; d[k].dy = d[k].uy = d[k].y; d[k].siz = 1; if(d[k].lc){ d[k].dx = min(d[k].dx, d[d[k].lc].dx); d[k].dy = min(d[k].dy, d[d[k].lc].dy); d[k].ux = max(d[k].ux, d[d[k].lc].ux); d[k].uy = max(d[k].uy, d[d[k].lc].uy); d[k].siz += d[d[k].lc].siz; } if(d[k].rc){ d[k].dx = min(d[k].dx, d[d[k].rc].dx); d[k].dy = min(d[k].dy, d[d[k].rc].dy); d[k].ux = max(d[k].ux, d[d[k].rc].ux); d[k].uy = max(d[k].uy, d[d[k].rc].uy); d[k].siz += d[d[k].lc].siz; } } void build(int &k, int l, int r, int flag, int fa){ if(l > r) return; k = newnode(); d[k].fa = fa; d[k].dt = flag; // printf(%d %d %d\n, k, l, r); if(l == r){ d[k].x = d[k].dx = d[k].ux = a[l].x; d[k].y = d[k].dy = d[k].uy = a[l].y; return; } int mid = (l + r) >> 1; if(flag) nth_element(a + l, a + mid, a + r, cmpx); else nth_element(a + l, a + mid, a + r, cmpy); d[k].x = a[mid].x; d[k].y = a[mid].y; build(d[k].lc, l, mid - 1, flag ^ 1, k); build(d[k].rc, mid + 1, r, flag ^ 1, k); pushup(k); } int judge(int k){ if((d[d[k].lc].siz + 1) * 0.8 > d[k].siz + 1) return 1; if((d[d[k].lc].siz + 1) * 0.8 > d[k].siz + 1) return 1; return 0; } void dfs(int k){ q.push(k); a[++tot] = point(d[k].x, d[k].y); if(d[k].lc) dfs(d[k].lc); if(d[k].rc) dfs(d[k].rc); } void rebuild(int k){ tot = 0; if(k == rt){ dfs(k); build(rt, 1, tot, 0, 0); return; } int f = d[k].fa, wh = (d[f].rc == k); dfs(k); if(wh) build(d[f].rc, 1, tot, 0, d[f].dt ^ 1); else build(d[f].lc, 1, tot, 0, d[f].dt ^ 1); } void ins(int k, int x, int y, int flag){ if(flag){ if(x <= d[k].x){ if(d[k].lc == 0){ a[1] = point(x, y); build(d[k].lc, 1, 1, flag ^ 1, k); }else ins(d[k].lc, x, y, flag ^ 1); }else{ if(d[k].rc == 0){ a[1] = point(x, y); build(d[k].rc, 1, 1, flag ^ 1, k); }else ins(d[k].rc, x, y, flag ^ 1); } }else{ if(y <= d[k].y){ if(d[k].lc == 0){ a[1] = point(x, y); build(d[k].lc, 1, 1, flag ^ 1, k); }else ins(d[k].lc, x, y, flag ^ 1); }else{ if(d[k].rc == 0){ a[1] = point(x, y); build(d[k].rc, 1, 1, flag ^ 1, k); }else ins(d[k].rc, x, y, flag ^ 1); } } pushup(k); } void ins(int x, int y){ ins(rt, x, y, 0); x = lst; int tmp = 0; while(x != 0){ if(judge(x)) tmp = x; x = d[x].fa; } if(tmp != 0){ rebuild(x); } } int ans; int get(int k, int x, int y){ int ret = 0; ret += max(0, d[k].dx - x); ret += max(0, d[k].dy - y); ret += max(0, x - d[k].ux); ret += max(0, y - d[k].uy); return ret; } void query(int k, int x, int y){ // printf(%d %d %d\n, rt, d[k].x, d[k].y); ans = min(ans, abs(d[k].x - x) + abs(d[k].y - y)); int dl = inf, dr = inf; if(d[k].lc) dl = get(d[k].lc, x, y); if(d[k].rc) dr = get(d[k].rc, x, y); if(dl < dr){ if(dl < ans) query(d[k].lc, x, y); if(dr < ans) query(d[k].rc, x, y); }else{ if(dr < ans) query(d[k].rc, x, y); if(dl < ans) query(d[k].lc, x, y); } } int query(int x, int y){ ans = inf; query(rt, x, y); return ans; }}kdt;int n, m;int main(){ //freopen(test.in, r, stdin); //freopen(test.out, w, stdout); scanf(%d%d, &n, &m); for(int i = 1; i <= n; i ++){ int x, y; scanf(%d%d, &x, &y); a[i] = point(x, y); } kdt.build(kdt.rt, 1, n, 0, 0); for(int i = 1; i <= m; i ++){ int opt, x, y; scanf(%d%d%d, &opt, &x, &y); if(opt == 1){ kdt.ins(x, y); }else{ printf(%d\n, kdt.query(x, y)); } } return 0;}
浅谈电动单座调节阀的保养
上海科学院激光探测技术研究中心研发的激光雷达进入多家企业
智慧灯杆的信息管理平台架构及应用介绍
刘庆峰:让民众有对大数据和人工智能的获得感
高温熔体压力传感器
「K-D Tree 膜板」「BZOJ2648」SJY摆棋子
智能家居系统的组成
Snapchat宣布与个性化表情符号背后的Bitmoji建立合作关系
5G的发展将对物联网领域产生革命性的影响
微软安卓版 OneDrive 更新：支持三星 Motion Photos 与 8K 视频回放
未来智慧城市将有多智能，主要集中体现在那几个方面
提高人工智能道德水平的9个步骤
功率放大器的工作原理是什么
波音737MAX飞机正在接受审查将不可能在11月前进行测试飞行
如果你的周围没有5G信号，你会满城市找5G信号吗？
三星欲推出Mini LED背光电视，或将由大陆和台湾LED厂商生产
物联网的以后会是怎样的
低烟无卤阻燃控制电缆型号_低烟无卤阻燃控制电缆规格表
W波段机场异物检测FOD雷达毫米波前端解决方案
降低时序报告中逻辑延迟的方法