定义函数 \(\Phi(T)\) 为当前树 \(T\) 中不同数的数量，易证明上限为 \(|T|\)。并规定整棵线段树的大小 \(= n\)。
我们再定义一个概念：对于一个线段树节点，如果它对应的区间包含于 \(\min\) 操作的区间 \([l, r]\)，且它的祖先不包含于 \([l, r]\) 那么称其为 “线段树节点区间” 。其实我说的就是普通线段树操作递归结束的那个节点。
对于每一次 \(\min\) 操作，我们最多使 \(\Phi(T)\) 增加 \(\log_2n\)，即任意一个区间 \([l, r]\) 可被分割为的最多“线段树节点区间”数。
不是在找到了包含于 \([l, r]\) 的“线段树节点区间”后，我们还有可能往下面子节点递归吗？接下来递归的过程中，就不可能使 \(\Phi(T)\) 增长了，只可能使其减少。
而递归到对应节点 \(x\) 的 \(\Phi(x) = 1\) 时，递归结束。这意味着对于一个“线段树节点区间”，我们称为 \(T\)，它顶多执行 \(\Phi(T)\) 次的递归。那么对于整棵线段树，它顶多执行 \(\Phi(n)\) 次的递归。
得证了 qwq。