UOJ Logo jiry_2的博客

博客

关于 《Segment tree Beats!》 的一些问题

2016-03-03 10:46:17 By jiry_2

这几天重新研究了一下冬令营营员交流《Segment tree Beats!》的课件,发现课件里面 $O(n \log n)$ 部分的复杂度证明似乎是伪证。

QAQ

哇

然后这两天挣扎了好久,然而既没有找到 $O(n \log n)$ 的复杂度证明,也没有构造出DFS次数 $n \log^2 n$ 的数据。(目前构造出来的数据在 $n,m = 5 \times 10^5$ 范围内暴力 DFS 次数在 $10^7$ 级别..我已经把它加到 extra test 里面重测了。)

因为感觉我的姿势水平已经无法闷声修掉这个 bug 了,所以想了一想还是把这个事故公开出来,希望对这个问题有兴趣的老司机能够带带我 QAQ。

在这一波重测结束之后我会把这道题目重新公开出来供大家 hack(因为目前还没有找到 $5 \times 10^5$ 范围内跑不出来的数据,所以就暂时不修改数据范围了)。如果因为 Hack 数据的 10M 大小限制而无法提交的话可以直接来找我,我可以直接加到 extra test 里面进行重测。

如果有老司机能构造出 $n \log^2 n$ 级别的数据 hack 或者想出更好的复杂度证明请务必和我联系,不胜感激。

评论

Ciki
反正WC上也没仔细听
mxh1999
[摸摸][祈祷] 真是悲伤的故事。。 难道以后就变成O(跑得过)了?【雾
AwD
orzorz
140142
反正WC上也没仔细听 [摸摸][祈祷]
dwjshift
【蜡烛】 为什么是伪证啊T_T
jiry_2
@dwjshift 因为标记回收那一套理论不适用于这儿。 我自己尝试证明标记回收的复杂度的时候使用的势能函数是“同一批标记加上根节点在线段树上形成的虚树大小和”。在没有区间加减或者其他修改操作的时候这么分析是对的,但是有了区间加减的话这个势能函数会有 O(n) 级别的变化就炸咯.. 当初在分析的时候对标记回收的结论太自信了..规约到标记回收上之后就没有仔细想,就当它是 mlogn 了,现在想想好像并不是很会证明 QAQ 所以就当它是伪证了。
Hentai
线段树的沉重打击

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。