咕果MTV onsite

第三轮用union find set可解吧，根设为set里最大值

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

大木虫 发表于 2018-11-11 09:58
我是这样想的，你看对不对
从root看，我知道左边有几个，右边有几个，所以我知道root是第几个。假设root ...

那感觉你这个思想更像是使用binary search tree?

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

巨魔阿克 发表于 2018-11-12 06:38
那segmentTreeNode应该怎么写？

struct segmentTreeNode{

对，是BST。我散要务就是这么写的

楼主，你的第三轮是怎么从nlogn优化成n的，可以细讲一下吗

想了想感觉BST还是make sense的，每个节点存储右子树的节点个数。。。
update就是删除再插入，删除或插入均需查找&更新O(logn)个节点，复杂度为O(log n)；getEntry就是大木虫讲的思路，复杂度也是O(log n)

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

大木虫 发表于 2018-11-12 08:13
对，是BST。我散要务就是这么写的

不过这样update score得handle BST的node deletion, 的确不容易写.