国家集训队2004论文集 林涛

《国家集训队2004论文集 林涛》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线段树的应用广西柳铁一中林涛线段树的定义线段树是一棵二叉树，记为T(a,b)，参数a,b表示区间[a,b]，其中b-a称为区间的长度，记为L。线段树T(a,b)也可递归定义为：若L>1:[a,(a+b)div2]为T的左儿子；[(a+b)div2,b]为T的右儿子。若L=1:T为叶子节点。表示区间[1,10]的线段树样例：[1,10][1,5][5,10][1,3][3,5][5,7][7,10][1,2][2,3][3,4][4,5][5,6][6,7][7,8][8,10][8,9][9,10]

2、线段树的特征定理二：线段树把区间上的任意一条线段都分成不超过2logL条线段。这些结论为线段树能在O(logL)的时间内完成一条线段的插入、删除、查找等工作，提供了理论依据定理一：线段树的深度不超过logL。线段树的基本操作插入一条线段：每个节点增加一个变量记录该节点被插入所有线段覆盖的次数，自根节点往下，直到一个被线段完全覆盖的节点。节点被插入的线段覆盖记录变量加1，儿子不再处理节点与插入线段不相干该节点及儿子都不作处理相干但不被覆盖把线段分别插入它的两个儿子删除一条插入过的线段，与插入操作是一致

3、的。查找一个区间内线段的总长度。每个节点增加一个变量记录该区间内线段的总长度，并在插入和删除后维护相关节点的这个变量：儿子区间内的线段长度+覆盖本区间的线段长度例1：蛇（SGU128）在平面上有N个点，现在要用一些线段将它们连起来，使其满足以下要求：1这些线段必须闭合2线段的端点只能是这N个点。3交于一点的两条线段成90度角4线段都必须平行于X轴或Y轴5所有线段除了在这N个点外不相交6所有线段的长度之和必须最短如果存在这样的线段，则输出最小长度，否则输出0。XY【问题分析】所求的图形是以题目所给的N

4、个点为顶点的多边形。每条边要和X轴或Y轴平行。每个顶点与一条平行于X轴和一条平行于Y轴的线段相连。XYP1P2P3P4P5P6P7P8P1P2P3P4P5P6将所有点排序后发现，在同一水平线的点中，设为P1，P2，P3，P4……Pn，P1必须连它右边的点——P2，P3只能连P4，P5连P6……，同垂直线上的点也是如此。如果有解，解是唯一的，那么最小长度的问题就解决了。不相连—不合法不自交—合法自交—不合法由于解是唯一，所以关键在于判断由上述方法构出的图形是否合法——满足线段不自交：【问题分析】如图，

5、两条线段在内部相交，则必须满足x1

6、点数。按顺序，扫描所有事件：如果遇到平行于X轴线段的左端点，则插入到线段树中，遇到右端点，则从线段树中删除。如果遇到平行于Y轴的线段，则在线段树中查找。S1S2S3S4将Ｙ轴坐标离散后，每次插入、删除、查找的复杂度是Ｏ(logn)级别的，由于所有线段数量是Ｏ(n)级别的，所以整题的复杂度是Ｏ(nlogn)级别。思考：本题删除的点与插入的点一一对应，所以删除实现很方便。如果删除的线段不一定插入过该怎么办？例2：空心长方体（POI99Cuboid）在一个三维正坐标系中，存在N(N<=5000)个点，现在

7、要求一点P(x，y，z)，使得O(0，0，0)与P(x，y，z)两个顶点构成的长方体内不包括N个点中的任何一个点(在长方体边缘不算包括)，并使这个长方体的体积最大。x，y，z均不得超过1000000。【问题分析】P(x,y,z)代表的长方体包含一点Q，那么P的所有坐标值，都大于Q点的坐标值。Px>QxPy>QyPz>Qz体积最大的长方体，其P点任意轴的坐标，都与N个点中的一个相同或者和边界相同。【问题分析】在已经确定P的X坐标情况下,将所有点的y坐标排序，得到序列y[1]，y[2]，y[3]……。m

8、ax[i]记录P的Y轴坐标为y[i]时，Z轴坐标的最大取值，数组max的值是单调不增的。把所有点按X轴坐标排序，当P点的X坐标与第i个点相同时，第i及第i以后的点都不可能被P包含了。y[i]>Qy把max看成一个区间y[i]>Qymax[j]>z可以看出每增加一个点的限制，需要修改的是一个区间，要高效的进行区间操作就可以用到线段树。【问题分析】从小到大枚举P点的X坐标，这个过程中要不断维护数组max。因为P的X坐标由第i个点的变成第i+1个点的，第i个点的坐标就会增加