差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:kd_tree [2020/06/24 15:41]
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$ 表示空间维数。
-===== 算法实现 ====
+===== 算法实现 =====
 为方便理解，这里仅讲解 2D_Tree，高维 KD_Tree 可以类推。实际上高维 KD_Tree 时间复杂度难以承受，算法竞赛中通常只涉及 2D_Tree。
@@ 行 59: / 行 59: @@
 <hidden 查看代码>
 <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 double alpha=0.75;
@@ 行 219: / 行 196: @@
 ===== 算法习题 =====
-=== 习题一 ===
+=== $K$ 远点对 ===
+[[https://www.luogu.com.cn/problem/P4357|洛谷p4357]]
+**题意**
+二维平面给定 $n$ 个点，求第 $k$ 远的点对。
+**题解**
+建树，然后对所有点查询，用小根堆维护前 $2k$ 大的数值即可。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,inf=0x7fffffff;
+inline LL Pow(LL x){
+	return x*x;
+}
+struct Point{
+	LL x,y;
+	Point(int x=0,int y=0):x(x),y(y){}
+	LL get_dis(const Point &P){
+		return Pow(P.x-x)+Pow(P.y-y);
+	}
+	void get_min(const Point &a,const Point &b){
+		x=min(x,min(a.x,b.x));
+		y=min(y,min(a.y,b.y));
+	}
+	void get_max(const Point &a,const Point &b){
+		x=max(x,max(a.x,b.x));
+		y=max(y,max(a.y,b.y));
+	}
+};
+struct Node{
+	int ch[2],cnt;
+	Point p,r1,r2;
+	void build(Point P){
+		p=r1=r2=P;
+		ch[0]=ch[1]=0;
+		cnt=1;
+	}
+	LL get_value(Point P){
+		return max(Pow(r1.x-P.x),Pow(r2.x-P.x))+max(Pow(r1.y-P.y),Pow(r2.y-P.y));
+	}
+}node[MAXN];
+void maintain(int pos){
+	node[pos].r1.get_min(node[node[pos].ch[0]].r1,node[node[pos].ch[1]].r1);
+	node[pos].r2.get_max(node[node[pos].ch[0]].r2,node[node[pos].ch[1]].r2);
+	node[pos].cnt=node[node[pos].ch[0]].cnt+node[node[pos].ch[1]].cnt+1;
+}
+int pool[MAXN],pos1,pos2,root,dimension;
+Point temp[MAXN];
+bool cmp(const Point &p1,const Point &p2){
+	if(!dimension)return p1.x<p2.x||(p1.x==p2.x&&p1.y<p2.y);
+	return p1.y<p2.y||(p1.y==p2.y&&p1.x<p2.x);
+}
+void Init(int n){
+	node[0].r1=Point(inf,inf);
+	node[0].r2=Point(-inf,-inf);
+	for(int i=n;i>=1;i--)
+	pool[++pos1]=i;
+}
+void build(int &pos,int lef,int rig,bool d){
+	if(lef>rig) return pos=0,void();
+	pos=pool[pos1--];
+	int mid=lef+rig>>1;
+	dimension=d;
+	nth_element(temp+lef,temp+mid,temp+rig+1,cmp);
+	node[pos].p=node[pos].r1=node[pos].r2=temp[mid];
+	build(node[pos].ch[0],lef,mid-1,!d);
+	build(node[pos].ch[1],mid+1,rig,!d);
+	maintain(pos);
+}
+void build(int n){build(root,1,n,false);}
+priority_queue<LL,vector<LL>,greater<LL> >ans;
+void update(LL v){
+	if(ans.top()<v){
+		ans.pop();
+		ans.push(v);
+	}
+}
+void query(int pos,Point x){
+	if(!pos)
+	return;
+	LL max_ans[2];
+	update(node[pos].p.get_dis(x));
+	max_ans[0]=node[pos].ch[0]?node[node[pos].ch[0]].get_value(x):0;
+	max_ans[1]=node[pos].ch[1]?node[node[pos].ch[1]].get_value(x):0;
+	int dir=max_ans[0]>max_ans[1]?0:1;
+	if(ans.top()<max_ans[dir])query(node[pos].ch[dir],x);dir=!dir;
+	if(ans.top()<max_ans[dir])query(node[pos].ch[dir],x);
+}
+void query(Point x){query(root,x);}
+int main()
+{
+	int n=read_int(),k=read_int(),x,y;
+	_for(i,0,k<<1)
+	ans.push(0LL);
+	Init(MAXN-1);
+	_rep(i,1,n)
+	temp[i].x=read_int(),temp[i].y=read_int();
+	build(n);
+	_rep(i,1,n)
+	query(temp[i]);
+	enter(ans.top());
+	return 0;
+}
+</code>
+</hidden>
+=== 矩阵维护 ===
 [[https://www.luogu.com.cn/problem/P6514|洛谷p6514]]
@@ 行 241: / 行 328: @@
 <hidden 查看代码>
 <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 double alpha=0.75;
@@ 行 388: / 行 452: @@
 </hidden>
-=== 习题二 ===
+=== 优化技巧 ===
 [[https://www.luogu.com.cn/problem/P3810|洛谷p3810]]
@@ 行 394: / 行 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]$。
@@ 行 414: / 行 478: @@
 <hidden 查看代码>
 <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;
 struct Pt{

CVBB ACM Team

用户工具

站点工具

差别

页面工具