线段树的基础应用.ppt

线段树的基础应用-lost cows解题报告AngelClover1精品模型：n有一个未知排列。n已知排列中元素个数以及每个元素前面有多少个元素比它本身小。n求此排列。2精品思考：如果我们从前面考虑每个给出的数字的话。当前这个数字只代表了它和它前面的元素的关系。我们能不能把它转化为对一个已知整体的考虑呢？3精品n显然是可以的。n如果我们从后向前看。n每一个剩下的局部都是一个可以已知的整体。n于是，此时的Ki+1代表的就是此元素在整个集合中的位置。4精品n当我们每确定一个元素的时候，就把它从原有集合中拿出来。n于是剩下的集合又可以继续刚才的过程。5精品n我们怎么实现在一个集合中查找第K大数而且还要支持动态删除点呢。n朴素算法显然是可以的。n但是我们需要更高效的算法。6精品n于是，线段树就出场了。7精品样例：8精品9精品10精品11精品12精品13精品n于是，排列就自动倒着出现了.14精品Thanks15精品