例题 分析 离散化事实上就是当这个数据范围比较大的时候但是能用到的数比较少的时候需要用到的算法。就比如这个题，a_i 和 b_i 的数据范围超大但 n 的数据范围只有 2\times 10^5。这个时候我们可以将其压缩，使得所有内容之间没有空位。 以样例为例，实现如下图：

排列数：A_n^m=\frac{n!}{(n-m)!} 组合数：C_n^m=\frac{n!}{m!(n-m)!} 最小公倍数：lcm[a,b]=\frac{a}{gcd(a,b)}\times b 余数公式（两两互推）： a=kb+r k=\lfloor{\frac{a}{b}}\rfloor r

分块 此文章列出了几种分块的常见用法涉及的模板题目和代码，便于理解和复习分块算法。 数列分块入门 1 【区间加法+单点查询】 题面 题目描述 给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，单点查值。 输入格式 第一行输入一个数字 n。 第二行输入 n 个数字，

逆序对是指在一个数列中，任意两个数满足前面的数大于后面的数，这两个数就构成了一个逆序对。计算逆序对的目的是衡量一个数列“乱序”的程度。 逆序对的定义： 对于一个序列 a_1, a_2, ..., a_n ，如果存在 i < j ，并且 a_i > a_j ，那么 (a_i, a_j) 就称为一个逆序

战功统计 1 时间限制： 2 秒 内存限制： 128M 题目描述 小可将军统率着n个士兵，士兵分别编号为1~n。已知他们现在的战功 a[i]，要为他们统计接下来的战功，战功可以透支使用，即战功可能为负数 杀敌可以增加战功，且战功可以兑换物资，所有战功会有增有减，统称为战功的变化 将军经常爱拿某一段编

亲戚 时间限制：1秒 内存限制：128M 题目描述 若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。 规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

计数排序和桶排序是两种不同的排序算法，但它们有一些相似之处。以下是对它们的详细解释： 计数排序 (Counting Sort) 计数排序是一种非比较排序算法，适用于对一定范围内的整数排序。其基本思想是利用数组下标作为值来记录每个数出现的次数，然后通过这些计数值直接构建有序的输出数组。 计数排序步骤：