快速排序 // 归并排序模板（复习）高精度乘法/除法模板（高+低）前缀和（一维+二维）差分（一维+二维）模板（8/31）-526互联

//快速排序模板

#include<iostream>
using namespace std;
const int N = 100001;
int a[N];
void quickersort(int l,int r)
{
if(l>=r) return;
int i=l-1;int j=r+1;int x=a[(l+r)/2];
while(i<j)
{
do i++;while(a[i]<x);
do j--;while(a[j]>x);
if(i<j) swap(a[i],a[j]);
}
quickersort(l,j);quickersort(j+1,r);//注意一定要用j返回，因为j在左边，作为终止返回，j+1正好分开

}

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




//归并排序模板
#include<iostream>
using namespace std;
const int N= 1e6+10;
int a[N],tmp[N];
void Sort(int l,int r)
{
    if(l>=r) return;
    int mid=(l+r)/2;//先进行二分，分出来，再返回的时候进行排序
    Sort(l,mid);Sort(mid+1,r);
    int i=l;int j=mid+1;int k=0;//取两个左边，然后进行将小的值存入数组
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[j]) tmp[k++]=a[i++];
        else tmp[k++]=a[j++];
    }
    while(i<=mid)tmp[k++]=a[i++];
    while(j<=r)tmp[k++]=a[j++];
    for( i=l,j=0;i<=r;i++) a[i]=tmp[j++];//再将数组存在原来数组，一定要按照左边值L进行首次返回
}


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

//高精度乘法模板
#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<int> mul(vector<int>&a,int b)
{
    int t=0;vector<int>c;
    for(int i=0;i<a.size()||t;i++)//高精度乘法核心代码
    {
        if(i<a.size()) t+=(a[i]*b);
        c.push_back(t%10);
        t/=10;
    }
    while(c.size()>1&&c.back()==0) c.pop_back();//为了应对b=0的情况
    return c;
}
int main()
{
    string a;int b;vector<int>A;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    vector<int>c;
    c=mul(A,b);
    for(int i=c.size()-1;i>=0;i--) printf("%d",c[i]);
    return 0;
}

//高精度除法
#include <iostream>
#include<string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> div(vector<int>& A, int b, int& r)
{
    r = 0; vector<int>c;//r为余数
    for (int i = A.size() - 1; i >= 0; i--)//因为很多题目混合运算，所以传倒着的数
    {
        r = r * 10 + A[i];
        c.push_back(r / b);//注意除的是b，不是10
        r %= b;
    }
    reverse(c.begin(),c.end());//引用头文件 algorithm
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

int main()
{
    string a;
    vector<int> A;

    int B;
    cin >> a >> B;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');

    int r;
    auto C = div(A, B, r);

    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];

    cout << endl << r << endl;

    return 0;
}

//一维前缀和模板
//公式：：b[i]=b[i-1]+a[i]

#include<iostream>
using namespace std;
const int N=100010;
int a[N],b[N];
int main()
{
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) b[i]=b[i-1]+a[i];
    while(m--)
    {
        int l,r;scanf("%d%d",&l,&r);
        printf("%d\n",b[r]-b[l-1]);//右边减 （左边减一）
    }
    return 0;
}

//二维前缀和
#include<iostream>
using namespace std;
#define N 1010
int a[N][N], b[N][N] = {0};
int main()
{
    int m, n, k;
    cin >> m >> n >> k;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            b[i][j] = b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1] + a[i][j];//核心公式
    while (k--)
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", b[x2][y2] - b[x1 - 1][y2] - b[x2][y1 - 1] + b[x1 - 1][y1 - 1]);//求范围和
    }
    return 0;
}

//一维差分
#include<iostream>
using namespace std;
#define N 100010
int a[N], b[N];
void insert(int l,int r,int x)
{
    b[l] += x;
    b[r + 1] -= x;
}
int main()
{
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)insert(i, i, a[i]);//巧妙求差分
    while (m--)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        insert(x, y, z);
    }
    for (int i = 1; i <= n; i++) b[i] += b[i - 1];//一定加上自身
    for (int i = 1; i <= n; i++) printf("%d ", b[i]);
    return 0;
}

//二维差分

#include<iostream>
using namespace std;
#define N 1010
int a[N][N], b[N][N];
void insert(int x1,int y1,int x2,int y2,int z)
{
    b[x1][y1] += z;
    b[x2 + 1][y1] -= z;
    b[x1][y2 + 1] -= z;
    b[x2 + 1][y2 + 1] += z;
}
int main()
{
    int m, n; int k;
    cin >> m >> n >> k;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            insert(i, j, i, j, a[i][j]);//类比一维差分，巧妙差分
    while (k--)
    {
        int x1, y1, x2, y2, z;
        cin>>x1>>y1>>x2>>y2>>z;
        insert(x1, y1, x2, y2, z);
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            b[i][j]+=b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];//一定加上自身
            printf("%d ",b[i][j]);
        }
        cout<<endl;
    }
    return 0;
}