2020-2021:teams:legal_string:jxm2001:kd_tree
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:kd_tree [2020/06/24 16:50] jxm2001 |
2020-2021:teams:legal_string:jxm2001:kd_tree [2020/07/28 17:21] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 7: | 行 7: | ||
| 空间复杂度 $O(n)$，单次插入时间复杂度 $O(\log n)$，查询时间复杂度 $O\left(k\sqrt[1-\frac 1k]n\right)$，其中 $k$ 表示空间维数。 | 空间复杂度 $O(n)$，单次插入时间复杂度 $O(\log n)$，查询时间复杂度 $O\left(k\sqrt[1-\frac 1k]n\right)$，其中 $k$ 表示空间维数。 | ||
| - | ===== 算法实现 ==== | + | ===== 算法实现 ===== |
| 为方便理解，这里仅讲解 2D_Tree，高维 KD_Tree 可以类推。实际上高维 KD_Tree 时间复杂度难以承受，算法竞赛中通常只涉及 2D_Tree。 | 为方便理解，这里仅讲解 2D_Tree，高维 KD_Tree 可以类推。实际上高维 KD_Tree 时间复杂度难以承受，算法竞赛中通常只涉及 2D_Tree。 | ||
| 行 59: | 行 59: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <cstdio> | ||
| - | #include <algorithm> | ||
| - | #include <cstring> | ||
| - | #include <cctype> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline void write(LL x){ | ||
| - | register char c[21],len=0; | ||
| - | if(!x)return putchar('0'),void(); | ||
| - | if(x<0)x=-x,putchar('-'); | ||
| - | while(x)c[++len]=x%10,x/=10; | ||
| - | while(len)putchar(c[len--]+48); | ||
| - | } | ||
| - | inline void space(LL x){write(x),putchar(' ');} | ||
| - | inline void enter(LL x){write(x),putchar('\n');} | ||
| const int MAXN=6e5+5,inf=1e9; | const int MAXN=6e5+5,inf=1e9; | ||
| const double alpha=0.75; | const double alpha=0.75; | ||
| 行 233: | 行 210: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <cstdio> | ||
| - | #include <algorithm> | ||
| - | #include <cstring> | ||
| - | #include <cctype> | ||
| - | #include <queue> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline void write(LL x){ | ||
| - | register char c[21],len=0; | ||
| - | if(!x)return putchar('0'),void(); | ||
| - | if(x<0)x=-x,putchar('-'); | ||
| - | while(x)c[++len]=x%10,x/=10; | ||
| - | while(len)putchar(c[len--]+48); | ||
| - | } | ||
| - | inline void space(LL x){write(x),putchar(' ');} | ||
| - | inline void enter(LL x){write(x),putchar('\n');} | ||
| const int MAXN=1e5+5,inf=0x7fffffff; | const int MAXN=1e5+5,inf=0x7fffffff; | ||
| inline LL Pow(LL x){ | inline LL Pow(LL x){ | ||
| 行 375: | 行 328: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <cstdio> | ||
| - | #include <algorithm> | ||
| - | #include <cstring> | ||
| - | #include <cctype> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline void write(LL x){ | ||
| - | register char c[21],len=0; | ||
| - | if(!x)return putchar('0'),void(); | ||
| - | if(x<0)x=-x,putchar('-'); | ||
| - | while(x)c[++len]=x%10,x/=10; | ||
| - | while(len)putchar(c[len--]+48); | ||
| - | } | ||
| - | inline void space(LL x){write(x),putchar(' ');} | ||
| - | inline void enter(LL x){write(x),putchar('\n');} | ||
| const int MAXN=1e5+5,inf=1e9; | const int MAXN=1e5+5,inf=1e9; | ||
| const double alpha=0.75; | const double alpha=0.75; | ||
| 行 528: | 行 458: | ||
| **题意** | **题意** | ||
| - | 三维空间中给定 $n$ 个点，编号为 $1 \sim n$。定义 $f[i]$ 表示恰好有 $i$ 个元素满足 $x_i\lt x_j,y_i\lt y_j,z_i\lt z_j$ 且 $i\ne j$ 的 $j$ 的个数。 | + | 三维空间中给定 $n$ 个点，编号为 $1 \sim n$。定义 $f[i]$ 表示恰好有 $i$ 个元素满足 $x_i\le x_j,y_i\le y_j,z_i\le z_j$ 且 $i\ne j$ 的 $j$ 的个数。 |
| 要求输出 $f[0 \sim n-1]$。 | 要求输出 $f[0 \sim n-1]$。 | ||
| 行 548: | 行 478: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <cstdio> | ||
| - | #include <algorithm> | ||
| - | #include <cstring> | ||
| - | #include <cctype> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline void write(LL x){ | ||
| - | register char c[21],len=0; | ||
| - | if(!x)return putchar('0'),void(); | ||
| - | if(x<0)x=-x,putchar('-'); | ||
| - | while(x)c[++len]=x%10,x/=10; | ||
| - | while(len)putchar(c[len--]+48); | ||
| - | } | ||
| - | inline void space(LL x){write(x),putchar(' ');} | ||
| - | inline void enter(LL x){write(x),putchar('\n');} | ||
| const int MAXN=1e5+5,inf=1e9; | const int MAXN=1e5+5,inf=1e9; | ||
| struct Pt{ | struct Pt{ | ||
2020-2021/teams/legal_string/jxm2001/kd_tree.1592988650.txt.gz · 最后更改: 2020/06/24 16:50 由 jxm2001
