K-Dtree

建 K-D tree

用于维护多维空间上的节点的相对状态或位置。将所有的点组成二叉搜索树。

以二维空间点举例：

10----x
9-----|---x
8     |   |
7---x |   |
6---|-x   |
5---|-|---|---------x
4   | |   |         |
3---|-|- -|- -x     |
2-x | |   |   |     |
1-|-|-|-x |   |     |
0 1 2 3 4 5 6 7 8 9 10

按 $x$ 维排序后取最中间的说数作为根节点，将整个“图”二分（将所有数分成左右两部分）。

10    x |
9       | x
8       |  
7   x   |  
6     x |  
5       |           x
4       |      
3       |     x      
2 x     |            
1       x            
0 1 2 3 4 5 6 7 8 9 10

k-d tree

        (4,1)

继续在左右部分二分，但这时要按 $y$ 维排序二分（一点个人理解：这么做的原因可以统计在一条线上的点，即不掉点，例如上图的 $(3,6)$ 和 $(3,10)$ 两个点。只要两个点不重合，就一定会加到树上）。

10    x |
9       | x
8       |  
7---x---|  
6     x |  
5       |-----------x-
4       |      
3       |     x      
2 x     |            
1       x            
0 1 2 3 4 5 6 7 8 9 10

k-d tree

        (4,1)
         / \
        /   \
       /     \
      /       \
     /         \
  (2,7)      (10,5)
     

接着，继续按 $x$ 维排序后二分插入树中，直至所有点全部插入。

10    x | |
9     | | x
8     | | |
7---x---| |
6 |---x-| |
5 |     |-----------x-
4 |     |     |
3 |     |     x      
2 x     |     |      
1 |     x     |      
0 1 2 3 4 5 6 7 8 9 10

k-d tree

           (4,1)
            / \
           /   \
          /     \
         /       \
        /         \
     (2,7)      (10,5)
      / \         / \
     /   \       /   \
  (1,2) (3,10)(5,9) (7,3)
     \
    (3,6)
     

建树结束，妙用在题中展现。

简单题

P4148 简单题

替罪羊树

替罪羊树是计算机科学中，一种基于部分重建的自平衡二叉搜索树。在替罪羊树上，插入或删除节点的平摊最坏时间复杂度是 $O(\log n)$，搜索节点的最坏时间复杂度是 $O(\log n)$。

有一个“估价”常量，如果一棵树的的某个子树的大小超过“估价”。将整棵树敲碎，然后重组。复杂度 $O(n)$，但是一定不会没回都重建所以均摊建树复杂度 $O(\log n)$。

“估价”常量不能大于 $1.0$ 或小于等于 $0.5$，前者会导致没有操作，后者会导致每回操作。

大体思路

• 动态开点（开垃圾桶，要多次删点，开点）
• 实现节点信息更新（区间管辖范围，区间和，子树大小）
• 检查是否用“重组”树
• 删点
• 重新建树操作
• 实现单点修改操作
• 判断节点区间于目标区间的相对关系
• 实现查询操作

代码

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cctype>
using namespace std;
int r_r(){//快读 
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
const int o_o=1e6+10;//数组下标大小 
struct po{
	int x,y;//坐标 
	int v;//价值 
	po(){};
	po(int x_x,int y_y,int v_v){
		x=x_x,y=y_y,v=v_v;//初始化 
	}
}p_p[o_o];
struct k_d{
	int l,r;//左右子树 
	
	//节点覆盖范围 
	int m_i_x;//最小 x 
	int m_i_y;//最小 y 
	int m_a_x;//最大 x 
	int m_a_y;//最大 y 
	
	int s_m;//区间和 
	int s_z;//子树大小 
	po p_p;//节点信息 
}t_r[o_o];
const double c_z=0.75;//子树占整棵树多少需要重构 
int d_x;//要重构节点个数 
int n;
int x_p;//新点编号 
int g_g;//根节点 
int s_m;//垃圾桶中节点数量 
int r_s[o_o];//节点垃圾桶 
bool c_1(po a,po b){//按 x 排序 
	return a.x<b.x;
}
bool c_2(po a,po b){//按 y 排序 
	return a.y<b.y;
}
int n_w(){//动态开点 
	if(s_m)return r_s[s_m--];
	return ++x_p;
}
void u_p(int k){
	t_r[k].m_i_x=t_r[k].m_a_x=t_r[k].p_p.x;//初始化横坐标最大最小值 
	if(t_r[k].l){//存在左节点，更新最大最小值 
		t_r[k].m_i_x=min(t_r[k].m_i_x,t_r[t_r[k].l].m_i_x);
		t_r[k].m_a_x=max(t_r[k].m_a_x,t_r[t_r[k].l].m_a_x);
	}
	if(t_r[k].r){//存在右节点，更新最大最小值 
		t_r[k].m_i_x=min(t_r[k].m_i_x,t_r[t_r[k].r].m_i_x);
		t_r[k].m_a_x=max(t_r[k].m_a_x,t_r[t_r[k].r].m_a_x);
	}
	t_r[k].m_i_y=t_r[k].m_a_y=t_r[k].p_p.y;//初始化纵坐标最大最小值 
	if(t_r[k].l){//存在左节点，更新最大最小值 
		t_r[k].m_i_y=min(t_r[k].m_i_y,t_r[t_r[k].l].m_i_y);
		t_r[k].m_a_y=max(t_r[k].m_a_y,t_r[t_r[k].l].m_a_y);
	}
	if(t_r[k].r){//存在右节点，更新最大最小值 
		t_r[k].m_i_y=min(t_r[k].m_i_y,t_r[t_r[k].r].m_i_y);
		t_r[k].m_a_y=max(t_r[k].m_a_y,t_r[t_r[k].r].m_a_y);
	}
	t_r[k].s_m=t_r[t_r[k].l].s_m+t_r[k].p_p.v+t_r[t_r[k].r].s_m;//更新权值大小 
	t_r[k].s_z=t_r[t_r[k].l].s_z+t_r[t_r[k].r].s_z+1;//更新子树大小 
}
void d_l(int k){//删点 
	if(!k) return;//节点不存在，返回 
	p_p[++d_x]=t_r[k].p_p;//记录要删的点的信息 
	r_s[++s_m]=k;//“垃圾”回收 
	d_l(t_r[k].l);//删左子树 
	d_l(t_r[k].r);//删右子树 
}
int z_b(int l,int r,int w){
	if(l>r) return 0;//非法范围，返回 
	int m_i=(l+r)>>1;
	int k=n_w();//开新节点 
	nth_element(p_p+l,p_p+m_i,p_p+r+1,w?c_2:c_1);//按顺序排序（按 x 或 y 排序）区间第 m_i 小 
	t_r[k].p_p=p_p[m_i];//继承信息 
	t_r[k].l=z_b(l,m_i-1,w^1);//左子树 
	t_r[k].r=z_b(m_i+1,r,w^1);//右子树 
	u_p(k);//更新节点信息 
	return k;//返回节点编号 
}
void f_b(int &k,int w){
	if(t_r[t_r[k].l].s_z>c_z*t_r[k].s_z||t_r[t_r[k].r].s_z>c_z*t_r[k].s_z){
		d_x=0;//初始化要重构点的个数 
		d_l(k);//删点 
		k=z_b(1,t_r[k].s_z,w);//重构 
	}
}
void a_d(int &k,po n_n,int w){
	if(!k){//节点不存在，创建节点 
		k=n_w();
		t_r[k].l=t_r[k].r=0,t_r[k].p_p=n_n;//初始化节点信息 
		u_p(k);//更新节点信息 
		return;
	}
	if(!w&&n_n.x<=t_r[k].p_p.x)a_d(t_r[k].l,n_n,1);//当前是按 x 排序，目标横坐标比当前值小，前往当前节点的左儿子 
	else if(!w)a_d(t_r[k].r,n_n,1);//当前是按 x 排序，目标横坐标比当前值大，前往当前节点的右儿子 
	else if(w&&n_n.y<=t_r[k].p_p.y)a_d(t_r[k].l,n_n,0);//当前是按 y 排序，目标纵坐标比当前值小，前往当前节点的左儿子 
	else a_d(t_r[k].r,n_n,0);//当前是按 y 排序，目标纵坐标比当前值大，前往当前节点的右儿子 
	u_p(k);//更新节点信息 
	f_b(k,w);//检查是否要重新建树 
}
bool n_i(int x_1,int y_1,int x_2,int y_2,int x_x,int y_y,int _x_,int _y_){
	return x_1<=x_x&&x_2>=_x_&&y_1<=y_y&&y_2>=_y_;//当前矩形在查询范围内 
}
bool w_i(int x_1,int y_1,int x_2,int y_2,int x_x,int y_y,int _x_,int _y_){
	return x_1>_x_||x_2<x_x||y_1>_y_||y_2<y_y;//完全范围外（完全不重合） 
}
int f_i(int k,int x_1,int y_1,int x_2,int y_2){
	if(!k) return 0;//子树不存在，不贡献 
	if(n_i(x_1,y_1,x_2,y_2,t_r[k].m_i_x,t_r[k].m_i_y,t_r[k].m_a_x,t_r[k].m_a_y))
		return t_r[k].s_m;//范围内直接加值 
	if(w_i(x_1,y_1,x_2,y_2,t_r[k].m_i_x,t_r[k].m_i_y,t_r[k].m_a_x,t_r[k].m_a_y))
		return 0;//完全不重合返回 
	int a_s=0;
	if(n_i(x_1,y_1,x_2,y_2,t_r[k].p_p.x,t_r[k].p_p.y,t_r[k].p_p.x,t_r[k].p_p.y))
		a_s+=t_r[k].p_p.v;//当前节点判断 
	a_s+=f_i(t_r[k].l,x_1,y_1,x_2,y_2)+f_i(t_r[k].r,x_1,y_1,x_2,y_2);//左右子树 
	return a_s;//返回统计结果 
}
int main(){
	n=r_r();
	int op,l_t=0;
	while((op=r_r())!=3){
		if(op==1){//值增加 
			int x=r_r(),y=r_r(),v=r_r();
			x^=l_t,y^=l_t,v^=l_t;//解密 
			a_d(g_g,po(x,y,v),0);//增加 
		}else{//矩阵内数字和 
			int x_1=r_r(),y_1=r_r(),x_2=r_r(),y_2=r_r();
			x_1^=l_t,y_1^=l_t,x_2^=l_t,y_2^=l_t;//解密 
			printf("%d\n",l_t=f_i(g_g,x_1,y_1,x_2,y_2));//查询 
		}
	}
	return 0;
}

ZPFAR

P2093 国家集训队 JZPFAR

主要思路：

• 建树
• 通过优先队列存储
• 判断优先级更新值
• 输出队顶元素值的编号

代码

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cctype>
using namespace std;
long long r_r(){//快读 
	long long x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
const int o_o=1e6+10;//下标大小  
const long long m_a=0x3f3f3f3f3f3f;//定义极大值 
int g_g;//根节点 
int z_y;//根据相同维度排序 
int x_p;//新编号赋值 
struct po{
	int x_y[2];//x，y 信息 
	int i_d;//编号 
	bool operator < (const po&a)const{//距离从大到小排 
		return x_y[z_y]<a.x_y[z_y];//根据相同维度排序 
	}
}p_p[o_o];
struct pp{
	int l,r;//左右子树 
	int m_a[2];//x 和 y 最大值 
	int m_i[2];//x 和 y 最小值 
	int i_d;//编号 
	po v;//节点信息 
}t_r[o_o];
struct f_a{
	int i_d;//编号 
	long long v;//价值 
	f_a(){};
	f_a(int p_p,long long b){//赋初值 
		i_d=p_p;
		v=b;
	}
	bool operator < (const f_a&a)const{//定义值只按一种排序方式 
		if(v==a.v)return i_d<a.i_d;
		return v>a.v;
	}
	bool operator > (const f_a&a)const{//定义值只按一种排序方式 
		if(v==a.v)return i_d<a.i_d;
		return v>a.v;
	}
};
priority_queue<f_a> q;
void u_p(int g_g){
	for(int i=0;i<2;i++){//遍历 x 和 y 
		t_r[g_g].m_a[i]=t_r[g_g].m_i[i]=t_r[g_g].v.x_y[i];
		if(t_r[g_g].l){//存在左子树 
			t_r[g_g].m_a[i]=max(t_r[g_g].m_a[i],t_r[t_r[g_g].l].m_a[i]);
			t_r[g_g].m_i[i]=min(t_r[g_g].m_i[i],t_r[t_r[g_g].l].m_i[i]);
		}
		if(t_r[g_g].r){//存在右子树 
			t_r[g_g].m_a[i]=max(t_r[g_g].m_a[i],t_r[t_r[g_g].r].m_a[i]);
			t_r[g_g].m_i[i]=min(t_r[g_g].m_i[i],t_r[t_r[g_g].r].m_i[i]);
		}
	}
}
void b_t(int &g_g,int l,int r,int d){//建树 
	if(l>r)return;//不符合合法情况 
	g_g=++x_p;//新节点赋新编号 
	int m_d=(l+r)>>1;
	z_y=d;//根据相同维度排序 
	nth_element(p_p+l,p_p+m_d,p_p+r+1);//将中间节点位置放好 
	t_r[g_g].v=p_p[m_d];//继承基础信息 
	t_r[g_g].i_d=p_p[m_d].i_d;
	b_t(t_r[g_g].l,l,m_d-1,d^1);//左子树 
	b_t(t_r[g_g].r,m_d+1,r,d^1);//右子树 
	u_p(g_g);//更新节点信息 
}
long long p_f(long long x){//计算平方 
	return x*x;
}
long long g_d(int g_g,po v){
	long long t_p=0;
	for(int i=0;i<2;i++)//点到矩形顶点中的最远曼哈顿距离 
		t_p+=p_f(max(abs(v.x_y[i]-t_r[g_g].m_a[i]),abs(v.x_y[i]-t_r[g_g].m_i[i])));
	return t_p;
}
long long d_s(int x,int y,int x_x,int y_y){//两点之间距离 
	return 1ll*(x-x_x)*(x-x_x)+1ll*(y-y_y)*(y-y_y);
}
void f_i(int g_g,po v){
	
	//从根节点开始找 
	f_a t_p=f_a(t_r[g_g].i_d,d_s(v.x_y[0],v.x_y[1],t_r[g_g].v.x_y[0],t_r[g_g].v.x_y[1]));
	if(t_p>q.top())q.pop(),q.push(t_p);//比目标大，更新 
	long long l_a=-m_a,r_a=-m_a;//极小值初始化 
	if(t_r[g_g].l)l_a=g_d(t_r[g_g].l,v);//存在左子树，向左子树询问 
	if(t_r[g_g].r)r_a=g_d(t_r[g_g].r,v);//存在右子树，向右子树询问 
	
	//值更大者优先 
	if(l_a<r_a){
		if(r_a>=q.top().v)f_i(t_r[g_g].r,v);
		if(l_a>=q.top().v)f_i(t_r[g_g].l,v);
	}else{
		if(l_a>=q.top().v)f_i(t_r[g_g].l,v);
		if(r_a>=q.top().v)f_i(t_r[g_g].r,v);
	}
}
int main(){
	int n=r_r();
	for(int i=1;i<=n;i++){
		for(int j=0;j<2;j++)p_p[i].x_y[j]=r_r();//读入点坐标信息 
		p_p[i].i_d=i;//初始化编号 
	}
	b_t(g_g,1,n,0);//建树 
	int m=r_r();
	while(m--){
		int k;
		po w;
		w.x_y[0]=r_r(),w.x_y[1]=r_r(),k=r_r();//读入初始信息 
		while(!q.empty())q.pop();//清空序列 
		while(k--)q.push(f_a(0,-1));//加入 k 次极小值（初始化） 
		f_i(g_g,w);//查找 
		printf("%d\n",q.top().i_d);//输出编号 
	}
	return 0;
}