标签归档:K-Dtree

BZOJ 1941: [Sdoi2010]Hide and Seek(K-Dtree查询平面最近点最远点)

Description

小猪iPig在PKU刚上完了无聊的猪性代数课,天资聪慧的iPig被这门对他来说无比简单的课弄得非常寂寞,为了消除寂寞感,他决定和他的好朋友giPi(鸡皮)玩一个更加寂寞的游戏—捉迷藏。 但是,他们觉得,玩普通的捉迷藏没什么意思,还是不够寂寞,于是,他们决定玩寂寞无比的螃蟹版捉迷藏,顾名思义,就是说他们在玩游戏的时候只能沿水平或垂直方向走。一番寂寞的剪刀石头布后,他们决定iPig去捉giPi。由于他们都很熟悉PKU的地形了,所以giPi只会躲在PKU内n个隐秘地点,显然iPig也只会在那n个地点内找giPi。游戏一开始,他们选定一个地点,iPig保持不动,然后giPi用30秒的时间逃离现场(显然,giPi不会呆在原地)。然后iPig会随机地去找giPi,直到找到为止。由于iPig很懒,所以他到总是走最短的路径,而且,他选择起始点不是随便选的,他想找一个地点,使得该地点到最远的地点和最近的地点的距离差最小。iPig现在想知道这个距离差最小是多少。 由于iPig现在手上没有电脑,所以不能编程解决这个如此简单的问题,所以他马上打了个电话,要求你帮他解决这个问题。iPig告诉了你PKU的n个隐秘地点的坐标,请你编程求出iPig的问题。

Input

第一行输入一个整数N 第2~N+1行,每行两个整数X,Y,表示第i个地点的坐标

Output

一个整数,为距离差的最小值。

Sample Input

4
0 0
1 0
0 1
1 1

Sample Output

1

 

HINT

对于30%的数据,N<=1000 对于100%的数据,N<=500000,0<=X,Y<=10^8 保证数据没有重点保证N>=2

还是对K-Dtree的估价函数了解不深啊,我以为最远点的估价函数和最近点的是一样的,结果样例都调不出来。但是我并不知道,这个最近点和最远点的估价函数该怎么证啊QAQ、、、

但是这次居然不用卡常啦,跑的还行,撒花~

 

BZOJ 2850: 巧克力王国(K-Dtree维护矩形中的点和)

Description

巧克力王国里的巧克力都是由牛奶和可可做成的。但是并不是每一块巧克力都受王国人民的欢迎,因为大家都不喜
欢过于甜的巧克力。对于每一块巧克力,我们设x和y为其牛奶和可可的含量。由于每个人对于甜的程度都有自己的
评判标准,所以每个人都有两个参数a和b,分别为他自己为牛奶和可可定义的权重,因此牛奶和可可含量分别为x
和y的巧克力对于他的甜味程度即为ax + by。而每个人又有一个甜味限度c,所有甜味程度大于等于c的巧克力他都
无法接受。每块巧克力都有一个美味值h。现在我们想知道对于每个人,他所能接受的巧克力的美味值之和为多少

Input

第一行两个正整数n和m,分别表示巧克力个数和询问个数。接下来n行,每行三个整数x,y,h,含义如题目所示。再
接下来m行,每行三个整数a,b,c,含义如题目所示。

Output

输出m行,其中第i行表示第i个人所能接受的巧克力的美味值之和。

Sample Input

3 3
1 2 5
3 1 4
2 2 1
2 1 6
1 3 5
1 3 7

Sample Output

5
0
4

HINT

1 <= n, m <= 50000,1 <= 10^9,-10^9 <= a, b, x, y <= 10^9。

知道这个题考的是K-Dtree,就想怎么维护出来答案,发现没有动态插入点,那么就不需要替罪羊重建了,直接建树查询即可。K-Dtree每个节点都可以代表了一个矩形区域,我们知道这个节点所代表的矩形边界后,判断一下这个节点的矩形区域是否在ax+by=c这条直线以下,如果是的话直接返回节点维护的和,否则的话分别递归下去。但是不知道为什么我的查询一直T,不断卡常后还是卡不过去,于是就去看别人的写法,改成别人那样查询居然快了10倍??

感觉对这个东西还是不够熟练,每写一次就有很大的常数问题,所以需要进一步研究。

 

 

BZOJ 2648: SJY摆棋子&2716: [Violet 3]天使玩偶 K-Dtree

Description

这天,SJY显得无聊。在家自己玩。在一个棋盘上,有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子,要么放上一个白色棋子,如果是白色棋子,他会找出距离这个白色棋子最近的黑色棋子。此处的距离是 曼哈顿距离 即(|x1-x2|+|y1-y2|) 。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子,输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。

Input

第一行两个数 N M
以后M行,每行3个数 t x y
如果t=1 那么放下一个黑色棋子
如果t=2 那么放下一个白色棋子

Output

对于每个T=2 输出一个最小距离

Sample Input

2 3
1 1
2 3
2 1 2
1 3 3
2 4 2

Sample Output


1
2
学习了一下K-Dtree,现在也只是学了个大概,简单说一下。。。如果有什么错误请尽情指出。
K-Dtree就是在k个维度这样一个空间上的一个划分,每个节点可以视为代表了一个矩形区域(在二维平面上来说)。它是一棵二叉树,而且类似于BST。毕竟如果k=1的时候,就相当于在数轴的一个划分,就是一棵BST了。
一般应用在二维平面上,比如这道题目就是在二维平面上找到一个点的最近点。
但是在二维或者更高维度上构建k-dtree的时候有一个问题,就是BST需要有一个比较,但是k个维度该怎么比较呢?有很多种方法,最简单的一种就是按照这k个维度的顺序进行轮流划分,比如对于二维平面,我们先按照x来划分这一层,找到一个根节点满足,他左儿子所代表的的矩形区域中的点都小于他的x坐标,右儿子所代表的矩形区域中的点都大于他的x坐标。这样的话每一次划分,都可以水平或者竖直的方向上把一个区域分成不相交的两部分,这样递归下去直到无法构建为止。
这样我们就知道了建树的方法,而节点信息我们主要维护的就是这个节点的x和y坐标,以及以他为根所代表的的这个矩形区域内,在x和y坐标的意义下的最大值和最小值。也就是说他所代表的那个矩形的边界信息。
当然我们可能需要维护一个Size域,因为我们可能需要动态的插入一些节点到k-dtree中,插入方式类比BST。但是这样有一个后果就是会导致k-dtree不再平衡。有一个简单的方法,就是替罪羊重构一下,来保证整棵树的平衡。
询问最近点的方式:维护一个全局变量ans,并初始为无穷大。我们先用当前根节点的信息来更新一下答案。然后拿(x,y)和根节点的左右儿子所代表的的矩形区域的边界进行比较,然后按照顺序,如果可以更优的话就更新递归下去,否则就退出。其实就是个暴力的剪枝。。。。
这样的复杂度在随机数据下是log的,但是如果构造的话是O(n)的。因为你本质上还是暴力嘛?什么数据?给你一个圆查圆心。。。。
网上很多人说是sqrt(n)其实是不对,k-dtree对于不同的询问信息复杂度不同,sqrt(n)貌似是剖矩形。。。
其实看看代码的话更好理解,了解了以上内容,那这两个题目就是裸题了。双倍经验撒花~~~