本讲主要内容：快速排序，归并排序，高精度，前缀和，差分，双指针，位运算，离散化，区间合并。参考自https://www.summerfire.cn/posts/acwing_1/

快速排序

AcWing-785 快速排序模版题

思路

先确定递归结束条件 l >= r
确定枢轴 l， r， l + r/2
调整范围，设置两个指针从左到右，左指针找大于枢轴，右指针找小于枢轴，然后两者互换
递归处理左右两段
代码
```cpp
include
include
using namespace std;

const int maxn = 1e6+10; int q[maxn]; int n;

void quick_sort(int q[], int l, int r) { //递归结束条件 if(l >= r) return ;

//取分界点并初始化指针
int x = q[(l+r)/2], i = l - 1, j = r + 1;
//调整区间
while(i < j)
{
    /*若有指针遇到了不符合条件的数，则停下来
    等两个指针都遇到了不符合条件的数，且i在j左边，交换他们所指向的数*/
    do i++; while(q[i] < x);
    do j--; while(q[j] > x); 
    if(i < j) swap(q[i], q[j]);
}
//划分子区间递归处理
quick_sort(q, l, j);
quick_sort(q, j + 1, r);

}

int main(void) { scanf(“%d”, &n); for(int i = 0; i < n; i++) scanf(“%d”, &q[i]);

quick_sort(q, 0, n-1);
for(int i = 0; i < n; i++) printf("%d ", q[i]);
return 0;

}

<a name="jkhi8"></a>
### 注意
注意： <br />如果递归条件写为（即j的对称改一下的形式，两种都可以）`quick_sort(q, l, i - 1); quick_sort(q, i, r);`x就不能取q[l]。<br />同理，若写为`quick_sort(q, l, j);quick_sort(q, j + 1, r)`;x不能取q[r]。 <br />否则会不断划分成`(0,n)或(n,0)`，一直递归造成死循环。 <br />另外在取分界点时最好取中点或者随机取，可以避免部分因为取左右边界点，使得快排复杂度退化为`O(n2)`而超时的情况。
---
<a name="BCLEV"></a>
## AcWing-786 第k个数
<a name="IreT8"></a>
### 思路
直接利用上面的快排模版也能AC。但是对于这个题可以进行特别的优化，因为只是为了寻找排序后第K个数，所以在进行一次递归后，可以判定一下，左边的元素个数`（j - l + 1)`是否大于 _k_。如果大于_k_的话，直接递归左边即可，否则只递归右边。这样每次只递归一边，_O(n)。_
<a name="XEZrt"></a>
### 代码
实际上只需要改动部分代码即可
```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e6+10;
int q[maxn];
int quick_sort(int q[], int l, int r, int k)
{
    if(l == r) return q[l];    //第k大的数所在的区间只有一个数，那么这个数就是整个区间第k大的数
    int x = q[(l+r) / 2], i = l - 1, j = r + 1;
    while(i < j)
    {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }
    //如果在左半区间，由于子区间已经有序，那么整个区间第k大的数就在这个区间的前k个元素中
    //反之，在右半区间的位次就是整个区间第k大的数的位置减去左半区间的元素个数
    if(j-l+1 >= k) quick_sort(q, l, j, k);
    else quick_sort(q, j+1, r, k - (j-l+1));
}
int main(void)
{
    int n, k;
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    printf("%d\n", quick_sort(q, 0, n-1, k));
    return 0;
}

注意

这里最需要注意的地方就是，左边的长度。以及如果递归右边，此时第K个数的次序。

归并排序

AcWing-787 归并排序模版题

思路

与快排不同的地方在于，归并排序要先递归处理两端，即先将一端递归到最小粒度，然后开始进行算法的比较和处理。而快排则是直接先进行粗粒度算法的处理，然后再递归向细粒度处理。

划分子区间
递归两端子区间
将该处理的两个子区间进行比较及合并到临时数组（包括收尾工作
把此次处理的临时数组区间存入原数组
代码
```cpp const int maxn = 1e6 + 10; int m[maxn], tmp[maxn];

void merge_sort(int m[], int l, int r) { //递归结束条件 if(l >= r) return ;

//划分子区间
int mid = (l + r) / 2;
//递归处理
merge_sort(m, l, mid);
merge_sort(m, mid + 1, r);
//合并子区间存到临时数组tmp中
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r)
{
    if(m[i] < m[j]) tmp[k++] = m[i++];
    else tmp[k++] = m[j++];
}
//若某子区间还有剩下的，由于已经是有序的，直接接到临时数组tmp后面就行
while(i <= mid) tmp[k++] = m[i++];
while(j <= r) tmp[k++] = m[j++];
//把临时数组中的子区间再存回原数组，合并得到排序后好的序列。
for(i = l, j = 0; i <= r; i++, j++) m[i] = tmp[j];

}

<a name="hs3VG"></a>
### 注意
1. 递归结束条件` l >= r`
1. 归并循环条件 `i <= mid && j <= r`
1. 最后存入原数组时` i <= r`
<a name="TURzo"></a>
## AcWing-788 逆序对的数量
<a name="DkuZd"></a>
### 思路
总体上来说是采用了归并排序的思路。与归并一样，先递归到底。<br />所有的逆序对只有三种情况：<br />![](https://cdn.nlark.com/yuque/0/2021/png/1699458/1619597646787-78a2e2f0-569b-477a-b462-5f3fe2de66a9.png#clientId=u5c79d664-8b54-4&from=paste&height=339&id=udf4c0c7c&margin=%5Bobject%20Object%5D&originHeight=678&originWidth=933&originalType=url&status=done&style=stroke&taskId=u5a31b404-a0ec-4115-ace5-213e5807a16&width=466.5)<br />在左半边、右半边、以及左右两侧各一个。递归到底之后，自然只剩下最后一种情况。<br />左右半边都排好序时，若左边的数`i` 大于右边的数 `j `，则此时_ _`i` 后面的数都比 `j` 大，即左边此时`i` 以及 `_i_`后面的数共`mid-i+1`个数都与数` j` 构成逆序对。<br />则可以设置一个全局变量`res`，每次若左边的一个数大于右边的数，则可以计算此时的逆序对个数。
<a name="p2Cyt"></a>
### 代码
```cpp
#include <iostream>
using namespace std;
const int N = 100010;
int q[N],tmp[N];
long long res; #注意res的大小
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
    {
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else{
            tmp[k++] = q[j++];
            res += mid - i + 1; #核心所在
        }
    }
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r)  tmp[k++] = q[j++];
    for (int i = l, k = 0; i <= r; i++, k++) q[i] = tmp[k];
}
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> q[i];
    merge_sort(q, 0, n-1);
    cout << res;
}

注意

res += mid - i + 1。注意是+=
这里的归并过程编写，由于逆序对的特殊，第一种情况：左边小于右边。必须写为q[i] <= q[j]

算法笔记

AcWing Part1

快速排序

AcWing-785 快速排序模版题

思路

代码

include

include

注意

归并排序

AcWing-787 归并排序模版题

思路

代码

注意