对于 LOJ.6029,要求支持 1. 区间加,和 2. 区间对给定值 k 除后下取整,对于操作 2 的具体做法就是直到 Δ=⌊kminn⌋−minn=⌊kmaxn⌋−maxn(minn 为区间最小值,maxn 为区间最大值),这个时候将其转化为区间加 Δ。
其中 LOJ 的讨论区中的@华山抡剑 大佬给出了势函数的设计 Φ=∑ln∣ai+1−ai∣,但是这个势函数的设计只涉及到元素而不是线段树和与其相关的线段树信息,所以我不是很能理解线段树操作引起的势能变化,认为这个势函数和线段树操作的时间代价联系不紧密,特别是没有给出数学证明。
在 BDFS 无果后,请问大家是否有其他势函数的设计和证明,或是就这个势函数设计,对于该题的利用势能分析法的数学证明?
非常感谢!