@TOC日常两道题今天之前都做了，所以重新提交。这两道题我在考线段树和科多里都可以过，但是科多里比较快。[[python刷题模板]Cordoli树ODT](https://blog.csdn.net/liulian...)[[python刷题模板]线段树](https://blog.csdn.net/liulian......)[【LeetCode解题报告】699.掉落的立方体](https://blog.csdn.net/liulian...)题目一，731.我的日程表II731。我的时间表附表II1。标题描述我的日程表II难度：中等实现一个MyCalendar类来存储您的日程表。如果要添加的时间不会导致三次预订，则可以存储此新时间表。MyCalendar有一个book(intstart,intend)方法。这意味着在开始和结束之间添加一个时间表。注意这里的时间是一个半开区间，即[start,end)，实数x的范围是，start<=xbool:m=self.树。query(1,1,10**9+1,start+1,end)如果m>=2:返回Falseself.tree.add(1,1,10**9+1,start+1,end,1)returnTrue2.699.FallingBlocks链接：699.FallingBlocks1.TitleDescriptionFallingBlocks难度：难度在二维平面的x轴上。放置一些块给你一个二维整数数组positions，其中positions[i]=[lefti,sideLengthi]表示：第i个块的边长为sideLengthi，它的左边与坐标对齐x轴上的左点。每个块从比所有当前下降的块更高的高度下降。该块沿负y轴下降，直到它落在另一个正方形的顶部边缘或x轴上。一个方块仅仅通过另一个方块的左边缘或右边缘不算作着陆。一旦着陆，它就会固定在原地，无法移动。每个块落下后，您必须记录到目前为止已经稳定的所有堆叠块的最高高度。返回一个整数数组ans，其中ans[i]代表第i个方块被丢弃后栈的最高高度。示例1：输入：positions=[[1,2],[2,3],[6,1]]输出：[2,5,5]解释：第一个方块被丢弃后，最高的堆叠由方块1组成，最大堆叠高度为2。第2个方块落下后，最高的堆叠由方块1和2组成，最大堆叠高度为5。第3个方块落下后，最高的堆叠仍然由方块1和2组成，最大堆叠高度为5.因此，返回[2,5,5]作为答案。示例2：输入：positions=[[100,100],[200,100]]输出：[100,100]解释：第1个块落下后，最高堆栈由块1组成，最高堆栈高度为100。第2个块落下后，最高栈可以由块1或块2组成，最大堆栈高度为100。因此，返回[100,100]作为答案。请注意，掠过方格1右侧的方格2不算落在方格1上。Tips:1<=positions.length<=10001<=lefti<=1081<=sideLengthi<=1062思维分析块落下时，显然高度取决于本块底边管辖范围内当前最高的块，这个方块将落在最上面。那么我们需要的就是一个快速查询区间极值和快速区间赋值的数据结构。显然，线段树可以。这道题范围比较大，但是可以离线，所以我们离散化一下。这道题有很多区间拉平的操作，Cordoli可以做到。这里还是线段树，如果需要Cordoli，可以去我上面贴的地址看看。3.代码实现classIntervalTree:def__init__(self,size):self.size=sizeself.interval_tree=[0for_inrange(size*4)]self.lazys=[0for_inrange(size*4))]defgive_lay_to_son(self,p,l,r):interval_tree=self.interval_treelazys=self.lazysiflazys[p]==0:returnmid=(l+r)//2interval_tree[p*2]=lazys[p]interval_tree[p*2+1]=lazys[p]lazys[p*2]=lazys[p]lazys[p*2+1]=lazys[p]lazys[p]=0defupdate(self,p,l,r,x,y,val):"""把[x,y]区域全变val"""ifyList[int]:n=len(positions)hashes=[leftforleft,_inpositions]+[left+sideforleft,sideinpositions]hashes=sorted(list(set(hashes)))#使用线段树维护x轴区间的??最大值，记录下每个点的高度：例如[1,2]这个盒子会让线段[1,2]上的每个高度闭区间变成2#当一个新的方块落下时，查询其底边线段[x,y]的最大高度h，此方块将落在这个高度h，并将新的高度h+side插入线段树[x,y]#每次插入结束时，树根的高度为当前最大高度#由于数据范围较大1<=lefti<=108，所以需要进行散列#散列后的值有左和右（短线段）#print(hashes)tree_size=len(hashes)tree=IntervalTree(tree_size)heights=[]forleft,dinpositions:right=left+dl=bisect_left(hashes,left)r=bisect_left(hashes,right)h=tree.query(1,1,tree_size,l+1,r)tree.update(1,1,tree_size,l+1,r,h+d)heights.append(tree.interval_tree[1])returnheights人生苦短，我用Python！
