D题每次算长度贡献的复杂度证明?

看了一些题解和代码,每次算长度贡献时,l[i]表示i能到达的最左端,r[i]表示i能到达的最右端

算贡献时枚举l[i]~i的点就t了,但是枚举l[i]~i与i~r[i]的更短的那一边就跑的飞快

感觉后者在特殊数据下也会被卡成n^2更新

有无大佬能解释一下

全部评论
完全二叉树能卡满,我也造了完全二叉树,但是效果没那么理想。
点赞 回复 分享
发布于 2024-06-09 09:14 陕西
nlog^2n,类似笛卡尔树上启发式合并,枚举较小的一棵子树合并
点赞 回复 分享
发布于 2024-06-09 09:04 陕西

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务