感觉需要按照 这个顺序 重新复习一下线段树，掌握一下先进姿势！

• 李白天，《浅谈函数最值的动态维护》，国家集训队2020论文集
• 吉如一，《区间最值操作与历史最值问题》，国家集训队2016论文集
• https://cp-algorithms.com/data_structures/segment_tree.html
• 数据结构闲谈：范围分治的「双半群」模型
• Segment Tree Beats! 初步和其他
• https://oi-wiki.org/ds/seg-beats/
• USACO Guide, Segment Tree Beats
• 【补档】关于线段树上的一些进阶操作
• Kinetic tournament tree 初步
• 《浅谈函数最值的动态维护》阅读随笔

首先我觉得最重要的就是仔细学习 atc 模板：

• https://atcoder.github.io/ac-library/production/document_en/segtree.html
• https://atcoder.github.io/ac-library/production/document_en/lazysegtree.html

虽然线段树模板茫茫多，但是这个无疑依然是目前最有生命力的一个，它不仅适用范围广，速度快（里面居然是个 zkw 树），而后面的 lazysegtree 模板的原理现在大家所说的「双半群」模型。
领悟之后我们发现大部分线段树问题竟然都变成了无脑填空题囧！！

• Luogu P4314. CPU 监控
• UOJ #164. 【清华集训2015】V

而另一个技术就是势能线段树！简单来说就是有些修改操作破坏半群性质修改的情况，我们找到区间后先暴力清空，或者放宽找区间的代码，递归下去。
这样看似暴力，但是因为有些时候修改操作可以势能分析，发现复杂度没变！
最经典的模型就是区间取模取根，区间染色，以及区间 CheckMin QueryMax！

• Codeforces Round 250 (Div. 1) Problem D. The Child and Sequence
• HDU 4027. Can you answer these queries?
• Codeforces Round 254 (Div. 1) Problem C. DZY Loves Colors
• HDU 5306. Gorgeous Sequence

Posted by xiaodao
Category: 日常