社区讨论

求助一道LOJ的题

学术版参与者 5已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@lo7gyw0w
此快照首次捕获于
2023/10/27 01:39
2 年前
此快照最后确认于
2023/10/27 01:39
2 年前
查看原帖
对于 LOJ.6029,要求支持 1. 区间加,和 2. 区间对给定值 kk 除后下取整,对于操作 22 的具体做法就是直到 Δ=minnkminn=maxnkmaxn\Delta=\left\lfloor\dfrac{minn}{k}\right\rfloor-minn=\left\lfloor\dfrac{maxn}{k}\right\rfloor-maxnminnminn 为区间最小值,maxnmaxn 为区间最大值),这个时候将其转化为区间加 Δ\Delta
其中 LOJ 的讨论区中的@华山抡剑 大佬给出了势函数的设计 Φ=lnai+1ai\Phi=\sum \ln |a_{i+1}-a_i|,但是这个势函数的设计只涉及到元素而不是线段树和与其相关的线段树信息,所以我不是很能理解线段树操作引起的势能变化,认为这个势函数和线段树操作的时间代价联系不紧密,特别是没有给出数学证明。
在 BDFS 无果后,请问大家是否有其他势函数的设计和证明,或是就这个势函数设计,对于该题的利用势能分析法的数学证明?
非常感谢!

回复

7 条回复,欢迎继续交流。

正在加载回复...