快排 O(nlogn) 不稳定

void quick_sort(int q[],int l,int r)
{
    if(l>=r)return ;
    int x= q[(l+r)>>1],i=l-1,j=r+1;//x取中间值，不然会tle
    while(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);//右边排序
}

用快速排序求出第k个数，O(n)

int quick_sort(int q[], int l, int r, int k){
    if(l == r)
        return q[l];
    int x = q[l + r >> 1], 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]);
    }
    int sl = j - l + 1; // 看左边还有多少个数
    if(k <= sl) // k在左边
        return quick_sort(q, l, j, k);
    else // k在右边
        return quick_sort(q, j + 1, r, k - sl);
}

归并排序 O(nlogn) 稳定

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 i=l,j=mid+1,k=l;
    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 x=l;x<=r;x++)
    q[x]=tmp[x];
}

用归并排序求逆序对数量 O（nlogn)

void merge_sort(int q[], int l, int r){
    if(l >= r)
        return 0;
    int mid = l + r >> 1;
    res = merge_sort(q, l, mid) , merge_sort(q, mid + 1, r); // 左边和右边组内的逆序对个数
    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r)
        if(q[i] <= q[j])
            tmp[k ++] = q[i ++];
        else{
            tmp[k ++] = q[j ++];
            res += mid - i + 1;
     // 若q[i] > q[j]，则q[r] >= q[r - 1] >= … >= q[j] > q[i], 
     //也就是说(i, r)， (i, r - 1), …, (i, j) 都能构成逆序对, 
     // 一共有 mid - i + 1 个逆序对
        }
    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];
}

整数二分模板

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;//一定要加1不然可能陷入循环，超时
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

浮点数二分模板

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

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;//注意精度
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

• 高精度四则运算

1.加法

C=A+B,A>=0,B>=0;
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();i++)
    {
        if(i<a.size())
        t+=a[i];
        if(i<b.size())
        t+=b[i];
        c.push_back(t%10);
        t/=10;
    }
    if(t)c.push_back(t);
    return c;
}

2.减法

// C = A - B, 满足 A >= B, A >= 0, B >= 0
bool cmp(vector<int>& A, vector<int>& B)
{
    if(A.size()!=B.size())return A.size()>B.size();
    for(int i=A.size()-1;i>=0;i--)
    {
        if(A[i]!=B[i])return A[i]>B[i];
    }
    return true;
}
vector<int> sub(vector<int>& A, vector<int>& B)
{
    vector<int>C;
    int t=0;
    for(int i=0;i<A.size();i++)
    {
        t=A[i]-t;
        if(i<B.size())t-=B[i];//如果B里面还有数
        C.push_back((t+10)%10);//保证t为正数
        if(t<0)t=1; //如果有借位
        else t=0;
    }
    while(C.size()>1&&C.back()==0)C.pop_back();// 处理前导0
    return C;
}

3.乘法

#define fo(i,a,b) for(int i=a;i<=b;++i)
#define go(i,a,b) for(int i=a;i>=b;--i)
vector<int> mul(vector<int> &A, vector<int> &B)
{
    vector<int> C(A.size() + B.size(), 0);

    fo (i, 0, A.size()-1)
    fo ( j, 0, B.size()-1)
    C[i + j] += A[i] * B[j];

    int t = 0;
    fo ( i,0, C.size()-1)
    {
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();//处理前导0
    return C;
}

4.除法

//高精度除以高精度
bool cmp(vector<int> &A, vector<int> &B){
    if(A.size()!=B.size()) return A.size()>B.size();
    for(int i=A.size()-1;i>=0;i--){
        if(A[i]!=B[i]) return A[i]>B[i]; 
    }
    return true;
}

vector<int> sub(vector<int> &A,vector<int> &B){
    vector<int> C;
    int t=0;
    for(int i=0;i<A.size()||t;i++){
        t = A[i] - t;
        if(i<B.size()) t -= B[i];
        C.push_back((t+10)%10);
        if(t<0) t = 1;
        else t = 0;
    }
    while(C.size()>1&&C.back()==0) C.pop_back();
    return C;
}

vector<int> div(vector<int> &A, vector<int> &B, vector<int> &r){
    vector<int> C;
    int j = B.size();
    r.assign(A.end()-j,A.end());
    while(j<=A.size()){
        int k=0;
        while(cmp(r,B)){
            vector<int> s = sub(r,B);
            r.clear();
            r.assign(s.begin(),s.end());
            k++;
        }
        C.push_back(k);
        if(j<A.size()) r.insert(r.begin(),A[A.size()-j-1]);
        if(r.size()>1&&r.back()==0) r.pop_back();
        j++;
    }
    reverse(C.begin(),C.end());
    while(C.size()>1&&C.back()==0) C.pop_back();
    return C;
}

//高精度除以低精度
// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int>& A, int& b, int& r){ // 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) // 去除前导0
        C.pop_back();
    return C;
}

• 前缀和，差分

1.前缀和
一维：
公式：S[i] = a[1] + a[2] + … a[i]
a[l] + … + a[r] = S[r] - S[l - 1]

//a数组是原始数组,s数组是前缀
void sum()
{
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s[i]=s[i-1]+a[i];//计算a数组的前缀和
    }
    while(m--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",s[r]-s[l-1]);
    }
}

二维前缀和
公式：s[i][j]=a[i-1][j]+a[i][j-1]+a[i][j]-s[i-1][j-1]
a[x1][y1]+…+a[x2][y2]=s[i][j]-s[x1][y2]-s[x2][y1]+s[x1][y1]
二维前缀和模板：

//a数组是原始数组,s数组是前缀和数组
void sum()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
        }
    }
    while(q--)
    {
        int x1,x2,y1,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n",s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);
    }
}

2.差分

可以发现拆分其实表现某段区间内的点的分布，
加上前缀和求得正好是区间点的数值

(1)一维差分
B[i] = a[i] - a[i - 1]
给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c
一维差分模板：

//a是原始数组,b是差分数组
void cf()
{
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]+=a[i];
        b[i+1]-=a[i];
    }
    while(m--)
    {
        int l,r,c;
        scanf("%d%d%d",&l,&r,&c);
        b[l]+=c;
        b[r+1]-=c;
    }
}

(2)二维差分
给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c
二维差分模板：

void cf()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            b[i][j]+=a[i][j];
            b[i+1][j]-=a[i][j];
            b[i][j+1]-=a[i][j];
            b[i+1][j+1]+=a[i][j];
        }
    }
    while(q--)
    {
        int x1,y1,x2,y2,c;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
        b[x1][y1]+=c;
        b[x2+1][y1]-=c;
        b[x1][y2+1]-=c;
        b[x2+1][y2+1]+=c;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
            cout<<b[i][j]<<" ";
        }
        cout<<endl;
    }
}

• 双指针算法

算法思想： 利用问题本身与序列的特性（序列递增性质），使用两个下标i、j对序列进行扫描 （可以同向扫描，也可以反向扫描） ，以较低的复杂度解决问题。(也就是把O(n*n)的时间复杂度化成O(n))
双指针算法模板：

for (int i = 0, j = 0; i < n; i ++ )
    {
        while (j < i && check(i, j)) j ++ ;

        // 具体问题的逻辑
    }
    //常见问题分类：
    //  (1) 对于一个序列，用两个指针维护一段区间
    //  (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

• 位运算

求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n

while(n--)
    {
        scanf("%d",&a);
        ans=0;
        while(a)
        {
            a-=a&-a;
            ans++;
        }
        cout<<ans<<" ";
    }

• 离散化

离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。
离散化模板

vector<int> alls; // 存储所有待离散化的值
    sort(alls.begin(), alls.end()); // 将所有值排序
    alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

    // 二分求出x对应的离散化的值
    int find(int 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,3...(便于做前缀和)
    }

• 区间合并

// **将所有存在交集的区间合并**
    void merge(vector<PII> &segs)
    {
        vector<PII> res;

        sort(segs.begin(), segs.end());

        int st = -2e9, ed = -2e9;
        for (auto seg : segs)
            if (ed < seg.first)
            {
                if (st != -2e9) res.push_back({st, ed});
                st = seg.first, ed = seg.second;
            }
            else ed = max(ed, seg.second);

        if (st != -2e9) res.push_back({st, ed});

        segs = res;
    }