BZOJ 2648: SJY摆棋子(K-D Tree)
2018-06-27 10:06:35来源:未知 阅读 ()
Submit: 6051 Solved: 2113
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
1 1
2 3
2 1 2
1 3 3
2 4 2
Sample Output
1
2
HINT
kdtree可以过
Source
K-D Tree裸题
洛谷上需要拍扁重构才能过
丧心病狂
#include<cstdio> #include<algorithm> #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 17, stdin), p1 == p2) ? EOF : *p1++) using namespace std; const int MAXN = 6 * 1e5 + 10, INF = 1e9 + 10; const double delat = 0.60; char buf[1 << 17], *p1 = buf, *p2 = buf; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, M, WD, root, Ans; inline int abs(int x) { return x < 0 ? -x : x; } #define ls(x) T[x].ls #define rs(x) T[x].rs struct Point { int x[2]; bool operator < (const Point rhs) const { return x[WD] < rhs.x[WD]; } }p[MAXN]; struct Node { int ls, rs, siz, mi[2], mx[2]; Point tp; }T[MAXN]; int rub[MAXN], top, cur; int NewNode() { return top ? rub[top--] : ++cur;//tag } void update(int k) { T[k].siz = T[ls(k)].siz + T[rs(k)].siz + 1; for(int i = 0; i <= 1; i++) { T[k].mi[i] = T[k].mx[i] = T[k].tp.x[i]; if(ls(k)) T[k].mi[i] = min(T[k].mi[i], T[ls(k)].mi[i]), T[k].mx[i] = max(T[k].mx[i], T[ls(k)].mx[i]); if(rs(k)) T[k].mi[i] = min(T[k].mi[i], T[rs(k)].mi[i]), T[k].mx[i] = max(T[k].mx[i], T[rs(k)].mx[i]); } } int Build(int l, int r, int wd) { if(l > r) return 0; int k = NewNode(), mid = l + r >> 1; WD = wd, nth_element(p + l, p + mid, p + r + 1); T[k].tp = p[mid]; T[k].ls = Build(l, mid - 1, wd ^ 1); T[k].rs = Build(mid + 1, r, wd ^ 1); update(k); return k; } inline void Apart(int k, int num) { if(T[k].ls) Apart(ls(k), num); p[num + T[ls(k)].siz + 1] = T[k].tp, rub[++top] = k; if(T[k].rs) Apart(rs(k), num + T[ls(k)].siz + 1); } inline int check(int &k, int wd) { if(T[k].siz * delat < T[ls(k)].siz || T[k].siz * delat < T[rs(k)].siz) Apart(k, 0), k = Build(1, T[k].siz, wd); } void Insert(Point a, int &k, int wd) { if(k == 0) { k = NewNode(); T[k].tp = a; update(k); return ; } if(a.x[wd] < T[k].tp.x[wd]) Insert(a, ls(k), wd ^ 1); else Insert(a, rs(k), wd ^ 1); update(k); check(k, wd); } inline int dis(Point a, Point b) { return abs(a.x[0] - b.x[0]) + abs(a.x[1] - b.x[1]); } inline int Manha(Point a, int b) { int rt = 0; for(int i = 0; i <= 1; i++) rt += max(0, a.x[i] - T[b].mx[i]) + max(0, T[b].mi[i] - a.x[i]); return rt; } int Query(Point a, int k) { Ans = min(Ans, dis(T[k].tp, a)); int disl = INF, disr = INF; if(ls(k)) disl = Manha(a, T[k].ls); if(rs(k)) disr = Manha(a, T[k].rs); if(disl < disr) { if(disl < Ans) Query(a, ls(k)); if(disr < Ans) Query(a, rs(k)); } else { if(disr < Ans) Query(a, rs(k)); if(disl < Ans) Query(a, ls(k)); } } int main() { #ifdef WIN32 freopen("a.in", "r", stdin); #endif N = read(); M = read(); for(int i = 1; i <= N; i++) p[i].x[0] = read(), p[i].x[1] = read(); root = Build(1, N, 0); while(M--) { int opt = read(), x = read(), y = read(); if(opt == 1) Insert((Point){x, y}, root, 0); else Ans = INF + 1, Query((Point){x, y}, root), printf("%d\n", Ans); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:OJ:又一道考察多态的题目
- bzoj3569 DZY Loves Chinese II 2020-05-25
- bzoj4036 [HAOI2015]按位或 2020-04-26
- 「BZOJ4173」数学 2020-01-15
- bzoj3944 Sum 2019-12-25
- BZOJ1008: [HNOI2008]越狱(快速幂) 2019-08-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash