四毛子算法（Method of Four Russians）的一些简单应用
2021-03-17 03:24
标签：区间 简单应用 个数 转化 如何 不同 中间 就是 有一个 与其说四毛子算法（Method of Four Russians）是一种算法不如说它是一种思想，一种（非常规）分块后暴力预处理以此来优化复杂度的思想。 一类经典的问题是「加一减一 ST 表」:就是现在有一个序列，满足其差分序列只有 +1 和 -1，如何快速维护区间最小值？我们的做法是，先按照 \(B=\lceil\frac{\log_2 n}{2}\rceil\) 分块，那么我们现在有 \(\lceil n/B\rceil\) 个块，只要我们能快速维护出块内每个子区间的最小值，就可以用 ST 表在 \(\mathcal{O}(\frac{n}{B}\log\frac{n}{B})=\mathcal{O}(n)\) 的复杂度内完成预处理。那么现在注意到块内的不同可能序列的个数最多只有 \(\mathcal{O}(2^B)=\mathcal{O}(\sqrt n)\) 种，于是可以预处理出每种可能的序列的每个子区间最小值所在位置，这样就可以做到 \(\mathcal{O}(n)-\mathcal{O}(1)\) 查询。 现在来看一个进阶版的：如何 \(\mathcal{O}(n)-\mathcal{O}(1)\) 查询树上两点的 LCA？一个做法是，先求出整棵树的（扩展）欧拉序，也就是不只是在退出一个点的时候记录，而是每次访问一条边就记录两个端点。这样容易证明从一个点的第一个位置到另一个点的第一个位置中间的深度最浅的点就是它俩的 LCA，于是转化为了 RMQ 问题，而注意到这也是一个「加一减一 ST 表」，于是优化到了 \(\mathcal{O}(n)-\mathcal{O}(1)\)。 终极进阶版：如何 \(\mathcal{O}(n)-\mathcal{O}(1)\) 求一个任意序列的 RMQ？先对这个序建出笛卡尔树，于是就转化为了 LCA 问题，这是我们已经会做了的。 四毛子算法（Method of Four Russians）的一些简单应用 标签：区间 简单应用 个数 转化 如何 不同 中间 就是 有一个 原文地址：https://www.cnblogs.com/whx1003/p/13996517.html
上一篇：钉钉二次开发c#发起审批
下一篇：Python获取Excel批注
文章标题：四毛子算法（Method of Four Russians）的一些简单应用
文章链接：http://soscw.com/essay/65122.html