1. 算法基础整合

1. 基础算法

1.1 排序

1.1.1 快速排序

模板：Acwing785 快速排序

题目：将一个长度为 /(n/) 的数组 /(q/) 从小到大排序。

思路：

1. 选取界点 /(x/)，一般为 /(q_{(l+r)/2}/)（/(l,r/) 为排序的左端点和右端点） 或随机选点（效率较高）。

2. 将 /(/le x/) 的数换到左边，将 /(/ge x/) 的数换到右边（主要步骤）。

3. 递归处理 /(x/) 的左右两边。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e5+10;

int q[N];

void qsort(int q[], int l, int r) {
    if (l >= r) //递归边界
        return ;
    
    int i = l-1, j = r+1, x = q[(l+r)/2]; //第1步
    while (i < j) { //第2步
        do i++;
        while (q[i] < x);
        do j--;
        while (q[j] > x);
        if (i < j)
            swap(q[i], q[j]);
    }
    
    qsort(q, l, j), qsort(q, j+1, r); //第3步
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) 
        scanf("%d", &q[i]);
    
    qsort(q, 1, n);
    
    for (int i = 1; i <= n; ++i)
        printf("%d ", q[i]);
    return 0;
}

1.1.2 归并排序

模板：Acwing 787. 归并排序

题目：将一个长度为 /(n/) 的数组 /(q/) 从小到大排序。

思路：

1. 确定分界点 /(x=/dfrac{l+r}{2}/).

2. 递归排序 /(x/) 的左右两边。

3. 将排好序的两边合并（主要步骤）。

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 1e5+10;

int q[N], tmp[N];

void msort(int q[], int l, int r) {
    if (l >= r) //递归边界
        return ;
    
    int mid = l + r >> 1; //步骤1
    msort(q, l, mid), msort(q, mid+1, r); //步骤二
    
    int i = l, j = mid+1, k = 1; //步骤三
    while (i <= mid && j <= r) 
        tmp[k ++] = (q[i] < q[j]) ? q[i ++] : q[j ++];
    while (i <= mid)
        tmp[k ++] = q[i ++];
    while (j <= r)
        tmp[k ++] = q[j ++];
    
    for (int i = l, j = 1; i <= r; ++i, ++j)
        q[i] = tmp[j];
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &q[i]);
    
    msort(q, 1, n);
    
    for (int i = 1; i <= n; ++i)  
        printf("%d ", q[i]);
    return 0;
}

应用：Acwing788. 逆序对的数量

题目：计算一个长度为 /(n/) 的序列 /(q/) 中逆序对的数量（逆序对的定义：若 /(i<j/) 且 /(q_i>q_j/)，则 /((i,j)/) 即为一个逆序对）。

思路：运用归并排序。

设 /(m(l, r)/) 表示 /(q_l/sim q_r/) 中的逆序对数量， /(x=/dfrac{l+r}{2}/). 则 /(m(l,r)=m(l,x)+m(x+1,r)/)/(+/) 横跨两段的逆序对的数量。

/(m(l,x)/) 和 /(m(x+1,r)/) 可以通过递归求出。那么横跨两段的逆序对的数量可以在归并排序的过程中完成。

看看归并排序的核心部分：

int i = l, j = mid+1, k = 1; //这里的mid即上文中的x
    while (i <= mid && j <= r) {
        if (q[i] <= q[j])
            tmp[k ++] = q[i ++];
        else
            tmp[k ++] = q[j ++];
    }
    while (i <= mid)
        tmp[k ++] = q[i ++];
    while (j <= r)
        tmp[k ++] = q[j ++];

再结合逆序对的定义，可知当 /(q_i>q_j/) 时，/((i,j),(i+1,j),…,(x,j)/) 均为逆序对（因为 /(q_l/sim q_x/) 已经排好序了，所以 /(q_x/ge q_{x-1}/ge …/ge q_i>q_j/)）。而 /(i/sim x/) 共有 /(x-i+1/) 个数。所以当 /(q_i/ge q_j/) 时，横跨两段的逆序对数量就增加 /(x-i+1/).

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

#define int long long //注意此题要开long long,仔细都数据范围

const int N = 1e5+10;

int q[N], tmp[N];

int msort(int q[], int l, int r) {
    if (l >= r)
        return 0; //注意,由于函数返回类型变为了int,所以不能直接return,要加上返回值0
    
    int mid = l + r >> 1;
    int ans = msort(q, l, mid) + msort(q, mid+1, r);
    
    int i = l, j = mid+1, k = 1;
    while (i <= mid && j <= r) {
        if (q[i] <= q[j])
            tmp[k ++] = q[i ++];
        else
            tmp[k ++] = q[j ++], ans += mid-i+1;
    }
    while (i <= mid)
        tmp[k ++] = q[i ++];
    while (j <= r)
        tmp[k ++] = q[j ++];
    
    for (int i = l, j = 1; i <= r; ++i, ++j)
        q[i] = tmp[j];
        
    return ans;
}

signed main() {
    int n;
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i) 
        scanf("%lld", &q[i]);
    
    int ans = msort(q, 1, n);
    printf("%lld/n", ans);
    return 0;
}

1.2 二分

1.2.1 整数二分

1.2.2 小数二分