template:base

快排

一般使用c++ stl即可，同时可以使用自定义cmp函数。std::sort在最坏情况下保持O(nlogn)时间复杂度，主流编译器采用introsort（快速排序+堆排序混合算法）实现

bool cmp(int a, int b) {
    return a%3 < b%3; // 按模3余数升序
}
sort(a, a+n, cmp);

归并排序

所谓归并，先递归，再合并。递归的解决两个子数组的排序的子问题，再合并出最终答案。
每一层需要合并n个元素。比如，第一层是合并两个n/2的数组，总共有n个元素。不管层数如何，每一层的合并操作都是O(n)的时间。而总共有logn层，所以总的时间复杂度应该是O(nlogn)

//用于存放合并结果，开一个数组temp
int temp[N];
//解决[l,r]区间内a数组的排序问题
void merge_sort(int a[],int l,int r)
{
    //设置出口
    if(l>=r) return;

    //划分数组
    int mid=l+r>>1;

    //递归到子问题->变区间
    merge_sort(a,l,mid);
    merge_sort(a,mid+1,r);

    //此时子问题已经解决，合并两个有序数组
    int k=0,i=l,j=mid+1;
    //同时遍历两个有序数组，依次把小元素填入temp中
    while(i<=mid&&j<=r)
    {
        if(a[i]<a[j]) temp[k++]=a[i++];
        else temp[k++]=a[j++];
    }

    //哪个数组还有剩余，直接填入temp
    while(i<=mid) temp[k++]=a[i++];
    while(j<=r) temp[k++]=a[j++];

    //此时temp存储了[l,r]区间内a数组的排序结果，填回a数组的[l,r]区间即可
    for(int i=0,j=l;j<=r;i++,j++) a[j]=temp[i];
}

归并排序的经典应用是求给定数组中数组逆序对的个数

采用归并的思想， 注意到逆序对可以分成三类：

• 两个元素都在左边；
• 两个元素都在右边；
• 两个元素一个在左一个在右；

归的过程依然包含了前两种逆序对
因此我们在并的过程中考虑两个元素一个在左一个在右这一情况贡献的新逆序对即可

注意我们在统计逆序对的过程中要同时进行排序，这样做的好处是保持左右子数组有序的同时，可以快速判断剩余元素的逆序关系:当 a[i] > a[j] 时,逆序对增量= mid − i + 1.

const int N=1e5+10;
int temp[N];
long long merge_sort(int a[],int l,int r)
{
    //设置出口
    if(l>=r) return 0;
    //划分数组
    int mid = (r+l)>>1;

    //递归到子问题，统计子问题的独立逆序对
    long long cnt=merge_sort(a,l,mid)+merge_sort(a,mid+1,r);

    //统计两个子问题的互逆序对
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        //正序，不贡献新的逆序对
        if(a[i]<=a[j]) temp[k++]=a[i++];
        //i,j逆序，则从此序号i开始到mid必然都与j形成逆序对逆序对，共计贡献mid-1+1个逆序对
        else{
            cnt+=mid-i+1;
            temp[k++]=a[j++];
        }
    }
    //剩余处理
    while(i<=mid) temp[k++]=a[i++];
    while(j<=r) temp[k++]=a[j++];
    for(i=0,j=l;j<=r;i++,j++) a[j]=temp[i];
    return cnt;

}

逆序对可以做很多事，比如最少交换次数问题:

超市货架上商品当前排列顺序为 [5,3,2,4,1]（商品ID），目标顺序为 [1,2,3,4,5]。每次只能交换相邻商品，求最小交换次数?

因为每次交换相邻元素最多减少1个逆序对，所以此问题只需要求出逆序对个数即可。

二分

二分法是基于解空间单调性提出的经典算法
二分是重要且朴素的思想，大致分为浮点二分和整数二分问题
浮点二分很好写，不断判断l和r谁更新为mid即可

//求三次方根
double b_search(double n)
{
    double l=-10000,r=10000,mid=0;
    while((r-l)>1e-8)
    {
        double mid =(l+r)/2;
        if(mid*mid*mid>n) r=mid;
        else l=mid;
    }
    return r;
}

整数二分需要考虑边界问题，对应有两种模版在下面写出。笔者认为采用一种名为”自然写法的”编码方式逻辑更清楚。所谓自然写法，意指写好check函数后自然地判断其后跟随的更新法则，根据r = mid还是l = mid,判断下一句是l = mid + 1亦或r = mid − 1,这种逻辑上的必然性是由check函数必须是闭集合的约定带来的。这样做有三个好处。

• 递归结束后必然有l = r = mid
• 两种不同写法都可找到满足题目需求的解，同时使用两种模版可以解决一种区间问题（见其后的例题）
• 只需要记忆:当check后面跟的是l=mid，则前面mid的更新需要+1变为(mid = (l+r+1)>>1)，如此便可以完全防止死循环!

bool check(int x) {/* ... */} 
// 检查x是否满足某种性质(与mid相关联)，这个检查逻辑应该包含我们所需要的逻辑，是一个闭区间。
// 举个例子，如果寻找升序数组中5的位置，那么check应该写为a[mid]>=5或者a[mid]<=5，而不是a[mid]>5或者a[mid]<5

// 这种写法事实上对应:区间[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;
}

考虑一道经典的问题

给定一个按照升序排列的长度为 n的整数数组，以及 q个查询。 对于每个查询，返回一个元素 k的起始位置和终止位置（位置从 0开始计数）。 如果数组中不存在该元素，则返回 -1 -1。

输入格式

第一行包含整数 n 和 q，表示数组长度和询问个数。
第二行包含 n个整数（均在 1∼10000范围内），表示完整数组。
接下来 q 行，每行包含一个整数 k，表示一个询问元素。

输出格式

共 q行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1
一般模版

#include<iostream>
#include<cmath>
using namespace std;
const int N=1e5+10;
int n,q,a[N];
int bl_search(int k)
{
    int l=0,r=n-1;
    while(r>l)
    {
        int mid=r+l>>1;
        if(a[mid]>=k) r=mid;
        else l=mid+1;
    }
    return l;
}
//check写成a[mid]<=k,则区间被分为区间[l, r]被划分成[l, mid-1和[mid, r],为什么呢
    //如果check满足，则mid作为左区间可以保留
    //如果check不满足，则mid作为右区间必然满足，需要-1
    //我们自然地写出了
    /*if(a[mid]>=k) l=mid;
        else r=mid-1; */
int br_search(int k)
{
    int l=0,r=n-1;
    while(r>l)
    {
        int mid = l+r+1>>1;
        if(a[mid]<=k) l=mid;
        else r=mid-1;

    }
    return l;
}
//如何判断谁输出了左右边界？看谁在左右边界的取舍更保守，更准确即可，事实上我们可以发现else后跟的语句是严格的边界判断，check后跟的是正确但未必在边界上的判断
void solve(int k)
{
    int l=bl_search(k);
    if (a[l]!=k) {
        cout<<"-1 -1\n";
        return;
    }
    printf("%d %d\n",bl_search(k),br_search(k));
}
int main()
{
    
    scanf("%d%d",&n,&q);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<q;i++)
    {
        int k;
        scanf("%d",&k);
        solve(k);
    }

}

前缀与差分

不用刻意背，作为一种思路可以写出来，记住要写前缀或者差分的时候，下标从1开始

一维前缀和 —— 模板题 AcWing 795. 前缀和

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

二维前缀和 —— 模板题 AcWing 796. 子矩阵的和

S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

一维差分 —— 模板题 AcWing 797. 差分

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

二维差分 —— 模板题 AcWing 798. 差分矩阵

给以(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

位运算

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

双指针算法

双指针算法的本质是利用了问题的某种单调性，使得两个指针仅有可能单向移动，对大循环搜索进行了优化,将时间复杂度从O(n²)优化至O(n) 我们需要考虑的是，如何移动指针，可以利用上问题的某种单调性。写法的基本框架就是在某一个指针的大循环下写另一个指针的while移动

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

    // 具体问题的逻辑
}

一类问题是两个指针遍历两个区间：
给定两个升序排序的有序数组A和B,以及一个目标值x。

数组下标从 0 开始。

请你求出满足A[i] + B[j] = x的数对(i, j)。
(保证问题只有一个解)

基本思路为:维护两个指针i,j,分别用于正序，倒序遍历a，b。外层大循环递增i，对于当前的i判断a[i]+b[j]与x的关系，当a[i]+b[j])>x时，不断递减j直到a[i]+b[j])<=x,此时判断:若a[i]+b[j])==x则答案已经找到。若a[i]+b[j])<x则说明当下的i没有对应的j组成答案，需要对下一个i进行判断。

问题的单调性在于对于之前的i抛弃的j，新递增出来的i也依然用不上这些j。这是升序数组带来的显然结果。因此我们可以保证，i和j只需要单向移动。

//双指针算法的本质是利用了问题的某种单调性，使得两个指针仅有可能单向移动。
#include<iostream>
using namespace std;
const int N = 1e5+10;
int a[N],b[N],n,m,x;
int main()
{
    scanf("%d%d%d",&n,&m,&x);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<m;i++) scanf("%d",&b[i]);
    int j=m-1;
    for(int i=0;i<n;i++)
    {
        while((a[i]+b[j])>x) j--;
        if((a[i]+b[j])==x) 
        {
            cout<<i<<" "<<j;
            return 0;
        }
        
    }
    return 0;
    
}

另一类问题是用两个指针维护某一个区间，比如经典的求最长不重复子序列的长度问题

基本思路

我们需要维护一个状态数组s[N]表示当前维护的区间里某个数出现了多少次

维护两个指针i,j分别代表当前区间的左右端点。初始i=0,j=0。令j一次一次的往外扩展，每一次扩展都要判断扩展后区间是否有重复，如果有，则令i向前扩展，直到追上j或者把重复的元素排出了当前区间为止。

重复上述操作，循环内不断更新最大数组长度res

本问题中我们使用到的单调性来源于连续不重复这一约定，这致使i,j有且仅有可能单向向左移动。

#include<iostream>
using namespace std;
const int N = 1e5+10;
int n,a[N],s[N]={0};
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    int i=0,res=0;
    for(int j=0;j<n;j++)
    {
        s[a[j]]++;
        if(s[a[j]]>1)
        {
            while(i<j&&s[a[j]]>1)
            {
                s[a[i]]--;
                i++;  
            }
        }
        res=max(res,j-i+1);
    }
    cout<<res;
}

离散化(坐标映射)

离散化的思想是映射，把大数映射到小数，无穷映射到有穷，笔者比较喜欢直接使用c++stl的hash来做

看一道题

假定有一个无限长的数轴，数轴上每个坐标上的数都是0。 现在，我们首先进行n次操作，每次操作将某一位置x上的数加c。 接下来，进行m次询问，每个询问包含两个整数l和r,你需要求出在区间[l, r]之间的所有数的和

输入格式

第一行包含两个整数n和m。 接下来n行，每行包含两个整数x和c。 再接下来m行，每行包含两个整数l和r。 输出格式 共m行，每行输出一个询问中所求的区间内数字和。

解答：

把所有坐标直接存下来？太大，不现实。我们事实上用到的坐标是什么？其实是每一组r,l,x 因此把所有的r,l,x都存到一个数组里面按升序排列好，取数组的脚标为新的坐标并排列好，原来的r，l处赋值为0，x处赋值+=c，求前缀和即可
有了思路，想想我们要开多少vector或者hashmap来存储需要的数据与关系？
unordered_map<int,int> vtoi 记录大坐标与小坐标的映射关系

typedef pair<int,int> pii;
vector<int> alls; 记录用到的所有坐标
vector<pii> query; 记录所有要求的区间和
vector<pii> adds; 记录所有要加c的x

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
int a[N]={0},s[N]={0};
unordered_map<int,int> vtoi;
typedef pair<int,int> pii;
int main()
{
    int n,m;
    cin>>n>>m;
    vector<int> alls;
    vector<pii> query;
    vector<pii> adds;
    for(int i=0;i<n;i++)
    {
        int x,c;
        cin>>x>>c;
        alls.push_back(x);
        adds.push_back({x,c});
    }
    for(int i=0;i<m;i++)
    {
        int l,r;
        cin>>l>>r;
        alls.push_back(l);
        alls.push_back(r);
        query.push_back({l,r});

    }
    //排序并去重
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    //因为要使用前缀和，这里脚标映射为i+1
    for(int i=0;i<alls.size();i++)
    {
        vtoi[alls[i]]=i+1;
    }
    //为有穷坐标赋值
    for(auto add:adds)
    {
        int x = add.first;
        int c = add.second;
        a[vtoi[x]]+=c;
    }
    //求前缀和
    for(int i=1;i<=alls.size();i++)
    {
        s[i]=s[i-1]+a[i];
    }
    //解决问题
    for(auto q:query)
    {
        int l =vtoi[q.first];
        int r =vtoi[q.second];
        cout <<s[r]-s[l-1]<<endl;
    }

}

区间合并

给n个区间，求n个区间合并之后的区间个数？
基本思路，先cin所有区间，利用sort优先左端点排序。 然后定义ed为我们此时维护的区间的末尾，每次如果ed大于a[i].first,则此ai可以合并，更新ed
否则，此ai不可合并，更新ed并ans++

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
typedef pair<int,int> pii;
pii a[N];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) scanf("%d%d",&a[i].first,&a[i].second);
    sort(a,a+n);
    int res=0;
    int l=a[0].first,r=a[0].second;
    for(int i=1;i<n;i++)
    {
        if(a[i].first>r) 
        {
            res++;
            l = a[i].first;
            r = a[i].second;
        }
        r=max(r,a[i].second);
    }
    res++;
    cout<<res;
}