标签: 吉司机线段树

  • MOCK quasi-PTS 20230102 日志

    又来了,要不然差临门一脚要不然是编译器出锅悬置指针导致了看似非常不合理的 undefined behavior。这已经不是简单的 frustration 了,要是考场上遇到这种根本没办法查出来的语言相关问题,不就三年 OI 一场空了么?

    不过,正是因为考试前从没“用过”悬置指针,才会诱发这样的问题。这再次提醒我们,考场上千万不要使用不熟悉的语法糖,使用平时经大量验证的写法,纵使排版稍欠美观、或代码量增长少许,也是稳定而完备的。

    不得不说,这几场“主题模拟赛”的题面中,唯这一场是最上心的。既将足球相关术语用平易近人的方式融合进题面里,又不使其过分冗长而消磨选手耐心。 (更多…)

  • 吉司机线段树(Segment Tree Beats!)复杂度分析

    这是原论文中证明的简化版本,但不失其正确性。

    记 $\newcommand\mx{\text{mx}}\mx_x$ 为 $x$ 子树中最大值,$\newcommand\smx{\text{smx}}\smx_x$ 为 $x$ 子树中严格次大值,$\newcommand\fa{\operatorname{fa}}\fa(x)$ 为 $x$ 的父亲。称节点 $x$ 为关键点,当且仅当 $x$ 是根节点,或 $\mx_{\fa(x)}\neq \mx_x$。设变量 $\Phi$ 表示目前线段树上关键点个数。 (更多…)