别的笔记暂时不发出来

1 快速排序

(1)【快速排序】普通快速排序

快速排序三步骤：
1.确定分界点，可以取中点
2.调整区间
3.递归处理左右两端

调整区间的方法

搞两个指针 $i$ $j$,将整个区间分为两半，一半所有数都是小于分界点的，一半是大于等于分界点的
两个指针一直移动，直到 $i$ 指针左边的元素 $\leq$ a[i]时停下来，同理j。
到最后满足条件了还是没有相遇，就交换i j.
最后递归处理边界

void sort(int a[],int l,int r){
    if(l>=r)return;
    int i=l-1,j=r+1,x=a[l+r>>1];
    while(i<j){
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j)swap(a[i],a[j]);
    }
    sort(a,l,j);
    sort(a,j+1,r);
}

对应AcWing 785.快速排序

(2)【快速排序】求第 $k$ 小值

先求出来 $i$ ~ $j$,里面元素的个数，如果 $k$ 大于元素，那么递归左边界
否则递归右边界

int ks(int l,int r,int k){
    if(l>=r)return a[r];//因为不是输出，所以返回a[l]和a[r]都行
    int i=l-1,j=r+1,x=a[l+r>>1];
    while(i<j){
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j)swap(a[i],a[j]);
    }
    int SL=j-l+1;
    if(k<=SL)return ks(l,j,k);// 递归左边界
    else return ks(j+1,r,k-SL);//递归右边界
}

对应AcWing 786.第k个数

2 归并排序

(1)【归并排序】普通归并排序

归并排序和快速排序类似，也是基于分治
1.确定分界点mid（平均值）
2.递归排序
3.归并：将第二步完成后，会分成两个有序序列，合并成一个有序序列
其实是双指针算法
归并做法：
搞一个新数组res，两个指针指向第一个元素。因为排好了序。所以第一个元素是最小值。比较一下这两个最小值，最小的就是总共的最小值了。如果第一个指针的数小，第一个元素存进去，第二个指针小，存进第二个指针，如果相等的话存第一个。

void gb(int q[],int l,int r){
    if(l>=r)return;
    int mid=l+r>>1;
    gb(q,l,mid);
    gb(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++];
    }
    while(i<=mid)tmp[k++]=q[i++];
    while(j<=r)tmp[k++]=q[j++];
    for(int i=l,j=0;i<=r;i++,j++)q[i]=tmp[j];
}

(2)【归并排序】逆序对的数量（重要！）

和归并排序一个思想
将逆序对分为三大类：
1.两个数同时出现在左半边
2.两个数同时出现在右半边
3.一个在左半边，一个在右半边
假设归并排序可以将整个区间排好序并且同时可以返回整个区间内部的逆序对个数
逆序对个数是三类之和

做法实现：

1.gb(l,mid)
2.gb(mid+1,r)
3.先求出第二个序列中的第一个数，算出第一个序列里有多少个数大于这个数，假设$s1$个数大于第二个序列的第一个数，并且能构成逆序对的，接着第二个数，第三个数……一直到 $sm$

快速求出 $s1~sm$ 之间逆序对数量

回顾归并的过程
假设第一个序列中的数是 $q_i$, 第二个序列是 $q_j$,如果 $q_i严格大于q_j$ 时，说明后面的数也都大于 $q_j$
求出 $s_j$,就是 $q_i$ 到后面数的个数
个数就是 $mid-i+1$
代码：

LL merge_sort(int q[],int l,int r){
    if(l>=r)return 0;
    int mid=l+r>>1;//右移的优先级小于加号，所以不用加括号
    LL res=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{
            res+=mid-i+1;//套用公式
            tmp[k++]=q[j++];
        }
    //扫尾
    while(i<=mid)tmp[k++]=q[i++];
    while(j<=r)tmp[k++]=q[j++];
    //物归原主
    for(i=l,j=0;i<=r;i++,j++)q[i]=tmp[j];
    return res;
}

3 整数二分

如果有单调性，一定可以二分，没有单调性，也可能也可以二分
二分的本质是边界，给定一个区间，假设在这个区间上定义了某种性质，性质在右半边区间是满足的，左半边区间是不满足的，如果我们能找到这个性质，将整个区间一分为二，二分就可以寻找这个性质的边界。

二分并不是找某个数，而是找到符合条件的最小的数或最大的数。

二分左边界

第一步取中点：mid=(l+r)/2
每次判断一下这个中间值书否满足这个性质if(check(mid))，如果是true，说明mid是满足这个条件的，所以一定是在左半边找，答案在mid到r，最后把[l,r]区间更新成[mid,r]区间（包含mid），l=mid。如果返回false,把[l,r]区间更新成[l,mid-1]区间，答案在l到mid-1

选择模板

先写一个check()函数，想一下check()函数是true或者false如何更新。如果是左半边（l=mid,r=mid-1)就用第一个模板，否则第二个模板

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

作者：yxc
链接：https://www.acwing.com/blog/content/277/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

为什么要加上一

如果l=r-1，l和r之间只相差1的时候，那么mid=l(下取整)，如果check成功了，那么到头来l一直没变，导致死循环
789.数的范围代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],n,q;
int main(){
    scanf("%d%d",&n,&q);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    while(q--){
        int k;
        scanf("%d",&k);
        int l=0,r=n-1;
        while(l<r){
            int mid=l+r>>1;
            if(a[mid]>=k)r=mid;
            else l=mid+1;
        }
        if(a[l]!=k)puts("-1 -1");
        else{
            printf("%d ",l);
            int l=0,r=n-1;
            while(l<r){
                int mid=l+r+1>>1;
                if(a[mid]<=k)l=mid;
                else r=mid-1;
            }
            printf("%d\n",l);
        }
    }
    return 0;
}

4 浮点数二分

浮点数二分简单，就是需要考虑精度问题，看790就知道了

#include<bits/stdc++.h>
using namespace std;
int main()
{
    double x;
    cin>>x;
    double l=-100,r=100;
    while(r-l>=1e-8){
        double mid=(l+r)/2;
        if(mid*mid*mid>=x)r=mid;
        else l=mid;
    }
    printf("%.6f",l);
    return 0;
}