1，快速排序
1）确定数组分界值x，可以是边界点、中点或者随机
2）调整区间，使第一个区间都小于x，第二个区间都大于x
3）递归处理左右两端区间
void q_sort(int q[], int l, int r) {
if (l >= r) return;
//x为数组中点值，而不是下标
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j) {
while (q[++i] < x);
while (q[--j] > x);
if (i < j) swap(q[i], q[j]);
}
q_sort(q, l, j);
q_sort(q, j + 1, r);
}
2，归并排序
1）确定分界点下标为中点
2）递归排序左右两区间
3）采用双指针，用额外数组t存储，每次存储较小的数
4）将t数组的值复制到原数组
void meger_sort(int q[], int l, int r) {
if (l >= r) return;
//mid是中点下标
int mid = l + r >> 1;
//先归并左右区间
meger_sort(q, l, mid);
meger_sort(q, mid + 1, r);
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (q[i] < q[j]) t[k++] = q[i++];
else t[k++] = q[j++];
}
while (i <= mid) t[k++] = q[i++];
while (j <= r) t[k++] = q[j++];
for (int i = l, k = 0; i <= r;) q[i++] = t[k++];
}
3，整数二分
1）当将区间[l, r]划分成[l, mid]和[mid + 1, r]时， 其更新操作是r = mid或者l = mid + 1
//r = mid的情况
int l = 0, r = n - 1;
while(l < r) {
int mid = l + (r - l >> 1);
if(check) r = mid;
else l = mid + 1;
}
1）当将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid
2）这里mid = l + (r - l + 2 >> 1)，是因为整数除法是向下取整，后面更新的时候有l = mid,
如果mid向下取整后为l，则会陷入死循环
//l = mid 的情况
int l = 0, r = n - 1;
while(l < r) {
int mid = l + (r - l + 2 >> 1);
if(check) l = mid;
else r = mid - 1;
}
4，浮点数二分
由于浮点数没有取整的情况，所以不用考虑+1, l和r也直接等于mid即可
double l = 0, r = n - 1;
while(l < r) {
int mid = l + (r - l) / 2;
if(check) l = mid;
else r = mid;
}
5，高精度
高精度主要是对c++语言而言，比如两个1e6相加减，一个数的长度为1e6和一个数为1e9相乘除
主要是将字符串存储到vector中，然后再进行按每一位的算术运算
加法
vector<int> add(vector<int> A, vector<int> B) {
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || i < B.size() || t; i++) {
//t为进位
if (i < A.size()) t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
return C;
}
减法
vector<int> sub(vector<int> A, vector<int> B) {
vector<int> C;
for (int i = 0, t = 0; i < A.size(); i++) {
//首先减掉借位
t = A[i] - t;
//看B处还有没有对应的数值
if (i < B.size()) t -= B[i];
C.push_back((t + 10) % 10);
//看有无借位
t = t < 0 ? 1 : 0;
}
//去掉前导0
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
乘法
vector<int> mul(vector<int> A, int b) {
vector<int> C;
for (int i = 0, t = 0; i < A.size() || t; i++) {
//每一位依次乘以b
if (i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
//如果b等于0，只取最后一位0
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
除法
vector<int> div(vector<int> &A, int &b, int &r) {
vector<int> C;
r = 0;
//除法从高位开始
for (int i = A.size() - 1; i >= 0; i--) {
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
6，前缀和
//一般下标从1开始
//s数组即为a数组的前缀和
for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
//a[l] + ... + a[r] = s[r] - s[l - 1]
7，差分
//在区间[l, r]上加上c
void insert(int l, int r, int c) {
b[l] += c;
b[r + 1] -= c;
}
//b是a的差分数组，a是b的前缀和
for (int i = 1; i <= n; i++) insert(i, i, a[i]);
//求b的前缀和即为a
for (int i = 1; i <= n; i++) b[i] += b[i - 1];
8，双指针
前面的快速排序、归并排序其实都是一种双指针算法
双指针算法包括：两个指针分别指向两个不同的序列；两个指针指向一个序列（比较常见）
一般双指针算法都会有以下形式：
for(int i = 0, j = 0; i < n; i++){
while(j < i && check(i, j)) j++;
//这里的check函数表示i，j满足某种性质
//每道题目的具体逻辑
}
9，位运算
求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n
10，离散化
离散化主要用于对于值域很大，而数目很少的数组，将这样的数组映射到一个值域也差不多的数组中
vector <int> alls;//存储所有待离散化的值
sort(alls.begin(), alls.end());//将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());//去掉重复元素
//二分求出x对应的离散化的值
int find(int x){
//找到第一个大于等于x的位置
int l = 0, r = alls.size() - 1;
while(l < r){
int mid = (l + r) >> 1;
if(alls[mid] >= x) r = mid;
else l = mid+1;
}
return r + 1;//映射到1,2...n;如果不加1是从0开始映射
}
11，区间合并
区间合并是指多个有交集的区间合并成一个区间，实际采用的是贪心算法
1）按区间左端点排序
2）扫描整个区间，将有交集的区间进行合并
如何合并?
- 假设每个区间为[l, r]
- 如果前一个区间是下一个区间的子集，则第一个区间左右端点不变
- 如果前一个区间和下一个区间有交集，则 r 更新为第二的区间的 r
- 如果前一个区间和下一个区间无交集，则前一个区间左右端点不变，找到一个无法合并的区间，并把下一个区间作为当前区间
vector<PII> segs, res;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
segs.push_back({l, r});
}
//对区间进行排序
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs) {
//如果ed小于当前区间的起点
if (ed < seg.first) {
//如果st不是初始值，加入答案
if (st != -2e9) res.push_back({st, ed});
//更新st和ed
st = seg.first;
ed = seg.second;
}
//否则有交集，ed取最大值
else ed = max(ed, seg.second);
}
//把最后一个区间加入答案
if (st != -2e9) res.push_back({st, ed});
cout << res.size() << endl;
