wrnxrxsb的博客

ST表SparseTable稀疏表是一种用于高效处理区间查询的数据结构，主要用于解决可重复贡献问题，如区间最大值、最小值、最大公约数等。ST表的核心思想是利用倍增的思想，通过预处理来快速计算出各个区间的最值。

一个问题的求解过程需一系列的计算，在已知条件和所求问题之间总有着某种关系，在计算时，如果可以找到前后过程中的数量关系（即递推式）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干的简单运算。这题是一道经典的递推题。我们设想，当从顶层沿某条路径走到第i层向第i+1层前进时，我们的选择一定是沿其下两条路径中最大数字和的方向前进的，为此，我们可以采用倒推的手法，设。一个人一开始在 N x M 的格子图的左上角，他每一步只能向下或向右走到相邻的格子，问他走到右下角有多少种不同的走法？

为了解决动态区间RMQ（最值问题）发明的一种能够快速修改和查询的数据结构。

个人站队为例，从第一个人开始，依次比较相邻的两个人是否逆序对，（高的在前，矮的在后），若逆序便交换两人，也就是第一个人与第二个人相比较，若逆序便交换两人，第二个人和第三个人比较，若逆序便交换两人，……于是，我们可以定义一个布尔变量，判断是否有交换，如果没有交换，说明排序已经完成，进而减少几趟排序。接着，原来n个人的排序问题，就转变成了n-1个人的排序，第二轮排序与第一轮很相似，只不过排序直到直到第n-2个人与第n-1个人比较为止。排序过程中，大数慢慢往后，相当于气泡上升，所以叫冒泡排序。

基本思想每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在待排序的数列的最前端，直到所有元素排完。

gcd(a,b)=gcd(a mod b,b)gcd(a,b)=gcd(a \bmod b,b)gcd(a,b)=gcd(amodb,b)因为 gcd(a,b)=gcd(b,a−b)gcd(a,b)=gcd(b,a-b)gcd(a,b)=gcd(b,a−b)，所以可以简化运算为运算。即 gcd(a,b)=gcd(b,a mod b)gcd(a,b)=gcd(b,a \bmod b)gcd(a,b)=gcd(b,amodb)。主要步骤拓展欧几里得算法主要用来求一个形如 ax+by=kax + by = k

好东西，可以求所有一次方程组的解。