ACWing基础算法模块

ACWing模板链接

基础算法[基础算法](常用代码模板1——基础算法 - AcWing)

数据结构[数据结构](常用代码模板2——数据结构 - AcWing)

搜索与图论[搜索与图论](常用代码模板3——搜索与图论 - AcWing)

数学知识[数学知识](常用代码模板4——数学知识 - AcWing)

AC模板

一.基础算法

1.快速排序

#include<iostream>
using namespace std;
const int N=100010;
int n;
int q[N];
void quick_sort(int q[],int l,int r){
    if(l>=r)return ;
    int i=l-1;
    int j=r+1;
    int x=q[l+r>>1];       //相当于(l+r)/2;

    while(i<j){
        do i++;while(q[i]<x);    //找到左区间中大于x的元素
        do j--;while(q[j]>x);    //找到右区间中小于x的元素
        if(i<j){
            swap(q[i],q[j]);     //将这两个元素交换
        }
    }
   //递归遍历左右区间
    quick_sort(q,l,j);    
    quick_sort(q,j+1,r);
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%d",&q[i]);
    } 
    quick_sort(q,0,n-1);     //此处元素从0开始存的，所以区间这样
                             //如果从有开始存就是(q,1,n);

    for(int i=0;i<n;i++){
        cout<<q[i]<<" ";
    }
    cout<<endl;
    return 0;
}

归并排序 二路合并

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

const int N =100010;
int n;
int q[N];
int ans[N];//辅助数组  

void merge_sort(int q[],int l, int r){
    if(l>=r)return ;
    //1.找分界点
    int mid=l+r>>1;

    //递归左右区间 
    merge_sort(q,l,mid);  merge_sort(q,mid+1,r);

    int k=0;//表示辅助数组中的元素下标
    int i=l;
    int j=mid+1;   //分别表示两区间的起始点 

    while(i<=mid&&j<=r){
        //将较小者放入辅助数组中 
        if(q[i]<=q[j]) ans[k++]=q[i++];
        else ans[k++]=q[j++];
    }

    //将两数组中剩余的部分加入到辅助数组中
     while(i<=mid)  ans[k++]=q[i++];
     while(j<=r) ans[k++]=q[j++];

     //最后要把辅助数组中元素复制回来
      for(i=l,j=0;i<=r;i++,j++) q[i]=ans[j];

}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%d",&q[i]);
    }
    merge_sort(q,0,n-1);

    for(int i=0;i<n;i++){
        printf("%d ",q[i]);
    }

    cout<<endl;
    return 0;

}

二分

这里以数的范围为例（题目链接[数的范围](789. 数的范围 - AcWing题库)），查找一个有序数组中目标值x的所在范围；

二分的思想是：能够将整体根据某种性质分成两个部分，通过使用l=mid和r=mid两个是否加1的模板，对数的范围左或右边界进行缩小和查找。

#include<iostream>
using namespace std;

const int N =100010;
int n,m;
int q[N];
int main() {
    cin>>n>>m;
    for(int i=0; i<n; i++) {
        scanf("%d",&q[i]);
    }

    //m次询问
    while(m--) {
        int x;
        scanf("%d",&x);

        int l=0,r=n-1; //定义边界

        while(l<r) {
            int mid=l+r>>1;    //刚开始不知道要不要加一，r=mid则不用加1
            if(q[mid]>=x) r=mid;  //如果中间值大于目标值，说明去区间在mid左边，缩小右边界
            else l=mid+1;
        }

        //注意：如果不存在目标值，即区间端点值不等于目标值，输出-1 -1"
        if(q[l]!=x) cout<<"-1 -1"<<endl;
        else {    
            cout<<l<<" "; //打印其中一个边界(右边界(根据首先要找的mid范围判断))
            l=0; r=n-1;
            while(l<r) {
                int mid=l+r+1>>1;     //需要加1，l=mid
                if(q[mid]<=x) l=mid;   //中间值小于目标值，说明区间在mid右边，缩小左边界
                else  r=mid-1;
            }
            cout<<l<<endl;  //打印哪个都一样
        }
    }
    return 0;
}

浮点数二分

保证答案一定在区间里面，直到区间非常小时可以当作答案就为端点值；

浮点数二分不需要考虑整除时的取整问题，因此更简单；

这里以开平方根为例 check是判断答案应在区间的函数

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;
}

数的三次方根

题目链接[数的三次方根](790. 数的三次方根 - AcWing题库)

#include<iostream>
using namespace std;
int main(){
    double x;
    cin>>x;
    double l=-10000,r=10000;
    //两边界之差小于1e-8说明最终结果在两数之间，在误差范围之内
    //同时注意题目要求保留多少小数位，要多加两位，如保留6位，则1e-8，保留八位，最后按6位输出
    while(r-l>1e-8)
    {
        //确定mid
        double mid=(l+r)/2;
        if(mid*mid*mid>=x)
        r=mid; //大于等于x，说明mid对应数的三次方大于了目标值，则缩小右边界
        else l=mid;
    }
    printf("%lf\n",l);//l或r都可，两者相差在误差内,而lf默认为6位小数输出，%.4lf则4位小数
    return 0;
}

高精度算法

高精度加法

利用数组对位数过长的数（长度可达到1e6位）进行求和 题目链接[链接](791. 高精度加法 - AcWing题库)

注意存储两个数时用字符串读入，再按逆序拆分（有进位的情况）后对两个数分别存储。

代码如下：

#include <iostream>
#include<vector>
using namespace std;
const int N =1e6+10;

vector<int> add(vector<int> &v,vector<int> &vs) {
    vector<int> ans;
    int t=0; // 保存进位
    for(int i=0; i<v.size()||i<vs.size(); i++) {
        if(i<v.size())  t+=v[i];
        if(i<vs.size()) t+=vs[i];  //t每步将两个数加一起，将个位数保留入组，10位数作为进位 
        ans.push_back(t%10);
        t/=10;
    }

    if(t) ans.push_back(1); //如果还有进位，需要补上
     return ans;
}
void printvec(vector<int> &ans) {
    for(vector<int>::iterator it=ans.end()-1; it!=ans.begin()-1; it--) {
        printf("%d",*it);
    }
    cout<<endl;
}
int main() {
    vector<int> v,vs;
    string a,b;
    cin>>a>>b;
    //位数太多，要用字符串读入
    for(int i=a.size()-1; i>=0; i--) {
        v.push_back(a[i]-'0');
    }
    for(int i=b.size()-1; i>=0; i--) {
        vs.push_back(b[i]-'0');
    }

    vector<int> ans=add(v,vs);
//    for(int i=ans.size()-1;i>=0;i--)
//    printf("%d",ans[i]);
//    
//    cout<<endl;
    printvec(ans);  //倒着输出 

    return 0;
}

高精度减法

将减法过程加个判断，当某个位数相减大于等于0时，直接减并减去上一位的借位，当小于0时需要借1位10，同时需要减去上一位的借位 t

一般是A大于B，如果小于，就反过来减，再加个符号

#include <iostream>
#include<vector>
using namespace std;
const int N =1e6+10;

vector<int> sub(vector<int> &v,vector<int> &vs) {
    vector<int> ans;
    int t=0; // 保存借位
    for(int i=0;i<v.size();i++){    //A一定大于B了 
        t=v[i]-t;
        if(i<vs.size()) t-=vs[i];           //如果B当前位数存在才减去，相当于A-B-t 
        ans.push_back((t+10)%10);           //两者相减小于0，则加10再模10，且t为1,否则为0
        if(t<0) t=1;
        else t=0; 
    }

    //最后如果前导位为0，则需要弹出
    while(ans.size()>1&&ans.back()==0)  ans.pop_back(); 
    return ans;
}

//判断v是不是>=vs 即A>=B 
bool cmp(vector<int> &v,vector<int> &vs){
    if(v.size()!=vs.size()) return v.size()>vs.size();
    for(int i=v.size()-1;i>=0;i--){      //注意我们是倒着存的数，但需要从高位依次判断大小 
        if(v[i]!=vs[i])
            return v[i]>vs[i];    //相同位数下，只要A有一位数大于B的话就说明A较大了
    }
    return true;        //如果都相同，则说明A==B 
} 
void printvec(vector<int> &ans) {
    for(vector<int>::iterator it=ans.end()-1; it!=ans.begin()-1; it--) {
        printf("%d",*it);
    }
    cout<<endl;
}
int main() {
    vector<int> v,vs;
    string a,b;
    cin>>a>>b;
    //位数太多，要用字符串读入
    for(int i=a.size()-1; i>=0; i--) {
        v.push_back(a[i]-'0');
    }
    for(int i=b.size()-1; i>=0; i--) {
        vs.push_back(b[i]-'0');
    }
    if(cmp(v,vs)) {
        vector<int> ans=sub(v,vs);
        printvec(ans); 
    }
    else {
        vector<int> ans=sub(vs,v);
        cout<<"-";    //A小于B时需要加负号 
        printvec(ans);
    }

    return 0;
}

高精度乘法（高精度*低精度）

按照模板背住就行，具体思路就是：从低位开始，每一位与低精度数相乘，将进位记录下来，将进位 %10 放入res，后 t/10作为下一位的进位 ，最后需要扫尾。题目链接[高精度乘法](793. 高精度乘法 - AcWing题库)

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> A;
int a;
vector<int> mul(vector<int> &A,int a){
    vector<int> res;
    int t=0;
    for(int i=0;i<A.size()||t;i++){
        if(i<A.size()) t+=A[i]*a;
        res.push_back(t%10);
        t/=10;
    }
//    while(t){
//        res.push_back(t%10);
//        t/=10;
//    }
    while(res.size()>1&&res.back()==0) res.pop_back();
    return res;
}
int main(){
    string s;
    cin>>s>>a;
    for(int i=s.size()-1;i>=0;i--){
        A.push_back(s[i]-'0');
    }
    vector<int> ans;
    ans=mul(A,a);
    for(int i=ans.size()-1;i>=0;i--){
        printf("%d",ans[i]);
    }
    cout<<endl;
    return 0;
}

高精度除法（高精度/低精度）

高精度除法与其他三种不太相同，是由高位开始进行除的，并且多了一个余数r，最后为了保持一致性，将res翻转了一下，这样在输出的时候也保证了一致（逆序输出）。最后也别忘了消去前导0。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> A;
int a;
vector<int> div(vector<int> &A,int a,int &r){
    vector<int> res;
    r=0;  //存放余数 

    //除法与其他三种运算不同，需要从高位开始运算 
    for(int i=A.size()-1;i>=0;i--){
        r=r*10+A[i];
        res.push_back(r/a);
        r%=a;
    }
    //存放的商的顺序是从高位到低位的，即顺序的，为了统一模板需要倒置一下 
    reverse(res.begin(),res.end());

    //仍然需要将前置0删去 
    while(res.size()>1&&res.back()==0) res.pop_back();
    return res;
}
int main(){
    string s;
    cin>>s>>a;
    for(int i=s.size()-1;i>=0;i--){
        A.push_back(s[i]-'0');
    }
    vector<int> ans;
    int r=0;
    ans=div(A,a,r);
    for(int i=ans.size()-1;i>=0;i--){
        printf("%d",ans[i]);
    }
    cout<<endl<<r;
    cout<<endl;
    return 0;
}

前缀和

一维前缀和

    快速求一个数组中一段区间内的数的和，解决在某些数据范围很大的情况下会超时的问题

    思路：利用公式si=a1+a2+~~ai; 在录入数组时，初始化前缀和数组s，每个位置存放前i个数的和

    实现求和时结果是线性的O(1)

    特殊：s数组第一个位置存放0 从1开始存，因为s[i]=s[i-1]+a[i]; 不会越界

    有时需要注意数据范围，可能需要用long long

公式：

    <S[i] = a[1] + a[2] + … a[i]>
    <a[l] + … + a[r] = S[r] - S[l - 1]>

例：求[l,r]内的数的和，则可以得s[r]-s[l-1] ; [题目链接](795. 前缀和 - AcWing题库)

代码如下：

#include <iostream>
#include<vector>
using namespace std;
const int N =1e5+10;
int n,m;
int q[N];
int s[N];

int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++)
{
    scanf("%d",&q[i]);
    s[i]=s[i-1]+q[i];
}
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",s[r]-s[l-1]);
    }
    return 0;
}

子矩阵的和（二维前缀和）

子矩阵的和也是公式重要，思路是容斥原理吗，即面积的相加相减，最后得到两点之间组成的区域和，录入前缀和数组以及输出区域和配图如下。题目链接[子矩阵的和](796. 子矩阵的和 - AcWing题库)

公式：

    录入：<s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];>

    输出: <s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];>

图一前缀和数组录入：

图二目标区域和输出:

代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

const int N =1010;
int n,m,q;
int a[N][N];
int s[N][N];

int main(){
    cin>>n>>m>>q;
    //读入矩阵，从11开始存 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    //前缀和数组，可以合并这两步，以防万一分开 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
        }
    }
    //q次询问 
    while(q--){
        int x1,y1,x2,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]);
    }

    return 0;
}

差分

一维差分

    就是前缀和的逆运算，即构造数组b，使得原数组a是b数组的前缀和数组。

即：b(n)=a(n)-a(n-1);  如 a2=b1+b2=a1+(a2-a1)=a2;

    目的：让数组中n个子区间[l,r]每个数都加上一个数C，可以用O(n)一个循环，

但是用差分可以实现O(1)。

    过程：bi加上C后，对应的ai也会加上一个C（因为：a2=b1+b2;），且其后面的剩余数也会加上C，

    最后再将br+1减去一个C，这样其后的所有数就相当于不加C，最后根据b数组求原数组即可得到。

    主要是公式：

       <b[l]+=c; b[r+1]-=c;>

大佬的总结：

最后代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
const int N =100010;
int a[N],b[N];
int n,m;

void insert(int l,int r,int c) {
    b[l]+=c;
    b[r+1]-=c;
}

int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        scanf("%d",&a[i]);
        insert(i,i,a[i]);     //看作数组是空的，然后在每个单位区间上加上了一个a[i]
    }
    while(m--) {
        int l,r,c;
        scanf("%d%d%d",&l,&r,&c);
        insert(l,r,c);
    }
    for(int i=1; i<=n; i++) {
//        b[i]+=b[i-1];           //直接用b[i]作为还原后的前缀和数组 
        a[i]=a[i-1]+b[i];      //得到加过的前缀和数组，这样更容易理解，因为a数组是b的前缀和数组 
    }
    for(int i=1;i<=n;i++) printf("%d ",a[i]);    //如果用b[i]存储前缀和数组，那就输出b[i] 
    return 0;
}

二维差分

与一维差分差不多，都是容斥原理，主要是公式的应用

[子矩阵差分](798. 差分矩阵 - AcWing题库)

公式如下：

    <**b[x1][y1]+=c;**>

    <**b[x2+1][y1]-=c;**>

    <**b[x1][y2+1]-=c;**>

    <**b[x2+1][y2+1]+=c;**>

最后由b数组按前缀和公式求出答案数组即可，此处用差分数组b代替前缀和数组

代码如下：

#include<iostream>
using namespace std;
const int N =1010;

int n,m,q;
int a[N][N];
int b[N][N];

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

    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            insert(i,j,i,j,a[i][j]);

    while(q--) {
        int x1,y1,x2,y2,c;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
        insert(x1,y1,x2,y2,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];

    for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
              printf("%d ",b[i][j]);
            printf("\n");
        }

    return 0;
}

双指针

核心思想：根据某种性质，将双层循环O(n^2)优化为 O(n);

背双指针模板，根据题目要求改写check。

    (check不一定是函数，可以是某个判断条件)

for(int i=0,j=0;i<n;i++){
   while(j < i && check(i,j) j++;
    //根据题目确定
}

换行输出单词

例：给定一个由一个空格隔开的几个单词组成的字符串，请换行输出每个单词。

运用双指针算法，可以将两层循环得到单词后的空格的操作时间复杂度缩小为O(n)

代码如下：

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int N =10010;
//将几个相隔一个空格的单词，分别换行输出 
int main() {
    char str[1000];
    gets(str);
    int len=strlen(str);  //得到字符串数组的长度  <string.h>

    for(int i=0;i<len;i++){
        int j=i; 
        while(j<len&&str[j]!=' ') j++;     //如果j指向的不是空格，则继续后移，等遇到空格后输出i到j的这一段即可 
        //输出当前区间的单词 
        for(int k=i;k<j;k++){
            cout<<str[k];
        }
        puts("");
        //
        i=j;  //将i指向j所指的当前空格，随后循环结束一次i++即可进行下一个单词的获取 
    }
    return 0;
}

最长连续不重复子区间

做双指针的思路，先像一个双层循环的暴力做法，再通过双指针优化。

[题目链接](799. 最长连续不重复子序列 - AcWing题库)

朴素做法：
for(int i=0;i<n;i++){
//每次j从头开始判断i，j区间是否满足不重复条件
    for(int j=0;j<=i;j++){
        if(check(i,j))      //不完整
    {
    res=max(res,i-j+1);  //子区间长度 
    }
  }
}

双指针代码优化如下：

其中while部分的删去思路：

    //如果当i所指的元素个数大于1时，则当前区间不满足条件，则需要将区间中从第一个数开始进行删除(实际上是减去出现次数，因为没说是有序数组啊，所以要依次删去，直到区间没有重复元素了，i 再往后继续走)，反之如果不重复，i则可以一直往后走，然后更新一下当前的最大长度不重复子区间长度。

#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
const int N =100010;
int n;
int a[N],s[N];
//s[N]用于判断当前i，j区间是否有重复元素
int res;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0,j=0;i<n;i++){
        s[a[i]]++; //i后移过程中不断更新当前数字的个数
        while(s[a[i]]>1){
            s[a[j]]--;
            j++;   
        }
        //更新区间长度
        res=max(res,i-j+1);
    }
    cout<<res<<endl;
    return 0;
}

数组元素目标和

[数组元素目标和](800. 数组元素的目标和 - AcWing题库)

目的是求两个有序数组中哪两个数的和为目标值x，输出两个下标。

以传统的双层循环进行判断没问题，但是O(n^2)，对于数据量过大会超限，所以用双指针进行优化，和纯暴力的O(n^2^)算法的区别就在于j指针不会回退 ，这样就节省了时间和内存。

记录：第一次提交爆了，换long long 还是爆，确实没想到 j 指针回溯的问题，实际上KMP算法也是 j 不回溯的优化，所以将 j 指针从后往前依次判断即可快速得到两下标，而且 j 不用回溯.

tips： 多画过程就好理解了

            注意上面加粗的 j 指针不会回溯

代码如下：

#include<iostream>
using namespace std;
const int N =100010;
typedef long long LL;
int n,m,x;
int a[N],b[N];

int main(){
    cin>>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]);

    for(int i=0,j=m-1;i<n;i++){          //双指针移动过程可以画一画，很好理解    
       while(j>=0&&(a[i]+b[j])>x) j--;
        //这样的j就可以移动到第二个数组中能与第一个数组中某元素和为x的元素，
        //随后i往后移，由于有序数组，便可以找到两个元素
        if(j>=0&&(a[i]+b[j])==x) cout<<i<<" "<<j<<endl;    
    }

    return 0;
}
/*
第一次提交：wa    好像是int爆了,不清楚哎
 //每次遍历完第二个数组后，j要从第一个位置重新开始匹配 和双层循环没区别了
*/

判断子序列

判断a数组是不是b数组的子序列，并不是连续的子序列，但是需要满足原顺序相同

如1，3，5 是1，2，3，4，5的子序列，其中数组元素可以为重复的

    刚开始试了下，用双指针，移动的话感觉没问题，样例能过几个，原因有两个：

1.当是重复元素时，我的 j 指针由于是a[i]!=b[j]时才移动，如果a中有重复的话，j就一直不动了，然后当a数组的指针 i 走完，j还是没动（a数组全相同的情况下），所以一定还是输出Yes。解决方法，就算想同了 j 也后移一个，这样可以防止重复元素时的错误，并且可以少一次while判断。

2.当b数组是逆序时，即1,3,5对应5,4,3,2,1；这时候 j 指针由于一直不等于 i 指向的元素1，直到 j 指向第五个元素5时，j停止移动，i++，然后a中元素肯定不可能与j指向元素相同了，j就++，此时j>m-1(元素从0开始存的话),while就一直不执行了，结果输出的不对。

根据2中的错误，可以在移动完j后（while结束），判断此时j是不是大于m-1，是的话就输出No然后ret，如果不是，那就再次j++，开始找下一个相同元素，只要j不越界就说明可以找到与 i 相同的元素，for循环外层输出Yes即可。

当然，可以记录相同元素的个数，如果等于a的长度，也说明是子序列

代码给出第二种,但是这个人是 j 作为外层循环，而判断条件是a[i]==b[j]时移动 i 而不是 j，循环结束后i到头了，说明匹配成功

代码如下：

#include<iostream>
using namespace std;
const int N =1e5+10;
int n,m;
int a[N],b[N];

int main(){
  cin>>n>>m;
  for(int i=0;i<n;i++) scanf("%d",&a[i]);
  for(int i=0;i<m;i++) scanf("%d",&b[i]);
int cnt=0;
  for(int i=0,j=0;i<n;i++)
{
    while(j<m&&a[i]!=b[j]) j++;

    if(j>m-1) {
        cout<<"No"<<endl;
        return 0;
    }
    j++;        //很重要，用来跳过重复元素
}
  cout<<"Yes"<<endl;
  return 0;
}


//第二种
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n; i++) scanf("%d",&a[i]);
    for(int j = 0;j < m; j++) scanf("%d",&b[j]);

    int i = 0;
    for(int j = 0;j < m; j++)
    {
        if(i < n&&a[i] == b[j])  i++;
    }
    if(i == n) puts("Yes");
    else puts("No");
    return 0;
}

位运算

两个常用的位运算你操作

1. n>>k&1 得到n的二进制数的第k位是多少，注意此处的位次是由最右边开始往左边计数，从0开始 即：0101 对应序号3,2,1,0位, 而&1是得到最后一位，则完成上述操作

   例：

   int n=10;
   for(int k=3;k>=0;k--) cout<<(n>>k&1);  得到10的二进制

2. lowbit(x) 操作：返回x的最后一位 1 以及 它后面的数

   如：x=1010 lowbit(x)返回 10

   x=10100 返回100

   注意lowbit并非是一个内置函数，其内部实现为x&(~x+1) 或 x&-x ;

   int lowbit(int x){
       return x &-x;
   }

   int x=10;
   x-=lowbit(x); //二进制减去最后一个1以及以后的数，得到10（2进制）

代码如下：

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int N =100010;
int n;
int lwbit(int x) {
    return x&-x;
}
int main() {
    cin>>n;
    while(n--) {
        int x;
        cin>>x;
        int ans=0;
        while(x) {
            x-=lowbit(x);     //每次删去最后一个1 
            ans++;
        }
        cout<<ans<<" ";
    }
    return 0;
}

离散化

特指整数的离散化。

离散化的含义：10^5个大小在(0–10^9)范围内的数，有些时候需要用这些数作为下标，就需要开辟很大的数组空间，所以进行映射使序列进行重新连续，大大减少空间浪费和效率，这个映射的过程就是离散化。

    解决离散化的两个主要问题：

1.数组a[]中可能有重复元素，如何进行映射呢 （需要进行去重操作，使用库函数unique……）

vector<int> v;
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());

unique函数返回的尾地址，到end()迭代器之间的区间erase即可

    关于unique函数

该函数的作用是“去除”容器或者数组中相邻元素的重复出现的元素
(1) 这里的去除并非真正意义的erase，而是将重复的元素放到容器的末尾，返回值是去重之后的尾地址（迭代器）。
(2) unique针对的是相邻元素，所以对于顺序顺序错乱的数组成员，或者容器成员，需要先进行排序，可以调用std::sort()函数

2.如何算出各个元素对应的离散值（使用二分）

int find(int x){        //查找x所在位置O(nlogn)
    int l=0,r=v.size()-1;
    while(l<r){
        int mid=l+r>>1;
        if(v[mid]>=x) r=mid;
        else l=mid+1;
  }
    return r+1;  
    1.如果加1说明映射到1，2，3，4，……
    2.如果不加说明映射到0，1，2，3，……
}

题目[链接](802. 区间和 - AcWing题库) ：

    假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。

现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。

接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。

    其中各个数据的范围为： 由x，l，r可以看出需要离散化

分析：需要对x以及l，r都进行离散化，因为它们范围太大了，映射后可以对$a[k]+=c$,其中k为x映射后的下标，随后求出离散化后的 l，r，对在$[kl,kr]$ 区间内的k进行求和即可。求和可以用前缀和进行快速计算。

代码如下：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N =3e5+10;  //n+2m个下标会被用到，因此需要开300010
#define endl '\n'

int n,m;
vector<int> v; //存放所有需要离散化的下标x,l,r
int a[N];
int s[N];//前缀和数组
vector<pair<int,int>> add,que;     //add存放n次在x位置添加的元素值与该位置
                                   //que存放待求和的l，r
//求离散化后的结果k
int find(int x) {
    int l=0,r=v.size()-1;
    while(l<r) {
        int mid=l+r>>1;
        if(v[mid]>=x) r=mid;
        else l=mid+1;
    }
    return r+1;  //映射为1，2，3，4……  映射到1因为前缀和求解从1开始较方便
}

int main() {
    cin>>n>>m;
    for(int i=0; i<n; i++) {
        int x,c;
        scanf("%d%d",&x,&c);
        add.push_back({x,c});    //加
        v.push_back(x); //待离散化下标
    }
    for(int i=0; i<m; i++) {
        int l,r;
        scanf("%d%d",&l,&r);
        que.push_back({l,r});   //求
        v.push_back(l);
        v.push_back(r);  //待处理下标
    }
    //去重
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());

    for(pair<int,int> c:add) {
        int x=find(c.first); //离散化添加的下标
        a[x]+=c.second;  //对应位置加上c
    }

    //预处理前缀和数组 ,经上一步操作，已经将对应的映射位置添加好元素
    for(int i=1; i<=v.size(); i++) {    //去重后的v的长度已经是现存元素的个数了
        s[i]=s[i-1]+a[i];
    }

    //求解区间和
    for(pair<int,int> c:que) {
        int l=find(c.first);
        int r=find(c.second);
        cout<<s[r]-s[l-1]<<endl;  //得到映射后的l到r的元素区间和
    }

    return 0;
}

区间合并

[区间合并](803. 区间合并 - AcWing题库)

给定 n 个区间 [li,ri]，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。

        类似贪心的做法（贪心专题中的区间分组，覆盖，选点等问题）

1.步骤 将区间按左端点进行排序 (可以重载运算operator或者写仿函数)

2.排序后可能的情况

第一种：包含，区间端点值st，ed不变

第二种：有交集，ed 更新为该区间的右端点

第三种：无交集，将之前的区间ans++。目标区间更新成这个无交集的区间。重复操作。

根据每种情况，更新st和ed ，并在第三种情况下加入答案数组{st,ed};

实现代码如下：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N =100010;
int n;
vector<pair<int,int>> v;

void merge(vector<pair<int,int>> &v){
    vector<pair<int,int>> res;
    //sort默认按pair的first值进行升序排序
    sort(v.begin(),v.end());

    int st=-2e9,ed=-2e9;            //包括最大区间的范围
    //遍历每个区间
    for(pair<int,int> c:v){
        if(ed<c.first){           //第三种情况
            if(st!=-2e9) res.push_back({st,ed});  //不包括初始的超长区间

            st=c.first; ed=c.second;  //更新待处理区间为当前区间
        }else {
            //区间有交集的情况,取并集 （包含关系或相重合关系，取两区间的右端点最大值即可）
            ed=max(ed,c.second);  
        }
    }

    //特判,最后一个区间并没有小于的左端点，因此不会加入到res中，需要在数组不为空的情况下加一个区间
    if(st!=-2e9) res.push_back({st,ed});

    v=res; //更新数组
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        v.push_back({l,r});
    }

    merge(v);
    cout<<v.size()<<endl;  //区间合并后被更新了
    return 0;
}

另一个大佬写的带注释代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std ;
typedef pair<int,int> pii ;
vector<pii> nums,res ;
int main()
{
    int st=-2e9,ed=-2e9 ;                           //ed代表区间结尾，st代表区间开头
    int n ;
    scanf("%d",&n) ; 
    while(n--)
    {
        int l,r ; 
        scanf("%d%d",&l,&r) ;
        nums.push_back({l,r}) ;
    }
    sort(nums.begin(),nums.end()) ;                 //按左端点排序
    for(auto num:nums)                   
    {
        if(ed<num.first)                            //情况1：两个区间无法合并
        {
            if(ed!=-2e9) res.push_back({st,ed}) ;   //区间1放进res数组
            st=num.first,ed=num.second ;            //维护区间2
        }
        //情况2：两个区间可以合并，且区间1不包含区间2，区间2不包含区间1
        else if(ed<num.second)  
            ed=num.second ;                         //区间合并
    }  
    //(实际上也有情况3：区间1包含区间2，此时不需要任何操作，可以省略)

    //注：排过序之后，不可能有区间2包含区间1

    res.push_back({st,ed});

    //考虑循环结束时的st,ed变量，此时的st,ed变量不需要继续维护，只需要放进res数组即可。
    //因为这是最后的一个序列，所以不可能继续进行合并。

    /*
    for(auto r:res)
        printf("%d %d\n",r.first,r.second) ;
    puts("") ;
    */

    //(把上面的注释去掉，可以在调试时用)

    printf("%d",res.size()) ;           //输出答案
    return 0 ;
}

第一部分就到此结束了……

STL

C++ STL简介
vector, 变长数组，倍增的思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算，按字典序

pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string，字符串
size()/length() 返回字符串长度
empty()
clear()
substr(起始下标，(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址

queue, 队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素

priority_queue, 优先队列，默认是大根堆
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector, greater> q;

stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素

deque, 双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
size()
empty()
clear()
begin()/end()
++, – 返回前驱和后继，时间复杂度 O(logn)

set/multiset
    insert()  插入一个数
    find()  查找一个数
    count()  返回某一个数的个数
    erase()
        (1) 输入是一个数x，删除所有x   O(k + logn)
        (2) 输入一个迭代器，删除这个迭代器
    lower_bound()/upper_bound()
        lower_bound(x)  返回大于等于x的最小的数的迭代器
        upper_bound(x)  返回大于x的最小的数的迭代器
map/multimap
    insert()  插入的数是一个pair
    erase()  输入的参数是pair或者迭代器
    find()
    []  注意multimap不支持此操作。 时间复杂度是 O(logn)
    lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似，增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()， 迭代器的++，–

bitset, 圧位
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]

count()  返回有多少个1

any()  判断是否至少有一个1
none()  判断是否全为0

set()  把所有位置成1
set(k, v)  将第k位变成v
reset()  把所有位变成0
flip()  等价于~
flip(k) 把第k位取反

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