首页 > 牛客推荐系统开发之标签重复度
开通博客写题解
头像 范艺杰
发表于 2021-06-11 22:30:39
考虑使用点分树维护，每次维护经过点分中心的权值。我们考虑计算每个点到点分中心的最小值和最大值，然后合并两个到点分中心的路径。将这样的最大最小值对按最小值排序后，计算贡献。考虑到后计算到的点最小值一定更大，则只有两种情况。1.最大值比之前的大，则贡献是之前的最小值乘现在的最大值。2.最大值比之前的小， 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 issue是云哥的小迷×呀
发表于 2021-06-13 11:20:10
LINK 比较明显的点分治问题,考虑如何计算通过点的路径贡献 获得从出发的所有路径,显然经过的所有路径都是由出发的两条路径拼接而来 每条路径存成一个,第一关键字为最大值,第二关键词为最小值 现在就是一个简单的二维偏序问题 一下那么每个位置的最大值一定比前面大 然后使用动态开点权值线段树，最小值为下标 展开全文
去ta的博客 赞 (2) 回复(1) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”