This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// 領域探索 (kD 木・2 次元バージョン) // Verified: AOJ DSL_2_C: Range Search (kD Tree) struct Node { int loc, l, r; }; struct Point { int id, x, y; }; Node T[500010]; Point P[500010]; int np = 0, NIL = -1; // [l, r) の範囲にある点について構築。その範囲における根を返す int make(int l, int r, int depth=0) { if(l >= r) return NIL; int mid = (l + r) / 2, t = np++; if(depth % 2 == 0) { sort(P+l, P+r, [](const Point &a, const Point &b){return a.x < b.x;}); } else { sort(P+l, P+r, [](const Point &a, const Point &b){return a.y < b.y;}); } T[t].loc = mid; T[t].l = make(l, mid, depth+1); T[t].r = make(mid+1, r, depth+1); return t; } // 左上 (sx, ty)、右下 (tx, sy) の長方形領域にある点を列挙 // v は kD-tree におけるインデックス // find(root, sx, tx, sy, ty, ans) のように使おう void find(int v, int sx, int tx, int sy, int ty, vector<int> &ans, int depth=0) { int x = P[T[v].loc].x, y = P[T[v].loc].y; if(sx <= x && x <= tx && sy <= y && y <= ty) { // ans.push_back(Point{x, y}); ans.push_back(P[T[v].loc].id); } if(depth % 2 == 0) { if(T[v].l != NIL && sx <= x) find(T[v].l, sx, tx, sy, ty, ans, depth+1); if(T[v].r != NIL && x <= tx) find(T[v].r, sx, tx, sy, ty, ans, depth+1); } else { if(T[v].l != NIL && sy <= y) find(T[v].l, sx, tx, sy, ty, ans, depth+1); if(T[v].r != NIL && y <= ty) find(T[v].r, sx, tx, sy, ty, ans, depth+1); } } // kD-tree end
#line 1 "structure/strc_012_kd_tree.cpp" // 領域探索 (kD 木・2 次元バージョン) // Verified: AOJ DSL_2_C: Range Search (kD Tree) struct Node { int loc, l, r; }; struct Point { int id, x, y; }; Node T[500010]; Point P[500010]; int np = 0, NIL = -1; // [l, r) の範囲にある点について構築。その範囲における根を返す int make(int l, int r, int depth=0) { if(l >= r) return NIL; int mid = (l + r) / 2, t = np++; if(depth % 2 == 0) { sort(P+l, P+r, [](const Point &a, const Point &b){return a.x < b.x;}); } else { sort(P+l, P+r, [](const Point &a, const Point &b){return a.y < b.y;}); } T[t].loc = mid; T[t].l = make(l, mid, depth+1); T[t].r = make(mid+1, r, depth+1); return t; } // 左上 (sx, ty)、右下 (tx, sy) の長方形領域にある点を列挙 // v は kD-tree におけるインデックス // find(root, sx, tx, sy, ty, ans) のように使おう void find(int v, int sx, int tx, int sy, int ty, vector<int> &ans, int depth=0) { int x = P[T[v].loc].x, y = P[T[v].loc].y; if(sx <= x && x <= tx && sy <= y && y <= ty) { // ans.push_back(Point{x, y}); ans.push_back(P[T[v].loc].id); } if(depth % 2 == 0) { if(T[v].l != NIL && sx <= x) find(T[v].l, sx, tx, sy, ty, ans, depth+1); if(T[v].r != NIL && x <= tx) find(T[v].r, sx, tx, sy, ty, ans, depth+1); } else { if(T[v].l != NIL && sy <= y) find(T[v].l, sx, tx, sy, ty, ans, depth+1); if(T[v].r != NIL && y <= ty) find(T[v].r, sx, tx, sy, ty, ans, depth+1); } } // kD-tree end