ST表 5
-
【题解】求m区间内的最值(ST表实现)
求m区间内的最小值题目描述一个含有 nnn 项的数列,求出每一项前的 mmm 个数到它这个区间内的最小值。若前面的数不足 mmm 项则从第 111 个数开始,若前面没有数则输出 000。输入格式第一行两个整数,分别表示 nnn,mmm。第二行,nnn 个正整数,为所给定的数列 aia_iai。输出
-
最近公共祖先LCA(倍增思想)
定义最近公共祖先简称LCA(Lowest Common Ancestor)。两个节点的最近公共祖先指的是这两个点的公共祖先中离根最远的那个。
-
ST表算法与代码实现
对于区间最值也就是 RMQ(Range Minimum/Maximum Query)问题,可以使用ST表(稀疏表)的方式进行离线预处理。ST表思想与原理ST表的核心思想是倍增。
-
【题解】gcd区间(ST表)
题目描述给定一行n个正整数a[1]…a[n]。m次询问,每次询问给定一个区间[L,R],输出a[L]…a[R]的最大公因数。输入格式第一行两个整数n,m。第二行n个整数表示a[1]…a[n]。以下m行,每行2个整数表示询问区间的左右端点。保证输入数据合法。输出格式共m行,每行表示一个询问的答案。输入