D题每次算长度贡献的复杂度证明?
看了一些题解和代码,每次算长度贡献时,l[i]表示i能到达的最左端,r[i]表示i能到达的最右端
算贡献时枚举l[i]~i的点就t了,但是枚举l[i]~i与i~r[i]的更短的那一边就跑的飞快
感觉后者在特殊数据下也会被卡成n^2更新
有无大佬能解释一下
看了一些题解和代码,每次算长度贡献时,l[i]表示i能到达的最左端,r[i]表示i能到达的最右端
算贡献时枚举l[i]~i的点就t了,但是枚举l[i]~i与i~r[i]的更短的那一边就跑的飞快
感觉后者在特殊数据下也会被卡成n^2更新
有无大佬能解释一下
相关推荐