清爽老师

文章
1
资源
0
加入时间
2年10月18天

HDU 4417 Super Mario (树状数组)

思路:首先我们先回顾一下树状数组。树状数组的的直接目的即区间求和(logn)。但由于具有logn单点修改的功能使得区间求和更为方便。对于这道题来说,我们先对m个询问中的h升序排序,利用了<=h1的元素一定也<=h2这个递推式,然后将n个数也排序,但同时需要记录这些数原本的位置信息。对于每个询问,我们将符合hi条件的点加入树状数组,注意,我们是将这个点原来的位置加入树状数组(数量是1)。这样构造