激昂西装

文章
6
资源
0
加入时间
2年10月17天

poj 2104 划分树(查询区间第k大数)

题意:给定一个n个数的数组,有m个查询,每个查询为[a,b,k],意思是区间[a,b]的第k大数。思路:由这个题认识了什么叫做划分树。划分树的基本思想就是对于某个区间,把它划分成两个子区间,左边区间的数小于右边区间的数。查找的时候通过记录进入左子树的数的个数,确定下一个查找区间,最后范围缩小到1,就找到了。建树的过程比较简单,对于区间[l,r],首先通过对原数组的排序找到这个区间的中位数a