求助一道LOJ的题
  • 板块学术版
  • 楼主E_huanJX泛舟客
  • 当前回复7
  • 已保存回复7
  • 发布时间2022/11/24 20:35
  • 上次更新2023/10/27 01:39:46
查看原帖
求助一道LOJ的题
546246
E_huanJX泛舟客楼主2022/11/24 20:35

对于 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 无果后,请问大家是否有其他势函数的设计和证明,或是就这个势函数设计,对于该题的利用势能分析法的数学证明?

非常感谢!

2022/11/24 20:35
加载中...