树结构在程序设计中的运用

1、树结构在程序设计中的运用浙江省4年NOI组队赛1目录引言树结构在程序设计中的运用2 2003年竞赛的知识结构分布 竞赛试题算法NOIP乒乓球数据统计NOIP数字游戏动态程序设计NOIP栈回溯法或组合数学的Catalan数NOIP麦森数高精度运算NOIP神经网络图的递归运算NOIP侦探推理回溯法NOIP加分二叉树递归的动态程序设计NOIP传染病扩展回溯法3 竞赛试题算法IOI 可视边界线段树IOI 代码转换程序语句在满足加法交换率和变量名改换情况下的匹配IOI 猜牛游戏贪心或类博弈树算法IOI 路径维护在无向图的生成过程过程中计算最小生成树IOI 逆向输出开放性试题IOI 机器人宽度优先搜索20

2、03年竞赛的知识结构分布4 竞赛试题算法NOI 木棒游戏枚举搜索NOI文本编辑器数据结构NOI 卫星探测二分查找NOI草莓后序遍历NOI 数据生成器前序遍历和后序遍历NOI智破连环阵回溯法2003年竞赛的知识结构分布5试题特点1、强调基础知识的灵活应用。每一轮竞赛都有基础知识题，但对灵活应用基础知识的要求愈来愈高。例如IOI的路径维护在逐边添入无向图的过程中计算最小生成树；文本编辑器要求设计多样的数据结构。例如线性表、非线性的树和图；NOIP的加分二叉树采用的动态程序设计是递归形式的；NOI的数据生成器必须综合使用前序遍历和后序遍历2、首次出现了线段树和可以选择类博弈树算法的试题3、近似算法类

3、的试题增加。例如IOI的猜牛游戏、逆向输出、机器人、NOI的卫星探测、草莓、智破连环阵等。由于这些例题视程序逼近最优解和最优效率的程度给分，因此拓展了选手思维的空间，易启发选手的创造性。但反过来说，由于近似算法类的选题空间比较大，因此有可能使得题目的难度加大。6试题特点4、树形结构类的问题增多。例如NOI的卫星探测通过二分查找构造一棵隐形的二叉树；草莓和数据生成器使用了人们容易被忽视的后序遍历；IOI的路径维护要求计算最小生成树；5、可“一题多解”和开放性的试题增多。例如，IOI的逆向输出就是一道没有固定模式和经典算法可套用、需要量身定制合适算法的试题；猜牛游戏既可以采用贪心法，亦可以采用类博

4、弈树的算法；NOIP的栈既可以通过回溯法计算，亦可以通过组合数学的Catalan数计算；6、出现一些“陷阱题”。例如NOIP的传染病扩展极易诱导选手错误地使用贪心法或动态程序设计，实际上该问题不具备最优子结构的特征，正确的算法是回溯搜索。7启示培养内省智力充分利用网络资源以问题为出发点、以自主探究为途径、以构造网络式思维模式为基础、以创新为目的组织集训 8培养内省智力入门 自信心提高 自省力自信心和自知之明是对立的统一。自信心倘若不是建立在自知之明的基础上，则会变成一种无知的自负，不可能取得持续的成功。 科学精神的核心是怀疑和批评。这种态度既对他人又对自己，“知人者智，自知者明”，“知常曰明”

5、 不能用看书取代上机实践，经常要想“自己怎样面对这个问题的挑战；如果由自己当场独立解题的话，会得到怎样的结果”。“纸上得来终觉浅，绝知此事要躬行”。看懂了不稀奇，会做有灵气，能讲清原理、提出质疑、拓延思路、探索新知才算了不起在挑选练习题时，既不要因为轻视而放弃基础题；也不要因为畏难而放弃大题难题。 9充分利用网络上与信息学活动相关的信息资源1、由于网络上大量的算法知识和试题的出现，使得学生学习的大部分时间和空间由课堂转移到网上学习，自主性显著提高，学习方式发生了根本性的变化2、学习的效率取决于如何在浩如烟海的网上信息中选择适应于竞赛需要和个性发展的东西3、千万不要有“太易了不屑做、太难了不愿做

6、”的主观随意性 10充分利用网络上与信息学活动相关的信息资源编程解题能力是在长期的上机实践中积累起来的。如果长期的无所事事、无所作为，迟早会落得了“小题做不对、大题难题不会做”的可悲结局应该对试题本身有一个科学的价值判断：“这道题是不是有利于夯实基础，或者这道题是不是引出带规律性的东西，能不能派生出更多类似的问题”，真正从提高自身的算法认知水平和编程能力的高度，来决定练习题的取舍。 11以问题为出发点、以自主探究为途径、以构造网络式思维模式为基础、以创新为目的组织集训第一步：界定问题。即明确试题要求我们做什么,解决什么问题，输出怎样的结果第二步：明确出发点，即明确试题的初始状态是什么，给出了哪

7、些求解条件，其中哪些是显性的，哪些是隐性的，必须无一漏失。第三步：寻找怎样做的创意。即要求学生独立思考，尽可能多地收集相关资料，尝试各种组合，调动所有的灵感和思考方式。第四步：集中测试。每人设计三组测试数据,分别从一般情况、边界情况、扩大问题规模三个角度测试程序的正确性、时间效率和空间效率。然后交流测试数据，学生间进行互测。这样做既能测出自己程序的正确程度，又能在改善程序的时空效率上取长补短。 12建立知识信息网络 归纳概括 通过对相关问题（即形式不同、本质类似的一类问题）的归纳，揭示内在的联系，概括出解决类似问题的一般规律，并得到高度抽象、概括的模型，为以后分析问题、设计算法进行指导。 13

8、触类旁通、联想外推 通过举一反三、由此及彼、触类旁通，从一个问题拓广出许多新问题。在解决这些新问题的过程中，进一步锻炼思维，并通过联想的线索将新问题、新模型、新算法并入知识网14近年来，由于各种竞赛纷纷采用free-pascal，因此对于算法来说，空间效率上的要求降低了，而对时间效率却提出了更高的要求。这使得选手不仅要娴熟地掌握常规算法，而且要大胆创新，构造更高效的算法来解决问题。在以往的程序设计中，链式结构采用得较多。的确链式结构有编程复杂度低、简单易懂等优点，但有一个致命的弱点：相邻的两个元素间的联系并不明显。而树结构却能很好的做到这一点。选手对树的先根遍历十分娴熟，但对后根遍历却不能像先

9、根遍历那样应用自如。15树结构在程序设计中的运用一并查集二线段树三解决动态统计的静态方法四、二叉树应用的拓广五、先根遍历与后根遍历的应用小结16并查集 竞赛中会经常遇到这样的题目：给出各个元素之间的联系，要求将这些元素分成几个集合，每个集合中的元素直接或间接有联系。在这类问题中主要涉及的是对集合的合并和查找，因此将这种集合称为并查集。 链结构的并查集 树结构的并查集17链结构的并查集链表被普通用来计算并查集.表中的每个元素设两个指针：一个指向同一集合中的下一个元素；另一个指向表首元素。 采用链式存储结构，在进行集合查找时的算法复杂度仅为O（1）；但合并集合时的算法复杂度却达到了O（n）。如果我

10、们希望两种基本操作的时间效率都比较高的话，链式存储方式就“力不从心”了。18树结构的并查集采用树结构支持并查集的计算能够满足我们的要求。并查集与一般的树结构不同，每个顶点纪录的不是它的子结点，而是将它的父结点记录下来。下面我介绍一下树结构的并查集的两种运算方式直接在树中查询边查询边“路径压缩”对应与前面的链式存储结构，树状结构的优势非常明显：编程复杂度低；时间效率高。 返回19直接在树中查询集合的合并算法很简单，只要将两棵树的根结点相连即可，这步操作只要O（1）时间复杂度。算法的时间效率取决于集合查找的快慢。而集合的查找效率与树的深度呈线性关系。因此直接查询所需要的时间复杂度平均为O（logN

11、）。但在最坏情况下，树退化成为一条链，使得每一次查询的算法复杂度为O（N）。20边查询边“路径压缩” 其实，我们还能将集合查找的算法复杂度进一步降低：采用“路径压缩”算法。它的想法很简单：在集合的查找过程中顺便将树的深度降低。采用路径压缩后，每一次查询所用的时间复杂度为增长极为缓慢的ackerman函数的反函数（x）。对于可以想象到的n，（n）都是在5之内的。21银河英雄传说 【问题描述】公元五八一年，地球居民迁移至金牛座第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。 宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱

12、因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。 杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1， 2， ， 30000。之后，他把自己的战舰也依次编号为1， 2， ， 30000，让第i号战舰处于第i列(i = 1， 2， ， 30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为Mij，含义为让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队

13、列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。 在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：Cij。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。 作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。 最终的决战已经展开，银河的历史又翻过了一页22【输入文件】输入文件galax

14、y.in的第一行有一个整数T（1T500，000），表示总共有T条指以下有T行，每行有一条指令。指令有两种格式：1. Mij：i和j是两个整数（1i ， j30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第i号战舰与第j号战舰不在同一列。2.Cij：i和j是两个整数（1i ， j30000），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。【输出文件】输出文件为galaxy.out。你的程序应当依次对输入的每一条指令进行分析和处理：如果是杨威利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；如果

15、是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目。如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。23设var Father，Count，Behind：array1.maxn of integer；在同一队列中的战舰组成一个树型结构的并查集。Fatherx 战舰x的父指针。Fatherx=x，表明战舰x为根节点。路径压缩后，树中所有子节点的父指针指向根节点；Countx 以节点x为根的树的节点数；Behindx 战舰x在列中的相对位置；初始时，我们为每一艘战舰建立一个集合，即Fatherx=x Countx=1 Be

16、hindx=0（1x30000) 241、查找根节点并进行路径压缩 function Find_Father(x：integer)：integer；查找节点x所在树的根节点，并进行路径压缩var i，j，f，next：integer；begin ix； 找出节点x所在树的根节点f while Fatherii do iFatheri； fi；ix； while if do 按照自下而上的顺序处理x的祖先节点 begin nextFatheri；FatherIf；把节点i的父节点设为f，完成路径压缩 jnext； repeat BehindiBehindi+Behindj；迭代求出路径上每一个子

17、节点相对于f的相对位置 jFatherj； until Fatherj=j； inext； end；while find_Fatherf； 返回x所在树的根节点end； Find_Father 252、计算合并指令 procedure MoveShip(x，y：integer)；把x所在的集合合并入y所在的集合var fx，fy：integer；begin fxfind_Father(x)；计算x所在树的根节点fx fyfind_Father(y)；计算y所在树的根节点fy Fatherfxfy；将fx的父节点设为fy BehindfxCountfy；计算fx的相对位置为Countfy Cou

18、ntfyCountfy+Countfx；计算新集合的节点数end； MoveShip 263、计算询问指令 procedure CheckShip(x，y：integer)；计算x节点和y节点的相对位置情况var f1，f2：integer；begin f1Find_Father(x)；计算x所在树的根f1 f2Find_Father(y)；计算y所在树的根f2 if f1f2 若x，y不在一棵树中，则返回-1，否则返回x和y间隔的战舰数then writeln(-1)else writeln(abs(Behindx-Behindy)-1)；end； CheckShip 27由此得出主程序：

19、for i1 to maxn do 初始时为每一艘战舰建立一个并查集 begin Fatheri i； Counti 1； Behindi 0； end；for readln(CmdCount)； 读指令数 for i1 to CmdCount do 顺序处理每一条指令 begin read(ch)；读第i条指令的类型 case ch of M：begin readln(x，y)；MoveShip(x，y)； end；处理合并指令 C：begin readln(x，y)；CheckShip(x，y)； end；处理询问指令 end；case end；for 28线段树 动态处理可以映射在一个坐

20、标轴上的一些固定线段，例如求并区间的总长度，或者并区间的个数等等。 优点：随时插入一个区间或删除一个已有区间，并同时用低耗费维护需要的性质。29线段树-构造思想下图显示了一个能够表示1，10的线段树： 30特点1、叶结点表示一个初等区间：a,b=a+1;每一个内部结点b-a1;2、根为a,b的线段树为T(a,b),其左子树为T(a,(a+b)/2),右子树为T(a+b)/2,b),直至细分为一个初等区间（叶结点）为止。 31线段树的存储结构1、动态数据结构TypeTnode=Treenode;Treenode=recordB,E:integer; 该区间为B,ECount:integer;记录

21、覆盖到B,E区间的线段条数LeftChild,Rightchild:Tnode;左右子树的根End;322、静态数据结构用数组B，E，C，LSON，RSON。设一棵线段树的根为v。那么Bv,Ev就是它所表示区间的界。Cv记录覆盖到B,E区间的线段的条数。LSONv，RSONv分别表示了它的左儿子和右儿子的根编号。 33线段树的运算1、建树 从根对应的区间a，b出发，每次分成两个部分，分别建立对应的左右子树，直到面临一个初等区间x,x+1。设一个全局变量n，来记录一共用到了多少结点。开始n=0procedure BUILD(a,b)Begin n n+1；v n；Bva；Evb；Cv0； if

22、b a1 thenbegin LSONvn+1；BUILD(a, （a+b）div 2)； RSONvn+1；BUILD(（a+b）div 2 ,b); end; end;342、插入线段将区间c,d插入线段树T(a,b),并设T(a,b)的根编号为v procedure INSERT(c，d，v)Begin mid=(Bv+Ev) div 2;计算（a,b）的中间点 if cBv and Evd若(c,d)覆盖（a,b），则区间数+1 then Cv cv+1 else begin若（c,d）位于(a,b)的左半区间，则递归插入v的左子树；若（c,d）位于(a,b)的右半区间，则递归插入v的

23、右子树 if cmid then INSERT(c,d;RSONv); end;end 353、删除线段在线段树T(a,b)中删除区间c,d,并设T(a,b)的根编号为v：procedure DELETE(c,d;v) begin if cBv and Evd 若(c,d)覆盖（a,b），则区间数-1 then Cv Cv-1 elsebegin若（c,d）位于(a,b)的左半区间，则递归删除v的左子树；若（c,d）位于(a,b)的右半区间，则递归删除v的右子树 if c (Bv+Ev) div 2 then DELETE(c,d;RSONv); end；end 特别注意：只有曾经插入过的区间

24、才能够进行删除。这样才能保证线段树的维护是正确的。36 线段树的动态维护1、计算测度结点的测度Mv 指的是结点v所表示区间中线段覆盖过的长度。Cv0,Mv = Ev-Bv;Cv=0 且v是叶子结点，Mv=0；Cv=0 且v是内部结点，Mv=MLSONv+MRSONv; 37连续线段数linev指的是区间中互不相交的线段条数。连续线段数并不能像测度那样将两个子结点中的连续线段数简单相加。于是我们引进了两个量lbdv，rbd v ，分别表示区间的左右两端是否被线段覆盖。 1 (左端点被线段覆盖到)lbdv = 0 (左端点不被线段覆盖到) 1 (右端点被线段覆盖到)rbdv = 0 (右端点不被线

25、段覆盖到)2、计算连续线段数38Lbd=1rbd=1line可以根据lbd，rbd定义如下： 1 (count 0) 0 (count=0 且结点为叶结点) Line= lch.Line + rch.Line - 1 (count=0 且结点为内部结点，lchrbd、 rchlbd都为1) lch.Line + rch.Line (count=0且结点为内部结点，hrbd, rchLbd不同时为1) 39线段树的变形对点统计原线段数记录基数的Cv这时就可以用来计算落在定区间内的点个数了。原搜索路径也发生了改变，不存在“跨越”的情况。同时插入每个点的时候都必须深入到叶结点，因此一般来说都要有lo

26、gn的复杂度。 应用这样的线段树一方面是方便计数。另一方面由于它实际上是排序二叉树，所以容易找出最大和最小来。 40例一商品促销一位顾客要进行n（1n5000）天的购物，每天他会有一些帐单。每天购物以后，他从以前的所有帐单中挑出两张帐单，分别是面额最大的和面额最小的一张，并把这两张帐单从记录中去掉。剩下的帐单留在以后继续统计。输入的数据保证，所有n天的帐单总数不超过1000000并且每份帐单的面额值是1到1000000之间的整数。保证每天总可以找到两张帐单。 41建立点线段树，范围是1，1000000，即每种面额的帐单设为一个叶结点。 如果CLSONv0,那么树v中的最小值一定在它的左子树上。

27、如果CRSONv0，它的最大值在右子树上； 线段树的深度为log 1000000 =2042改进的办法 用hash来保存每一种面额的帐单数目，然后对于一个具体的帐单（面额V），在线段树中保存V/100的值，即把连续的100种面额的帐单看成是一组。由于V的范围是1.1000000，所以线段树中有10000个点。在找最大的数的时候，首先找到最小的组，然后在hash里对这个组进行搜索，显然这个搜索的规模不会超过100。由于线段树变小了，所以树的深度只有14左右，整个问题的复杂度极限为N*14+n*14*100*2，对于问题的规模来说，仍然是高效率的。但这样做比前种方法在一定程度上节省了空间。同时实际

28、上也提醒了我们对线段树应该加以灵活的应用。43 农夫Don要监察他的N米乘N米(2 N 500,000)的正方形田园的围栏。该围栏的一角在原点(0，0)上，另一对角則在坐标点(N，N)上, 围栏的边平行於X轴及Y轴。围栏上有些支柱, 這些支柱分別立在围栏的四個角上及围栏的每条边上每隔1米的地方, 因此整个围栏上就有4N根支柱。這些支柱是垂直的，而且可以认为其半径为0。农夫Don希望知道，当他站在田园中的某一点时他可以看到的支柱的数量。 农夫Don的田园內有R块巨石 (1 R 30,000) 阻碍他的视线。因為他不夠高，无法从巨石上面望过去，因此有些支柱看不到。巨石的底部是一个面积不为零的凸多边

29、形, 而多边形的端点坐标均为整数。巨石垂直地立在地上。巨石之間不重叠，互相之間不接触， 巨石与农夫Don或围栏也不接触。农夫Don所站立的地方也不接触围栏，他也不会站在巨石內或巨石上。 给定农夫Don的围栏大小, 其內的巨石的位置及形状，以及农夫Don所站立的位置, 求出Don在该位置上可以看到的支柱数量。如果一根支柱在农夫Don的视线上刚好和巨石的边重叠，则农夫Don是看不到该支柱的。 可视边界44将统计农夫位置“可视”的正方形四条边界上的整点总数问题，简化为计算农夫站立位置到正方形下边界线的可视点数的问题。 我们按逆时针顺序枚举多边形i的每一个顶点（1ir），不断调整最左端的顶点序号min

30、和最右端的顶点序号max，并按照下述方法计算区间lt、rt若第j个顶点位于农夫位置的上方(yijy01)，则分析：若第j个顶点位于农夫位置的左方（xijx01），则设区间左端点lt为0；否则设区间右端点rt为n-145若第j个顶点位于农夫位置的下方(yijy01)，则计算截点的x坐标（hv为截点存在标志）x0= x01+ *y01） lt= rt= 如果正方形下边界线上不存在截点（hv=false），是不是意味着正方形下边界线上的顶点都是可视点呢？不一定 即过农夫位置引垂直于X轴的射线，如果与凸多边形i最左的顶点min、最右的顶点max所连线段不相交，则凸多边形i不挡住正方形下边界线上的任何整

31、点；否则凸多边形i挡住了正方形下边界线。相交的标志是农夫位置的x坐标位于顶点min的x坐标和顶点max的x坐标之间（(ximinx01ximax)）且交点在农夫位置之下（yimin+ *(x01-ximin)y01） 46构建区间表xx和tp 区间表xx。xx存储正方形下边界线上被r个凸多边形挡住的所有区间； 区间表元素的类型tp。其中 tpi=1，表明排序前的xxi为区间左端点的x坐标； tpi=-1，表明排序前的xxi为区间右端点的x坐标， lg:=0;区间表的长度清零 for i:=1 to r do依次处理每个凸多边形 begin 计算正方形下边界线被凸多边形i挡住的区间lt,rt x

32、xlg+1:=lt; xxlg+2:=rt;将lt,rt存入区间表 tplg+1:=1; tplg+2:=-1; inc(lg,2) end;for47计算正方形下边界线上被挡住的整点数a1 目标是计算正方形下边界线上被各个区间的线段覆盖过的长度a1（简称a1为测度）。这里有两种做法： 建立线段树，最后统计测度；将xx和tp中所有区间的端点lt,rt进行排序，根据tp表自左而右扫描一遍，利用统计点值的和s统计测度a1：48 sort(1,lg);对区间表进行分治排序 s:=0; al:=0;初始化点值和与测度 for i:=1 to lg do(从左到右扫描区间表的每一个元素) if tpi=

33、1一个新区间开始 then begin if s=0 then lt:=xxi;若点值和为0，则该截点作为连续区间的左端点 inc(s) 点值和+1 endthen else begin(若当前区间结束，统计测度) if s=1 then al:=al+trunc(xxi)-trunc(lt-zero)+ord(lt1e-6); dec(s) 点值和-1 end;else 显然，正方形下边界线上的可视点数为n-a1。 49主程序 输入信息； ans:=0; for t:=1 to 4 do分别处理正方形四条边 begin 构建区间表xx和tp； 计算正方形下边界线上被挡住的整点数a1； ans

34、:=ans+n-al;将农夫所能看到的正方形t边上的支柱数n-a1记入ans for i:=0 to r do将每一个凸多边形逆时针转90度，以便将下一条边旋转至下底边 for j:=1 to pi do begin x0:=xij;y0:=yij;xij:=n-trunc(y0); yij:=trunc(x0) endfor end;for 输出农夫Don所能看到的支柱数ans ； 50线段树的总结1、线段树经过左右分割以后具有二叉排序树的性质；2、线段树的建立方式非常适用于处理线段，对于点的问题，亦可以推广应用3、线段树上的一个结点分裂为两个半区间的时候实际上是通过一个中间点来分割的；4、

35、在线段树上需要设立左右指针；结点表示区间，但处理点的时候不需要保留这样的区间。51一定范围内计数问题的特点1 描述简单2 要求对数据动态维护，动态计算3 解决手段：特殊的统计模式和结构怎样用静态方法解决动态统计的问题？52一种静态统计方法例题IOI2001 MOBILES ：在一个N*N的方格中，开始每个格子里的数都是0。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子矩阵(x1,y1)-(x2,y2)中所有元素的和；修改的规则是指定某一个格子(x,y)，在(x,y)中的格子元素上加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1N1024,提问和修改的总数可能达到

36、60000条。 53一维序列求和设序列的元素存储在a中，a的下标是1.n的正整数，需要动态地更新某个ax的值，同时要求出ax1到ay1这一段所有元素的和（sum(1,y1)-sum(1,x1-1)）。 54对于序列a1.n，设一个数组C1.n 其中Ci=ai- 2k +1+ai k为i在二进制下末尾0的个数。例如10000 k =4 C10000 =a10001+ a10000 计算Cx对应的2k LOWBIT（x）=2k =x and (x xor (x-1)55修改一个ax的值 与C的哪些下标变量p相关？ 例如x=76=(1001010)2，从形式上进行观察，可以得到： p1= 10010

37、10 p2= 1001100 p3= 1010000 p4= 1100000 p5=修改Cp1,Cp2,56procedure UPDATA(x,A)begin px while (p0) do begin ansans+Cp pp-LOWBIT(p) endreturn ansend Cp=ap- 2k +1+ap下一个p=x- 2k58推广为原来的二维问题，把C构造成 Cx，y，其每一维定义与原来相同。推广后算法：两层嵌套，一次维护费用为O(log2n)59在解决点统计问题时，多考虑静态二叉排序树二分法的虚拟实现树60集合3，4，5，8，19，6 静态二叉排序统计树实现是把所有要处理的点坐

38、标离散化，形成一个排序的映射，例如我们称为X映射，并且设其中一共有n个不同的对象。例如在上例中，X=3，4，5，6，8，19，n=6。 第一个点61静态二叉排序统计树与一般二叉排序树的区别1、一般二叉排序树的结构由输入顺序决定的2、静态二叉排序统计树的结构由区间中间点决定，因此需要预先排序62把X映射中的点值填入到树中，使它有上面的构造。这里我们选择静态结构作为对二叉树的支持。将二叉树的结点从上到下，从左到右进行编号，并令根结点的编号为1。即上图中对应的编号应该是：对于任何一个编号为i的结点，它的左儿子编号自然为i*2，右儿子编号为i*2+1。现在要把X的映射填入到数组V中去。V1.n应该保存

39、相应位置上的点值。注意到对V对应的二叉树进行中序遍历的结果就对应X中的映射，所以可以通过递归的方法建立V：63构造过程1 递归：建立所有点坐标的映射Xp 0 作为X映射中的指针procedure BUILD(ID:integer) beginif (ID*2n) then BUILD(ID*2); pp+1； VID=Xp； if (ID*2+1n) then BUILD(ID*2+1);end在主程序中调用BUILD(1) 64构造过程2 非递归 方法，依次找出当前点的后继点的下标 第一个点first一定为最下层最左边的一个位置,若n个点有L层,则first=2 L-1function fi

40、rst:integerbeginlevel 1, tot = 2while (tot-1n) do begin levellevel+1；tottot*2 end return tot div 2end65若当前的点位置为now：如果它有右儿子，即now*2+1x) thennownow*2x在now的左子树方向 else nownow*2+1x在now的右子树方向until falseEnd删除 的方法是类似的672、插入时，计算每个结点以及其左子树上顶点的总数设LESS表示值小于等于根结点值的总数 (LESSI=SUMI-SUMI*2+1)：procedure INSERT1(x)Begi

41、nnow 1repeat if (xx) then nownow*2 计算左儿子指针 else nownow*2+1计算右儿子指针 until falseend68利用二叉排序统计树解决MOBILES问题这个过程与前一个大同小异。实际上LESSI=SUMI-SUMI*2+1。举这个例子在于说明利用二叉排序树的结构，是很容易结合具体的问题进行变化的。我们对其变化，甚至也可以利用来解决MOBILES问题。只要将刚才LESS的定义作一点变化，令它为根及其左树上所有点上的权和。如果要在ax上增加A。可以很容易得到：69procedure INSERT2(x,A)beginnow 1repeat if

42、(xx) then nownow*2 else nownow*2+1until falseend70求a1.x的元素和SUM(x)function SUM(x):longintbeginans 0now 1repeat if (Vnowx) then nownow*2 else nownow*2+1until falsereturn ansend 71例题采矿(KOP) 金矿的老师傅年底要退休了。经理为了奖赏他的尽职尽责的工作，决定送他一块长方形地。长度为S，宽度为W。老师傅可以自己选择这块地。显然其中包含的采金点越多越好。你的任务就是计算最多能得到多少个采金点。如果一个采金点的位置在长方形的

43、边上，它也应当被计算在内。 任务：读入采金点的位置。计算最大的价值。 输入：文件KOP.IN的第一行是S和W，(1=s,w=10000);他们分别平行于OX坐标和OY坐标，指明了地域的尺寸。接下来一行是整数n (1=n=15000)，表示采金点的总数。然后是n行，每行两个整数，给出了一个采金点的坐标。坐标范围是(-30000=x,y=30000)。 输出：一个整数，最多的采金点数。72样例图示73初步，对X离散化后，图示741、对于每一种坐标y，建立成两个点事件(y,+1),(y+w+1,-1)，例如在一个带状区域内有5个点的纵坐标分别是5，3，9，1，9，w=2 ，标成(1,+1),(4,-

44、1),(3,+1),(6,-1),(5,+1),(8,-1),(9,+1),(12,-1), (9,+1),(12,-1),2、将他们按照y的坐标排序，得(1,+1),(3,+1),(4,-1), (5,+1)， (6,-1), (8,-1), (9,+1), (9,+1),(12,-1), (12,-1)3、把后面的标号反映在一个y坐标的映射上，然后从低到高求和 75坐标下的求和，这些和中最大的一个就是该带状区域中一个包含最多点数的矩形 在插入或者删除一个点事件之后，能够维持坐标下的值；能够在很短时间内得到中最大的一个值。 76实现：SUMnow对应子树上所有+1，-1标号的和。实现极简单M

45、AXSUMnow，子树上和最大的一个前缀值。MAXSUM1是一种状态下得到最优解。如何维护？MAXSUM有哪几种可能？ 1 最大值在左树上； 2 最大值正好包含根结点； 3 最大值在右树上。 77自下而上维护树的特性procecure INSERT(y,k)begin now 1 repeat 向下找到y所在的结点 if Vnow=y then breakif Vnowy then nownow*2+1 else nownow*2until false; Repeat 再向上，对路径上的每个点的SUM和MAXSUM进行修改 SUMnowSUMnow+k MAXSUMnowMax 对取得连续和最

46、大值的3种情况 进行决策 MAXSUMnow*2, 最大值在左树上 SUMnow-SUMnow*2+1, 最大值正好包含根结点 SUMnow-SUMnow*2+1+MAXSUMnow*2+1 最大值在右树上 now now div 2 until now = 0 End;78二分法虚拟实现树二叉树使用之前必须构造出一个空的二叉树 对于任何一个有序表，在对其进行二分查找时，实际上就等于在一个二叉树上进行查找 79对于一个有序表1，3，4，8，9的二分查找，等价于在如下图的二叉排序树上进行查找： m取中间位置值，即为一棵树的树根，它左边的所位置值即l,m-1构成了其左子树上的形态，而m+1,r构成

47、了右子树上的形态 。等价的二叉排序树是平衡二叉树。最多logn次查找就可以指定的结点。 80举插入结点的例子，来说明这种虚实现的方法设LESS表示根及其左树上结点的个数： procedure INSERT(x)beginl1,rnwhile (l=r) do begin m=(l+r) div 2 if x=Vm then LESSmLESSm+1 if x =Vm then break if xVm then r m 1 else lm+1 endend 81例4在一个平面直角坐标系上有n个点，n最多为15000，要求每个点的左下方有多少个点，也就是说对于每个点xi,yi，求满足xjxi并且

48、yjyi的j的个数。1、按照x为第一关键字、y为第二关键字的顺序对所有点进行升序排列2、对排好序的y坐标建立映射关系，放在V数组中，并按照先前点排序的顺序依次把各个y插入到计数用的LESS中去，同时就可以得到一个点左下方的值。 82function INSERT-AND-GET(y):integerbegin l1,rn ans0 while (l=r) do begin m=(l+r) div 2 if y=Vm then ansans+LESSm if y =Vm then break if yVm then r m 1 else lm+1 end return ansEnd 复杂度为O(

49、logn) 83例题最长下降序列给定一个整数序列a，求最长下降序列的长度。设mi为ai的前缀中（包括ai ）的最长下降序列的长度。该序列中ai前的整数为api1、最基本的解决方法O（n2)84 对P进行特殊的限制，即在所有等价的(相同长度)决策j中，P选择aj最大的那一个 在处理完a1.x-1之后，对于所有长度为Mx-1的下降序列，Px的决策只跟其中末尾最大的一个有关。 用另外一个动态变化的数组b，当我们计算完了ax之后，a1.x中得到的所有下降序列按照长度分为L类，每一类中只需要一个作为代表，这个代表在这个等价类中末尾的数最大，我们把它记为bj,1jL。 处理当前的一个数ax，我们无需和前面

50、的aj（1jx-1）作比较，只需要和bj（1jL)进行比较。 85 首先，如果ax=b1，这时ax 仅能构成长度为1的下降序列，同时它又必然是最大的，所以它作为b1的代表,b1=ax。 如果前面的情况都不存在，我们肯定可以找到一个j,2jL,有bj-1ax,bjax，这时分析，ax必然接在bj-1后面，行成一个新的长度为j的序列。 86 这几种情况实际上都可以归结为：处理ax，令bL+1为无穷小，从左到右找到第一个位置j，使bjax,然后则只要将bj=ax,如果j=L+1,则L同时增加。x处以前对应的最长下降序列长度为Mx=j。 顺序查找L 0； 下降序列的最大长度初始化for x1 to n

51、 do beginbL+1无穷小 j1从左到右找到第一个使得bjax的位置j while (bjax) do jj+1 bjax if jL then Lj end 87顺序查找更改成二分法查找 L0 下降序列的最大长度初始化for i1 to n do begin j1;kL;在b1.bL中二分法查找第一个使得bjax的位置j while (jk) do改为二分法查找 begin m (j+k) div 2; if bmai then jm+1 else km-1; end if jL then LL+1；bjai end88卫星探测（Detect）【问题描述】A国最近检测到了B国内有不正常

52、的辐射，经调查发现，这是因为B国正在耗资百亿研制新式武器连环阵。可是，由于B国对此武器的高度保密措施，A国的间谍甚至无法确定出连环阵的具体位置。不过，A国的卫星还是可以找出连环阵所在的基地的。我们现在知道该基地是一个边上含有放射性物质的凸多边形。经研究发现，在这个凸多边形所在的平面内，它具有如下性质： 包含坐标原点；任意两条边不在同一直线上；没有和x轴或y轴平行的边； 所有顶点的x坐标和y坐标都是整数。现在A国可以通过卫星发出无限大的扇形探测波，与该凸多边形所在平面交于一条直线。不过该直线不是与x轴平行，就是与y轴平行。通过反射信号，我们可以确定该直线与凸多边形的交点个数和所有交点的坐标（如果

53、有的话）。现在，需要你写一个程序，通过控制卫星发出的探测波来确定这个凸多边形。891、通过二分法确定凸多边形的左端顶点和右端顶点 我们通过readx（at，nm，y1，y2）过程询问直线x=at与凸多边形交点的个数nm和两个交点坐标y1、y2。 rcdat,1.3为x=at与凸多边形交点的y坐标和交点个数Procedure readx(at:longint;var nm:longint;var y1,y2:double);询问直线x=at与凸多边形的相交情况begin if rcdat,10 如果以前询问过，则直接返回询问结果 then begin nm:=round(rcdat,3);y1:

54、=rcdat,1; y2:=rcdat,2 endthen else begin nm:=ask_x(at,y1,y2);询问直线x=at与凸多边形的交点 if y1y2y1和y2按照递增排列 then begin y1:=y1+y2;y2:=y1-y2;y1:=y1-y2 end;then rcdat,1:=y1;rcdat,2:=y2; rcdat,3:=nm记录询问结果 endelseend; readx 90fillchar(rcd,sizeof(rcd),0); 询问结果初始化 hd:=-10000; tl:=0; md:=0;设定左端顶点所在的区间，交点个数初始化 while tr

55、ue do begin md:=(hd+tl) div 2;将询问的直线设在区间中点处 readx(md,nm,y1,y2);计算该直线与凸多边形的交点y1、y2和交点个数nm if nm=1 then break;若仅有一个交点，则退出循环 if nm=0 then hd:=md+1若没有交点，则取右区间 else tl:=md-1若有两个交点，则取左区间 end;while x1:=md;y1:=round(y1);确定左端顶点的坐标hd:=0; tl:=10000; md:=0;设定右端顶点所在的区间，交点个数初始化while true do begin md:=(hd+tl) div

56、2;将询问的直线设在区间中点处 readx(md,nm,y1,y2);计算该直线与凸多边形的交点y1、y2和交点个数nm if nm=1 then break;若仅有一个交点，则退出循环 if nm=2 then hd:=md+1若有两个交点，则取右区间 else tl:=md-1若没有交点，则取左区间 end;while显然，通过上述运算后，（x1，y1）为凸多边形最左方顶点的坐标；（md，y1）为凸多边形最右方顶点的坐标 912、按照先下方、后上方的顺序计算凸多边形的顶点坐标 在找出凸多边形的左端点和右端点之后，由左端点开始，沿着上方的路径和下方的路径，逐步找出凸多边形的其他顶点。其中每次

57、从当前顶点（X0，Y0）开始，先询问直线XX01确定下一条边的斜率tg=y-y0 然后二分地寻找斜率开始发生变化的顶点，这个顶点就是下一个顶点 92计算与凸多边形的下一个顶点相邻的两条直线每次二分查找的边界不必定得过大。由于之前我们已经进行过了一些询问，询问的结果存储在rcd数组中。我们可以充分利用已得到的信息，通过rcd数组限制边界范围，即确定一个顶点在rcd数组中哪两条相邻直线之间，将这两条直线设为下一次询问的边界。设目前已得出凸多边形的第n个顶点为（xn，yn），尚待计算的下一个顶点在rcd数组中的直线x=lt和直线x=rt之间，这两条相邻直线与凸多边形相交的情况存储在rcdlt和rcd

58、rt中。凸多边形与直线x=lt的交点（lt，rcdlt，1）(计算上方顶点时交点为（lt，rcdlt，2）)连接（xn，yn）的直线斜率 =tg；凸多边形与直线x=rt的交点（rt，rcdrt，1）(计算上方顶点时交点为（rt，rcdrt，2）)连接（xn，yn）的直线斜率 tg。我们从xn+1出发，由左而右计算直线x=lt；从凸多边形的右端点的x坐标-1出发，由右而左计算直线x=rt：93结合跨度kd二分查找 由于直线x=lt和直线x=rt是目前询问到的两条直线，因此其在x轴的间隔完全可能大于1。如何以尽可能少的询问次数找到位于两条直线间的凸边形顶点（xn+1，yn+1）呢？ 凸边形的边（x

59、n，yn），（xn+1，yn+1）经过点（xn+1，y），由此得出该边的斜率为tg=y-yn。由于凸边形顶点（xn+1，yn+1）的坐标为整数，因此位于x=xn与x=xn+1间的有些直线不会与斜率tg的直线交与整数坐标，这些直线不必询问。 为了尽可能将这些顶点从询问范围内剔除，我们将斜率tg化为一个既约分数A/B，把B（而不是1）作为询问的“跨度”，即每一次询问，x直线的间隔距离为B。这个B值可以枚举。 我们通过函数get_kd(tg)计算询问的“跨度”Bfunction get_kd(x:double):longint;求跨度 var i:longint; begin get_kd:=0;

60、for i:=1 to 20000 do if abs(x*i-round(x*i)1e-6 then begin get_kd:=i; exit endend; get_kd 94按照先下方、后上方的顺序计算凸多边形的顶点坐标 tx:=md;n:=1; 记下凸多边形左端的x坐标 repeat从顶点1出发，计算凸多边形下方各边的顶点坐标 readx(xn+1,nm,y1,y2);计算（xn，yn）至（xn+1，y1）的斜率tg tg:=y1-yn;kd:=get_kd(tg);计算跨度kd lt:=xn; rt:=tx;与第n+1个顶点相邻的两条直线初始化 for i:=xn+1 to tx