咕果MTV onsite

Heinrich 发表于 2018-12-1 00:11
没……没错的意思就是确实是要去更新整个右半边树？

不过感觉segment tree 代码写起来更易懂。
bst维护count 感觉还是麻烦的。  segment tree 确实是只需要更新parent，就很简单了。
segment 内部的parameter 是 (left, right, start, end, count, ids)
老哥不知道有没有听说过 lazy update，要lazy update 只更新要更新的。  这道题segment tree 就是完美解法。
for example.
第一层是            0-2000, 100个
                         /                        \
第二层是   0-1000, 40个，           1000-2000， 60个
               /                 \                          /                       \
第三层是0-500，10个，500-1000，30个，1000-1500，40个，1500-2000，20个

hlckl123456 发表于 2018-12-2 01:25
不过感觉segment tree 代码写起来更易懂。
bst维护count 感觉还是麻烦的。  segment tree 确实是只需要 ...

我没听说过lazy propagation哎……是这个LC帖子里类似的概念么？https://leetcode.com/articles/a- ... s-lazy-propagation/ 我去看看把概念弄懂再来讨论哈。（这题我还没怎么搞懂怎么用segment tree做，更别说lazy propagation了）

楼主拿到offer了吗?

给你点个赞！

qiuxuxing007 发表于 2018-12-2 04:26
楼主拿到offer了吗?

HC通过啦

gky58 发表于 2018-12-2 07:02
HC通过啦

恭喜楼主！！！沾沾喜气，12月12号面，紧张地不行了……

hlckl123456 发表于 2018-12-2 01:25
不过感觉segment tree 代码写起来更易懂。
bst维护count 感觉还是麻烦的。  segment tree 确实是只需要 ...

我不是很确定用segment tree会更简单。这道题在刚开始给的时候给的分数（人）， 所以如果是建segment tree，恐怕也是以分数为range来建吧？（本身获取这个range就有点儿麻烦，需要发现这堆人分数的最大值？也就是说建这个segment tree可能就比较麻烦）往下接着想的话，以分数为range，查找的话也比较麻烦，得不断去query子节点的count，而非根据分数直接决定query哪些个子节点，也不是segment tree本意……

Anyway……我还是想想怎么用BST吧，觉得BST +lazy propagation似乎更好一些。

Heinrich 发表于 2018-12-2 09:37
我不是很确定用segment tree会更简单。这道题在刚开始给的时候给的分数（人）， 所以如果是建segment tre ...

嗯 你先做几道segment tree的题目就知道了，segement tree 很容易套公式，并且bit bst能做的它都能做，甚至能做其他不能做的，遇到不同情况只需要加parameter就好了，而且它是直接获取和更新（整个segment tree 从一开始就固定了，结构不会变），bst的话，每次更新，都要重新update树的一部分，删除node的时候重新更新count会稍微麻烦一些，要更新和它相关的所有，逻辑要稍微难写一点。

segment 不需要遍历下去，比如 要求top 100   比作左子树有80个，就可以直接拿过来 不用再遍历下去了。（只需要在每个segement tree 维护一个set（）即可）

Heinrich 发表于 2018-12-2 09:37
我不是很确定用segment tree会更简单。这道题在刚开始给的时候给的分数（人）， 所以如果是建segment tre ...

对了，蠡口的那个lazy propagation 的例子是针对更新区间值的bst做法。
如果是index的话用不到lazy propagation，就是直接lazy update（插入一个node，更新一个node的路径）

第一题： 不用最优解，如果建立一个struct A 存储<score,unordered_set<string>> ，用score表示同一个分数，set表示的人的个数。。然后对这个A 做一个list，从大到小。。同时用一个hashmap存每次对应的学号的score，来找list中element的位置。