Fast platoon training

Quick layout template

void quick_sort(int a[], int l, int r)
{
    if (l >= r)
        return;
    int flag = a[(l+r)/2], i = l - 1, j = r + 1;
    while (i < j)
    {
        do
            i++;
        while (a[i] < flag);
        do
            j--;
        while (a[j] > flag);
        if (i < j)
            swap(a[i], a[j]);
        else
            break;
    }
    quick_sort(a, l, j);
    quick_sort(a, j + 1, r);
}

Merge sort

Merge sort template

void merge_sort(int a[], int l, int r)
{
    if (l >= r)
        return;
    int mid = (l + r) / 2;
    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])
            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, ++j)
        a[i] = tmp[j];
}

Integral dichotomy

Integer dichotomy template

// Integer binary algorithm template

bool check(int x) {/* ... */} // Check whether x satisfies certain properties

// When the interval [l, r] is divided into [l, mid] and [mid + 1, r], use:
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check() to determine whether the mid meets the nature
        else l = mid + 1;
    }
    return l;
}
// When the interval [l, r] is divided into [l, mid - 1] and [mid, r], use:
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;
}

Floating point dichotomy

Floating point binary template

// Floating point binary algorithm template

bool check(double x) {/* ... */} // Check whether x satisfies certain properties

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // The accuracy of eps depends on the requirement of the subject for accuracy
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

Large integer addition

Large integer addition template

vector<int> add(vector<int> &a, vector<int> &b)
{
    vector<int> c;
    int up = 0;
    for (int i = 0; i < a.size() || i<b.size(); ++i)
    {
        if (i < a.size())
            up += a[i];
        if (i < b.size())
            up += b[i];
        c.push_back(up % 10);
        up /= 10;
    }
    while (up>0)
    {
        c.push_back(up % 10);
        up /= 10;
    }
    return c;
}

Large integer subtraction template

Given two positive integers, calculate their difference, and the result may be negative.

Input format
 There are two lines, each containing an integer.

Output format
 A total of one line, including the difference.

Data range
 1 ≤ integer length ≤ 105
 Input example:
32
11
 Output example:
21

#include <iostream>
#include <vector>
using namespace std;
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;
    for (int i = 0, up = 0; i < a.size(); ++i)
    {
        up = a[i] - up;
        if (i < b.size())
            up = up - b[i];
        c.push_back((up + 10) % 10);
        if (up < 0)
            up = 1;
        else
            up = 0;
    }
    while(c.size()>1&&c.back()==0)
    c.pop_back();
    return c;
}
int main()
{
    string a, b;
    vector<int> A, B;
    cin >> a >> b;
    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');
    if(cmp(A,B))
    {
        auto C=sub(A,B);
        for (int i = C.size() - 1; i >= 0; --i)
        printf("%d", C[i]);
    }
    else
    {
        printf("-");
        auto C=sub(B,A);
        for (int i = C.size() - 1; i >= 0; --i)
        printf("%d", C[i]);
    }
    cout << endl;
    return 0;
}

High precision multiplication template

Given two positive integers A and B, please calculate the value of A * B.
    
Input format
 There are two lines in total. The first line contains the integer A, and the second line contains the integer B.

Output format
 A total of one line, containing the value of A * B.

Data range
 1 ≤ A length ≤ 100000,
0≤B≤10000
 Input example:
2
3
 Output example:
6

#include <iostream>
#include <string>
#include <cstdlib>
#include <cstring>
using namespace std;
const int cmax = 1e6 + 5;
int a[cmax], b[cmax], sum[cmax];
int main()
{
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(sum, 0, sizeof(sum));
    string astr, bstr;
    cin >> astr >> bstr;
    for (int i = astr.size() - 1, j = 0; i >= 0; --i, ++j)
        a[j] = astr[i] - '0';
    for (int i = bstr.size() - 1, j = 0; i >= 0; --i, ++j)
        b[j] = bstr[i] - '0';
    int alen = astr.size();
    int blen = bstr.size();
    for (int i = 0; i < alen; ++i)
        for (int j = 0; j < blen; ++j)
            sum[i + j] += a[i] * b[j];
    int up = 0, k = 0;
    while (k < alen + blen - 1)
    {
        sum[k] += up;
        up = sum[k] / 10;
        sum[k++] = sum[k] % 10;
    }
    while (up)
    {
        sum[k++] = up % 10;
        up /= 10;
    }
    if (astr[0]=='0' || bstr[0]=='0')
        cout << "0" ;
    else
        for (int i = k - 1; i >= 0; --i)
            printf("%d", sum[i]);
    cout << endl;
    return 0;
}

High precision division template

Given two nonnegative integers A and B, please calculate the quotient and remainder of A / B.

Input format
 There are two lines in total. The first line contains the integer A, and the second line contains the integer B.

Output format
 There are two lines in total. The first line outputs the quotient and the second line outputs the remainder.

Data range
 1 ≤ A length ≤ 100000,
1≤B≤10000
 B must not be 0

Input example:
7
2
 Output example:
3
1

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> div(vector<int> &A,int &b,int &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)
    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');
    int r;
    auto B=div(A,b,r);
    for(auto it=B.rbegin();it!=B.rend();++it)
    printf("%d",*it);
    cout<<endl<<r<<endl;
    return 0;
}

One dimensional prefixes and templates

Enter a sequence of integers of length n.

Next, enter m queries, one pair of l, r for each query.

For each query, the sum of the first number to the r number in the origina l sequence is output.

Input format

The first line contains two integers, n and m.

The second row contains n integers, representing an integer sequence.

Next m lines, each containing two integers l and r, represent the range of a query.

Output format

There are m lines in total, and each line outputs a query result.

Data range

1≤l≤r≤n1≤l≤r≤n,
1≤n,m≤1000001≤n,m≤100000,
- 1000 ≤ value of elements in the sequence ≤ 1000 − 1000 ≤ value of elements in the sequence ≤ 1000

Input example:

5 3
2 1 3 6 4
1 2
1 3
2 4

Output example:

3
6
10

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int cmax = 10e5 + 5;
int a[cmax], sum[cmax];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + a[i];
    while (m--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", sum[r] - sum[l - 1]);
    }
    return 0;
}

2D prefixes and templates

Input an integer matrix with n rows and m columns, and then input q queries. Each query contains four integers x1, y1, x2, y2, representing the upper left and lower right coordinates of a sub matrix.

The sum of all numbers in each query output submatrix.

Input format

The first line contains three integers n, m, q.

Next n lines, each containing m integers, represent an integer matrix.

Next line q, each line containing four integers x1, y1, x2, y2, represents a set of queries.

Output format

There are q lines in total, and each line outputs a query result.

Data range

1≤n,m≤10001≤n,m≤1000,
1≤q≤2000001≤q≤200000,
1≤x1≤x2≤n1≤x1≤x2≤n,
1≤y1≤y2≤m1≤y1≤y2≤m,
- 1000 ≤ value of elements in matrix ≤ 1000 − 1000 ≤ value of elements in matrix ≤ 1000

Input example:

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

Output example:

17
27
21

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int cmax = 1e3 + 5;
int a[cmax][cmax], sum[cmax][cmax];
int main()
{
    int n, m, q;
    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]);
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + a[i][j] - sum[i - 1][j - 1];
        }
    }
    while (q--)
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]);
    }
    return 0;
}

One dimensional difference template

Enter a sequence of integers of length n.

Next, enter m operations, each of which contains three integers, l, r, c, to add c to each number between [l, r] in the sequence.

Please output the sequence after all operations.

Input format

The first line contains two integers, n and m.

The second line contains n integers, representing the sequence of integers.

Next m lines, each containing three integers l, r, c, represent an operation.

Output format

A total of one line, including n integers, representing the final sequence.

Data range

1≤n,m≤1000001≤n,m≤100000,
1≤l≤r≤n1≤l≤r≤n,
−1000≤c≤1000−1000≤c≤1000,
- 1000 ≤ value of element in integer sequence ≤ 1000 − 1000 ≤ value of element in integer sequence ≤ 1000

Input example:

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

Output example:

3 4 5 3 4 2

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int cmax = 1e5 + 5;
int a[cmax], sum[cmax];
void insert(int l, int r, int val)
{
    sum[l] += val;
    sum[r + 1] -= val;
}
int main()
{
    int n, m;
    scanf("%d%d", &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 l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }
    for (int i = 1; i <= n; i++)
        sum[i] += sum[i - 1];
    for (int i = 1; i <= n; i++)
        printf("%d ", sum[i]);
    return 0;
}

Two dimensional difference template

Input an integer matrix of n rows and m columns, and then enter q operations. Each operation contains five integers x1, y1, x2, y2, c, where (x1, y1) and (x2, y2) represent the upper left and lower right coordinates of a submatrix.

Each operation adds c to the value of each element in the selected submatrix.

Please output the matrix after all operations.

Input format

The first line contains the integers n,m,q.

Next n lines, each containing m integers, represent an integer matrix.

Next row q, each row contains five integers x1, y1, x2, y2, c, representing an operation.

Output format

There are n lines in total, m integers in each line, indicating the final matrix after all operations are completed.

Data range

1≤n,m≤10001≤n,m≤1000,
1≤q≤1000001≤q≤100000,
1≤x1≤x2≤n1≤x1≤x2≤n,
1≤y1≤y2≤m1≤y1≤y2≤m,
−1000≤c≤1000−1000≤c≤1000,
- 1000 ≤ value of elements in matrix ≤ 1000 − 1000 ≤ value of elements in matrix ≤ 1000

Input example:

3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1

Output example:

2 3 4 1
4 3 4 1
2 2 2 2

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int cmax=1e3+5;
int a[cmax][cmax],b[cmax][cmax];
void Differential (int x1,int y1,int x2,int y2,int c)
{
    b[x1][y1]+=c;
    b[x1][y2+1]-=c;
    b[x2+1][y1]-=c;
    b[x2+1][y2+1]+=c;
}
int main()
{
    int n,m,q;
    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++)
            Differential(i,j,i,j,a[i][j]);
    while(q--)
    {
        int x1,x2,y1,y2,c;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
        Differential(x1,y1,x2,y2,c);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        b[i][j]+=b[i][j-1]+b[i-1][j]-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;
}

Double pointer algorithm (finding the longest continuous common subsequence)

Given a sequence of integers of length n, find the longest continuous interval without repeated numbers and output its length.

Input format

The first line contains the integer n.

The second line contains n integers (all in the range of 0-100000), representing the sequence of integers.

Output format

A total of one line, including an integer, indicating the length of the longest consecutive subsequence without repeating numbers.

Data range

1≤n≤1000001≤n≤100000

Input example:

5
1 2 2 3 5

Output example:

3

#include <bits/stdc++.h>
using namespace std;
const int cmax=1e6+5;
int a[cmax],s[cmax];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    scanf("%d",&a[i]);
    int res=0;
    for(int i=0,j=0;i<n;++i)
    {
        s[a[i]]++;
        while(s[a[i]]>1)
        {
            s[a[j]]--;
            j++;
        }
        res=max(res,i-j+1);
    }
    printf("%d\n",res);
    return 0;
}

Bit operation (lowbit algorithm)

Given a sequence of length n, please find the number of 1 in the binary representation of each number in the sequence.

Input format

The first line contains the integer n.

The second row contains n integers representing the entire sequence.

Output format

A total of one row, including n integers, where the ith number represents the number of 1 in the binary representation of the ith number in the sequence.

Data range

1≤n≤1000001≤n≤100000,
0 ≤ value of elements in the sequence ≤ 1090 ≤ value of elements in the sequence ≤ 109

Input example:

5
1 2 3 4 5

Output example:

1 1 2 1 2

#include <bits/stdc++.h>
using namespace std;
int lowbit(int x)
{
    return (x & (-x));  //Returns the first 1 of the first right to left number in binary and the 0 after it (returned in decimal)
}
int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int x, flag = 0;
        scanf("%d", &x);
        while (x)
        {
            x -= lowbit(x);
            flag++;
        }
        cout << flag << " ";
    }
    return 0;
}

If not tired, then my dream is not very cheap