小知识点

---

Hello_World

---

预处理

一个问题需要对某些值进行多次询问，如果能将询问的时间复杂度下降至 $O(\log n)$ 或者 $O(1)$，则尽量将这个时间复杂度减下来，这就需要预处理，下面来介绍三个简单的预处理姿势。

sort 函数的使用

$sort$ 函数内部实现是快速排序，头文件为 algorithm。其功能是将传入的数组进行快速排序，时间复杂度为 $O(n\log n)$，空间复杂度为 $O(1)$。快排足以应对大多数题目，如果出现卡常数的题目，可以手写基数排序，这里不进行展开。
这里介绍一下几种简单的 $sort$ 函数的用法。

1. 对基本数据类型的数组进行默认排序

sort 函数的默认排序规则是从小到大，如果对基本数据类型数组进行排序，则只要将数组的首地址作为函数的第一个实参，超尾地址作为函数的第二个实参，就可以对数组从第一个参数指向的地址到第二个参数指向的地址之间的元素进行排序。
超尾地址：数组最后一个元素的后一位，例如对于声明为

const int maxn = 100;
int num[maxn];

的整型数组，最后一个元素为

num[maxn - 1];

其超尾地址就是

&num[maxn];

也可以写为

num + maxn;

要对数组所有元素进行排序，sort 函数的调用方式为

sort(num, num + maxn);

如果以

sort(num, num + n);

调用 sort 函数，则对 num 数组的前 $n$ 个元素从小到大排序，示例代码如下：

#include <stdio.h>              // printf 的头文件
#include <algorithm>            // sort 的头文件
using namespace std;            // 命名空间
int main() {
     int num[] = {3, 2, 1, 5, 7};
     sort(num, num + 5);        // 默认从小到大排序
     for(int i = 0; i < 5; ++i) {
           printf("%d ", num[i]);   // 输出排序后的数组
     }
     return 0;
}

2. 对基本数据类型按特定规则排序

sort 函数的另一个重载形式，可以支持第三个参数：比较函数的传入，它会将比较函数应用在快速排序中，当比较函数返回值为 true/非零值时，第一个元素被认为比第二个元素小，当比较函数返回值为 false/$0$ 时，第一个元素被认为大于等于第二个元素，比较函数可以自定义，但是一定要注意：比较函数必须要定义小于号的意义，而不能定义小于等于号的意义。
以下是对 num 整型数组所有元素进行绝对值从小到大排序的比较函数定义与 sort 函数的调用方法示例：

const int maxn = 100;
int num[maxn];
bool cmp(int a, int b) {
    return abs(a) < abs(b);
}
sort(num, num + maxn, cmp);

前缀和

对于大小为 $n$ 的数组，定义

$$sum_j=\sum_{k=1}^{j}a_k\quad(1\leq j\leq n)$$
则
$$\sum_{k=i}^{j}a_k=sum_j-sum_{i-1}\quad (1\leq i\leq j\leq n)$$

代码：

for(int i = 1; i <= n; ++i) {
    sum[i] = sum[i - 1] + num[i];
}

杨辉三角 $C_n^k$

定义1：

$$C_n^k=\frac{n!}{(n-k)!k!}$$
定义2：
$$C_0^0=1\quad\quad C_n^0=C_n^n=1\\ C_n^k=C_{n-1}^{k-1}+C_{n-1}^k\quad\quad(n>1,\quad0<k<n)$$

代码：

C[0][0] = 1;
for(int i = 1; i <= n; ++i) {
    for(int j = 0; j <= i; ++j) {
        if(j == 0 || j == i) {
            C[i][j] = 1;
        } else {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
        printf("C[%d][%d] = %d\n", i, j, C[i][j]);
    }
}

离散化

对于某些数据范围比较大，但是要用数组模拟的题目，第一种方法可以用 map 处理，但是 map 的询问比数组多一个 $O(\log n)$，如果数值相对的大小关系比较重要，而数本身的值并不重要的话，可以用离散化来对数据进行预处理，达到减小空间复杂度和时间复杂度的目的。

例如，将数组

$$a = \{555,422,72,24,24,24,422,54,68,142\}$$
中各个元素的值离散化，得到新数组
$$b=\{7,6,4,1,1,1,6,2,3,5\}$$

代码：

const int maxn = 100;
struct Node {
    int num;
    int Index;
};
bool operator<(const Node &a, const Node &b) {
    return a.num < b.num;
}
int n = 10;
int a[maxn] = {555, 422, 72, 24, 24, 24, 422, 54, 68, 142};
int b[maxn];
Node node[maxn];
for(int i = 0; i < n; ++i) {
    node[i].num = a[i];
    node[i].Index = i;
    printf("%5d", a[i]);
}
printf("\n");
sort(node, node + n);
int cnt = 1;
b[node[0].Index] = cnt;
for(int i = 1; i < n; ++i) {
    if(node[i].num == node[i - 1].num) {
        b[node[i].Index] = cnt;
    } else {
        b[node[i].Index] = ++cnt;
    }
}
for(int i = 0; i < n; ++i) {
    printf("%5d", b[i]);
}
printf("\n");

取模公式

加减法：
加法：$\quad\quad(a+b)\%p=(a\%p+b\%p)\%p$
若 $b<0$：$\quad b=>（b\%p+p）\%p$
减法：$\quad\quad((a-b)\%p+p)\%p=((a\%p–b)\%p+p)\%p$

扩展：若 $a_i\times a_j(1\leq i\leq j\leq n)$ 爆了 long long，但答案需要求出 $\prod_{i=1}^na\%p$的值，应该怎么办？有更快的方法吗？

乘除法：
乘法：$\quad(a*b)\%p=((a\%p)*(b\%p))\%p$
逆元：若 $(a*b)\%p=1$，则 $b$ 是 $a$ 相对于 $p$ 的逆元
$\quad\quad$记为 $a^{-1}=b\quad(\mod p)$
除法：$\quad(a/b)\%p=((a\%p)*b^{-1})\%p$

扩展：
1. 欧拉函数
将对于任意正整数 $a$，在区间 $[1,a)$ 内，与其最大公约数为 $1$ 的整数的个数，定义为 $a$ 的欧拉函数 $\phi(a)$。
对于任意正整数 $a$，$\phi(a)$ 的求法为：

$$\phi(1)=1$$
若
$$a=p_1^{k_1}\times p_2^{k_2}\times\cdots\times p_n^{k_n }\quad\quad(a>1)$$
其欧拉函数
$$\phi(a)=(1-\frac{1}{p_1})\times(1-\frac{1}{p_2})\times\cdots\times(1-\frac{1}{p_n})$$
其中 $p_1,p_2,\cdots,p_n$ 分别为能整除 $a$ 的 $n$ 个不同的质数。
2. 逆元
当且仅当 $\gcd(a,p)=1$ 时，$a^{-1}(\mod p)$ 存在，此时 $a^{-1}=a^{\phi(p)-1}(\mod p)$

二分答案

如果答案满足下面的性质，则可以考虑用二分答案来解决：
1. 答案为整数
2. 答案具有单调性，单调非递增或单调非递减
3. 求最小值的最大值，或者最大值的最小值
4. 验证答案比直接求解答案更容易

二分有两种写法，一种左闭右开，一种左开右闭，即 $[low, high)$ 与 $(low, high]$。
1. 二分的答案满足条件（或 judge 函数返回 true）时，需要查找更大值，这时需要用左闭右开的写法，若采用这种写法，$low$ 应初始化为答案的下界，$high$ 应初始化为答案的上界 $+1$，最后的答案为 $low$。
2. 二分的答案满足条件时，需要查找更小的值，这时需要用左开右闭的写法，若采用这种写法，$low$ 应初始化为答案的下界 $-1$，$high$ 应初始化为答案的上界，则最后的答案为 $high$。

lower_bound 与 upper_bound 实现代码：

int* lower_bound(int *begin, int *end, int num) {
    int low = -1;
    int high = end - begin;
    int mid;
    while(high - low > 1) {
        mid = (low + high) / 2;
        if(begin[mid] >= num) {
            high = mid;
        } else {
            low = mid;
        }
    }
    return begin + high;
}
int* upper_bound(int *begin, int *end, int num) {
    int low = -1;
    int high = end - begin;
    int mid;
    while(high - low > 1) {
        mid = (low + high) / 2;
        if(begin[mid] > num) {
            high = mid;
        } else {
            low = mid;
        }
    }
    return begin + high;
}
const int maxn = 100;
int n = 10;
int a[maxn] = {2, 3, 3, 4, 6, 6, 6, 7, 8, 9};
for(int i = 0; i <= 10; ++i) {
    printf("lower_bound %2d at %2d\n", i, lower_bound(a, a + n, i) - a);
    printf("upper_bound %2d at %2d\n", i, upper_bound(a, a + n, i) - a);
}

并查集

并查集是通过修改祖先节点，判断两个节点的祖先是否相同，来判断两个点是否在同一个连通块的数据结构，其时间复杂度为 $O(1)$。除了初始化 $(Init)$，并查集有两种操作：询问祖先 $(Find)$ 与合并两个节点到同一个连通块中 $(unit)$。
$Init$：将每个点的父节点定义为它自己，$Fa[i]=i$。
$Find$：递归查找节点 $x$ 的父节点，直到找到某个点 $x'$ 的父节点 $Fa[x']=x'$，则节点 $x$ 的祖先节点即 $x'$。
$unit$：将节点 $x$ 与节点 $y$ 合并到同一个联通块中，分别递归查找节点 $x$ 与节点 $y$ 的祖先节点 $f_x$ 与 $f_y$，将 $f_y$ 赋值给 $Fa[f_x]$，使 $f_y$ 成为 $f_x$ 的父节点。

代码：

const int maxn = 10000 + 100;
int fa[maxn];
void Init() {
    for(int i = 0; i < maxn; ++i) {
        fa[i] = i;
    }
}
int Find(int x) {
    return (x == fa[x]? x: fa[x] = Find(fa[x]));
}
void unit(int x, int y) {
    int xx = Find(x);
    int yy = Find(y);
    fa[xx] = yy;
}