[学习笔记]李超线段树

这个之前学过的，结果我发现我忘了，怕之后再忘，我就再写一下吧。毕竟这个东西非常有用(好写)可以代替cdq/平衡树+斜率优化，来优化dp

流程

数据结构本质是一棵线段树，每个节点都储存了/(bst[]/)。
/(bst[l,r]/)表示覆盖该点范围的在/(mid/)处取最值的线段。
你会想：维护这个有什么用？每个点就只能维护一个，复杂度和正确性怎么保证？
便于理解，就直接讲操作了。

加入（一条线段/(id/)）

从根遍历线段树。令/(F(k,x)/)表示自变量为/(x/)在线段/(k/)上取值。假如这里的最值是/(max/)。

• 如果/(bst[x]=0/)，/(bst[x]=id/)结束。
• 如果/(F(id,mid)>F(bst[x],mid)/)，更新/(bst[x]/)，不过我们做的是/(swap(bst[x],id)/)此时原来的/(bst[x]/)就替换了/(id/)（处于待加入状态）。
• 接下来虽然/(id/)在中点处不如/(bst[x]/)，但在两端处可不一定，但是我们发现了一个可以保证复杂度的性质：/(id/)至多在左或右的一端优于/(bst[]/)(像一个跷跷板…)。
  这样/(id/)在哪边优就往哪边继续递归。当然如果左右两端（整条线段劣于/(bst/)，自然就结束了）
• 最后在叶子时，发现保存的恰好是/(mid/l/r/)取值最优线段。结束。
• 复杂度/(O(log^2n)/)：划分为/(log_2n/)个区间后，每个区间都有可能执行到叶子
  特别的：加入直线是/(O(logn)/)因为没有划分区间的过程了。

查询

• 单点查询直接从上一直到叶子或/(bst=0/)取每个点的值更新。
• 如果是区间查，就需要存一个变量表示子树最值，加入时P_up()即可维护。

应用 (都是优化dp的，不想特别去讲了)

[HEOI2013]Segment
「NOI2007」货币兑换
外层套树链剖分:[SDOI2016]游戏
又是sdoi: [SDOI2012]基站建设