四毛子

神秘科技。

但是感觉其实没有什么本质的优化。因为最后实际上借助计算机能够 处理二进制上的某些信息来去掉复杂度的一个 。

猫树

可爱捏。

对于每个节点，维护左子节点的全部后缀信息，右子节点的全部前缀信息。

补成完全二叉树，lca 恰好是最长公共前缀，也就是 x >> log(x xor y)，因为异或会把相同的地方全部消去而不同的地方全都保留。

适用于区间合并困难但是单点合并轻松的问题。

听群友说这个好像也被称作不交 st 表。这么有道理。

单调栈

感觉先前从来没有人说过这样做的 motivation。

实际上前缀 的单调栈里面存储的是从 向前扫，所有可以 chkmin 的位置。

因为对一个序列，她的后缀最小值是从后向前单调不增的。因而我们仅需维护产生变化的位置，就可还原出这个序列的后缀最小值序列。

并且，后缀最小值发生变化当且仅当在此处产生一个比原最小值更小的值。因而实际上我们能够通过后缀最小值序列获取所有我们想要获取的和后缀相关的最小值信息。

这是很深刻的。

然后有一个很可爱的均摊证明帮助我们动态维护一个单调栈。

rmq

首先对原序列以 为块长分块。

• 对整块，猫树可以帮我们完成 的 rmq。

  然而实际上整块只有 个。因而我们对整块的处理是 的。

  所以当 时，我们能够做到 预处理。

• 对散块，也即要对长度为 的小块支持 rmq。

  考虑可持久化压位单调栈。

  根据前面对于单调栈的理解，一个前缀的单调栈实际上维护的是她后缀最值的变化位置。

  最小值单调不升。因而我们查询 中的最小值时，找出前缀 中大于等于 的最靠前的最值变化位置即可。也即此处单调栈中的最靠前的位置。

  我们只有 个数，将她们压到一个二进制串中。

  每次用位运算去除掉小于 的所有位置，lowbit 就是我们希望获得的位置。

lca

考虑欧拉序。

不加证明地，我们给出结论： 到 的 lca 为欧拉序中最小值所在位置。

然后使用 rmq 就完结撒花啦。