/************************************************/ 
//模板1 归并排序
 //#include<bits/stdc++.h>
//using namespace std;
//int n;
//const int N=1000010;
//int q[N];
//////1.确定中点
////2.递归排序左边右边 
////3.归并-合二为一
int tmp[N]; 
void merge_sort(int q[],int l,int r){
    if(l>=r)
        return;
    int mid=(l+r)/2;
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);
    int=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];

}
int main()
{
    scanf("%d",&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]);
    }
    return 0;
}



/************************************************/ 
//第二节课 二分
//整数二分 
//二分模板一共有两个
//记得 红色 枚举左边的最右边界
//   绿色 枚举右边的最左边界 
//   对应最大求最小、最小求最大
//l=mid 补上+1
//r=mid 不加1 
//模板1
//当我们将区间[l,r]划分成[l,mid]和[mid+1,r]时，其更新操作是
//r=mid或l=mid+1,计算mid的时候不需要+1
int bsearch_1(int l,int r){
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))
            r=mid;
        else l=mid+1; //这个相当于绿色情况
                        //枚举右边的最左边界 
    }
    return l;
} 
//模板2 
//当我们将区间[l,r]划分成[l,mid-1]和[mid,r]时，其更新操作是
//r=mid-1或l=mid,计算mid的时候需要+1

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;
} 
//模板3
//浮点数二分，不会出现整除，不用考虑边界问题
//同时也不用改变 r 和 l 直接通过mid来改变
double l=0,r=x;
 while(r-l>1e-8){   //经验值 保留6位小数 -》1e-8; 
                    //保留4位小数 1e-6； 
    double mid=(l+r)/2;
    if(mid*mid>=x)
        r=mid;
    else l=mid;// 不需要处理边界 只需要l或r变成mid 
 } 
//第二种写法 暴力循环100次 不用精度
/********************************************/ 
//第三节课 高精度
//两个大整数相加
//两个大整数相减
//大整数 乘以一个小整数
//大整数乘以一个小整数

//1、大整数的存储 
//大整数每一位存在数组里面
//数组的第0位存个位 "倒着存" 
//因为进位要补一个数字 在数组的末尾补一个数字很方便 
//2.大整数的运算
//代码模拟竖式运算的过程
 /*大数相加*/
#include<bits/stdc++.h>
using namespace std;
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(1);
    return C;

}
int main()
{
    string a,b;
    vector<int> A,B;
    cin>>a>>b;//a=123456
    for(int i=a.size()-1;i>=0;i--){
        A.push_back(a[i]-'0');
    }
    for(int i=b.size()-1;i>=0;i--){
        B.push_back(b[i]-'0');
    }
    auto C=add(A,B);
    for(int i=C.size()-1;i>=0;i--){
        printf("%d",C[i]);

    }
    cout<<endl;
    return 0;
} 
/*大数相减*/
#include<bits/stdc++.h>
using namespace std;
vector<int> sub(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] - t;
        if (i < B.size())t -= B[i];
        C.push_back((t + 10) % 10);  //保证了t大于0的时候 push t t<0的时候push t+10 
        if (t < 0)
            t = 1;
        else t = 0;
    }
    while (C.size() > 1 && C.back() == 0)
        C.pop_back();
    return C;

}
bool cmp(vector<int> &A, vector<int> &B) {
    if (A.size() != B.size()) {
        if (A.size() > B.size())
            return true;
        else return false;
    }
    else {
        for (int i = A.size()-1; i >= 0; i--) {
            if (i < B.size()) {
                if (B[i] > A[i])
                    return false;
                else if (A[i] > B[i])
                    return true;
            }
        }
        return true;
    }
}
int main()
{
    string a, b;
    vector<int> A, B;
    cin >> a >> b;//a=123456
    for (int i = a.size() - 1; i >= 0; i--) {
        A.push_back(a[i] - '0');
    }
    for (int i = b.size() - 1; i >= 0; i--) {
        B.push_back(b[i] - '0');
    }
    //比较A B的大小
    if (cmp(A, B)) {
        auto C = sub(A, B);
        for (int i = C.size() - 1; i >= 0; i--) {
            printf("%d", C[i]);

        }
    }
    else {
        cout << "-";
        auto C = sub(B, A);
        for (int i = C.size() - 1; i >= 0; i--) {
            printf("%d", C[i]);


        }
    }

    cout << endl;
    return 0;
}
//大数乘法
//把小的数看成一个整体
//把大的数一位一位的乘以小的数
#include<bits/stdc++.h>
using namespace std;
vector<int> mul(vector<int> &A,int b){
    vector<int> C;
    int t=0;
    for(int i=0;i<A.size();;i++){
        t+=b*A[i];
        C.push_back(t%10);
        t/=10;
    }
    while(t){   //除完之后还有进位,则把剩余的t落下来 
        C.push_back(t%10);//例如最后一位 进位110
                            //则落下来110; 
        t/=10; 
    } 
    while(C.size()>1&&C.back()==0)//记得去掉前导0 
        C.pop_back(); 
    return C;
}
int main()
{
    string a;
    int b;
    cin>>a>>b;
    vector<int> A;
    for(int i=a.size()-1;i>=0;i--){
        A.push_back(a[i]-'0');
    }
    vector<int> C=mul(A,b);
    for(int i=C.size()-1;i>=0;i--){
        cout<<C[i];
    }
    cout<<endl;
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
// a/b 商为c 结果为r 
vector<int> div(vector<int> &a,int b,int &r )
{
    vector<int> c;
    for(int i=a.size()-1;i>=0;i--)
    {
        r=a[i]+r*10;
        c.push_back(r/b);
        r%=b;
    }
    reverse(c.begin(),c.end());
    while(c.size()>1&&c.back()==0)c.pop_back();
    return c; 
} 
int main()
{
    string a;
    int b;
    cin>>a>>b;
    vector<int> a1;
    int len1=a.size();
    for(int i=len1-1;i>=0;i--)
    {
        a1.push_back(a[i]-'');
    }
    int r=0;
    vector<int> C=div(a1,b,r);
    for(int i=C.size()-1;i>=0;i--)
    {
        cout<<C[i];
    }
    cout<<endl<<r<<endl;

    return 0;
}
//前缀和//
//1、如何求Si 
//s[i]通过s[i-1]+a[i]算出 
//2、作用 
//快速求出原数组中一段的和
//前缀和一般从1开始 
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int s[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);      
    }
    for(int i=1;i<=n;i++)
    {
        s[i]=s[i-1]+a[i];
    }
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",s[r]-s[l-1]); 
    }

}


//二维前缀和
//容斥定理
//理解公式推导过程，如图所示 
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int a[N][N],s[N][N];
int main()
{
    scanf("%d%d%d",&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++){
            s[i][j]=s[i-1][j]+s[i][j-1]-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[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);//计算子矩阵的和 
    }
    return 0;
} 
//差分
//前缀和的逆运算

//a1 a2... an
//构造b1 b2 ...bn
//使得 ai=b1+b2+...bi
//b1=a1
//b2=a2-a1
//b3=a3-a2
//bn=an-a(n-1)
//差分的含义
//使得a[l,r]的区间内所有元素加上c
//l+上c l后面的所有点都加上c
//r的位置减去c r后面的元素不加不减


#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m;
int a[N],b[N];
void insert(int l,int r,int c){
    b[l]+=c;
    b[r+1]-=c;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        b[i]=a[i]-a[i-1]; //构造差分数组 
    }
    while(m--){
        int l,r,c;
        scanf("%d%d%d",&l,&r,&c);
        intsert(l,r,c);  //使用差分数组 
    }
    for(int i=1;i<=n;i++){
        b[i]+=b[i-1];  //根据差分数组恢复原数组 
    }
    for(int i=1;i<=m;i++)
        printf("%d",b[i]);
    return 0;
}
//
//二维差分
//aij 是 bij的前缀和 
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
const int N=1e3+10;
int a[N][N],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()
{
    scanf("%d%d%d",&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,x2,y1,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        insert(x1,y1,x2,y2,c); //使用二位差分 加上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];
            a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j]; 
        }               //根据差分数组恢复原数组                               
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
         printf("%d ",a[i][j]); 
    }
    printf("\n");
}
    return 0;

}
总结
一维前缀和
1、 Si=a1+a2+...+ai
2、 sum(L,R)=aL+aL+1+aL+2+...+aR=Sr-Sl-1
步骤
1、预处理前缀和数组
2、用公式求区间和


二维前缀和
1、s[i,j]如何计算
S[i,j]=S[i-1,j]+S[i,j-1]-S[i-1,j-1]+a[i,j]

2、(x1,y1),(x2,y2)这一子矩阵中所有数的和如何计算
 S[x2,y2]-S[x1-1,y2]-S[x2,y1-1]+S[x1-1,y1-1]

差分
差分是前缀和的逆运算
 给定a[1],a[2],...a[n]
 构造差分数组b[N],使得
a[i]=b[1]+b[2]+...b[i];

核心操作
将a[L~R]全部加上C,等价于
b[l]+=C,b[R+1]-=C
a[1~L-1] 无影响
a[L~R] 加上了C
a[R+1~N] 无影响
a[]数组也可以用核心操作构造

 注意： 差分数组求前缀和就等价于操作后的原数组


二维差分

给定原矩阵a[i,j],构造差分矩阵b[i,j],使得a[][]是b[][]的二维前缀和 

不用考虑b数组 通过核心操作构造出b数组

二维差分核心操作
给以(x1,y1)为左上角，(x2,y2)为右下角的子矩阵中的所有数
a[i,j]加上c 

对于差分数组的影响
S[x1,y1]+=c
S[x1,y2+1]-=c
S[x2+1,y1]-=c
S[x2+1,y2+1]+=c


双指针算法
for(i=0,j=0;i<n;i++){
    while(j<i&&check(i,j))j++;
    //每到题目的具体逻辑 
} 
核心思想
将双重for循环这种暴力解法优化
从O(n^2)优化都O(n);
应用某种性质 如单调性

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
int a[N],s[N];
最长连续不重复子序列
j： j往左最远能到什么地方 
for(int i=0,j=0;i<n;i++){
    while(j<=i&&check(j,i))j++;
    res=max(res,i-j+1);
} 
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];  
    int res=0;
    for(int i=0,j=0;i<n;i++){
        s[a[i]]++;   // i 每走一步 向 s[i]中加一个数 
        while(s[a[i]]>1){//s[a[i]]>1 说明有重复的元素 
            s[a[j]]--;  //有重复的元素就将j向右移动 
            j++;        //j向右 s中减少一个数 直到 s[a[i]]不大于1 
        }
        res=max(res,i-j+1);
    }
    cout<<res<<endl;
    return 0;
} 

位运算 模板
1、 求整数n的二进制数表示中第k位是几 
①、先把第k位移到最后一位 n>>k
②、看个位是几 x&1
n>>k&1  -> n的二进制第k位数字是几


int k=10;
for(int k=3;k>=0;k--){
    cout<<(n>>k&1); //1010
} 


2、lowbit操作 树状数组的基本操作
返回x的最后一位1

x=1010 lowbit(x)=10;
x=101000 lowbit(x)=1000; 

 核心操作x&(-x)=x&(~x+1);

二进制 -x=~x+1;

作用：统计一个数x的二进制中1的个数 
每次把最后一位1减去  
次数就是1的个数

#include<iostream>
using namespace std;
int low_bit(int x){
    return x&(-x);
}
int main()
{
    int n;
    cin>>n;
    while(n--){
        int x;
        cin>>x;
        int ans=0;
        while(x>0)
        {
            x=x-low_bit(x);
            ans++;
        }
        cout<<ans<<" ";
    }
    return 0;
}

离散化
整数的离散化
将数字映射
a[] 1 3 100 2000 500000 
    0 1  2    3    4
1、 a中可能有重复元素 去重
2、 如何算出 a[i]离散化后的值是多少 (映射的值)
二分找出 a[i] 的下标 多少

去重 
a.erase(unique(a.begin(),a.end()),a.end()); 
模板

    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; r的位置就是找到的x位置 r+1是为了映射从1开始
                        映射1 2..n 
    }


离散化的应用 
区间和 
由于数据范围比较大 不能开那么大的数组 不能使用前缀和
跨度很大 但是有用的数据很稀疏 就使用离散化

 映射后就可以使用前缀和来解决
  #include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=3e5+10;
typedef pair<int,int > PII;
int a[N],s[N];
vector<int> alls;
vector<PII> add,que;
int find(int x ,int len){
    int l=0;int r=len-1; //有边界 是alls向量的长度 
    while(l<r){
        int mid=(l+r)/2;//在alls里面找 
        if(alls[mid]>=x) //这里是大于等于 
            r=mid;
        else l=mid+1;
    }
    return r+1;  //映射到从1开始 

}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x,c;
        cin>>x>>c;
        add.push_back(make_pair(x,c));
        alls.push_back(x);  

    }
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        que.push_back(make_pair(l,r)); 
        alls.push_back(l);
        alls.push_back(r);
    }
    sort(alls.begin(),alls.end());//alls.erase 对alls 进行去重 
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
    int len=alls.size();
    for(int i=0;i<=add.size()-1;i++){
        int pos=find(add[i].first,len);
        a[pos]+=add[i].second;
    }
    for(int i=1;i<=alls.size();i++){//遍历alls次 包括l r的 即使数字为0也求前缀和 
        s[i]=s[i-1]+a[i];
    }   
    for(int i=0;i<=que.size()-1;i++){
        int L=find(que[i].first,len);
        int R=find(que[i].second,len);
        cout<<s[R]-s[L-1]<<endl;
    }
    return 0;
}


区间合并



4. 区间合并

    // 将所有存在交集的区间合并
    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;
    }

1、 按区间的左端点排序
2、 扫描 每次维护一个区间
区间问题 很多都是贪心 先对左端点或右端点排序

#include<bits/stdc++.h>
using namespace std;
typedef  pair<int,int> PII;
vector<PII> num;
int n;
void merge(vector<PII> &segs){
    vector<PII> res;
    sort(segs.begin(),segs.end());//对区间的左端点排序 
    int st=-2e9,ed=-2e9; //pair默认对first升序排序

    st=segs[0].first;
    ed=segs[0].second;
    for(int i=0;i<segs.size();i++){
        if(ed<segs[i].first){
                res.push_back(make_pair(st,ed));
                st=segs[i].first;
                ed=segs[i].second;
                //当前区间的左边 是大于维护区间的右边
                //不可合并的 

        }
            else if(ed<segs[i].second){
                ed=segs[i].second;
            }//当前区间的左边小于维护区间的右边
            //可以合并 
    }
    if(st!=-2e9&&ed!=-2e9)
        res.push_back(make_pair(st,ed));
    cout<<res.size()<<endl;
} 
int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        num.push_back(make_pair(x,y));
    }
    merge(num);
    return 0;
}