前言

“李超线段树，简称李超树。它支持插入直线或线段，并查询某个横坐标处的最值。”

本文以最大值为例，讨论广义李超线段树，与传统的李超线段树不同，它插入的是函数而非直线或线段，但为了保证正确的时间复杂度，对函数有较严格限制，见条件。

不展开讨论对于 \(x=k\) 时函数值相等时的具体处理，可依题意而定。

正文

广义李超线段树可以在线解决下述问题添加函数 \(f_i\) 或给定 \(x\) 求 \(\max\{f_i(x)\}\).

条件

定义 \(f(x)\) 和 \(g(x)\) 的大小关系交换为从 \(f(x)>g(x)\) 变为 \(f(x)<g(x)\)，或反之，则有：当 \(f\) 和 \(g\) 的大小关系交换次数 \(\le 1\) 时，函数 \(\text{v}(f,g)=1\)，否则 \(\text{v}(f,g)=0\) 。当函数集合 \(F\) 满足 \(\forall \alpha,\beta\in F,\text{v}(\alpha,\beta)=1\)，则 \(F\) 可以用李超线段树维护。

过程

考虑区间 \([l_i,r_i]:\)
1. 去除区间绝对劣势函数 \(f_{\text{bad}}:\forall x\in[l_i,r_i],f_{\text{bad}}(x)<f_{\text{tag}_i}(x)\)，一定不是解；
2. 保留优势函数 \(f_{\text{tag}_i}:\forall \phi,f_{\text{tag}_i}(m_i)>\phi(m_i)\) 不下放；
3. 下放相对优势函数 \(f_{\text{good}}:\exists x\in[l_i,r_i],f_{\text{good}}(x)>f_{\text{tag}_i}(x),\text{good}\neq\text{tag}_i\) 至子区间，条件保证其在某一区间绝对劣势。

以上是插入新函数时区间需要做的事，时间复杂度 \(O(\log V)\).

考虑整体：
1. 叶子节点 \([w,w]\) 的函数中除了其区间优势函数，其他都是绝对劣势函数，会被筛掉（不考虑相同）；
2. 非叶子节点，除区间优势函数和绝对劣势函数，其他函数都下放直至成为区间绝对劣势函数，或区间优势函数留在某结点；
3. 相对优势函数不会存在。

查询 \(k\) 时是在所有剩下的 \(\log V\) 个区间的优势函数，即非绝对劣函数内选取最大，这显然正确，时间复杂度 \(O(\log V)\).

实现

核心思想是维护 区间最优函数，及时排除不优答案，实现时，维护 \(\text{tag}_i\) 表示 \([l_i,r_i]\) 的最优函数编号，即定义域完全覆盖 \([l_i,r_i]\) 并且在 \(m_i=\dfrac{l_i+r_i}{2}\) 处 取值最大 的函数。

不考虑定义域，插入函数 \(f_j\)，设当前区间为 \([l_i,r_i]\)，中点为 \(m_i\)。若 \(f_j(m)>f_{\text{tag}_i}(m)\)，则 \(f_j\) 比 \(f_{\text{tag}_i}\) 更优，交换 \(\text{tag}_i\) 和 \(j\)；讨论 \(f_j(m)<f_{\text{tag}_i}(m)\)：若 \(f_j(l_i)>f_{\text{tag}_i}(l_i)\) ，则 \(f_j,f_{\text{tag}_i}\) 大小关系交换发生在 \((l_i,m_i)\)，向 \([l_i,m_i]\) 递归插入 \(f_j\)；同理，若 \(f_j(r_i)>f_{\text{tag}_i}(r_i)\) ，则 \(f_j,f_{\text{tag}_i}\) 大小关系交换发生在 \((m_i,r_i)\)，向 \((m_i,r_i]\) 递归插入 \(f_j\)；否则，\(f_j\) 在该区间绝对劣势，舍去。

根据 Condition，两个分支至多进入一个，因此时间复杂度 \(O(\log V)\)，\(V\) 为定义域。

查询 \(x=k\) 的答案，需要找到线段树上从 \([1,V]\) 到 \([k,k]\) 的路径 \(\text{Path}\)，则 \(\text{ans}=\max\limits_{i\in\text{Path}} f_{\text{tag}_i}(k)\)；时间复杂度 \(O(\log V)\).