1
void quick_sort(int q[], int l, int r)
2
{
3
    if (l >= r) // 区间里没有数或只有一个数
4
        return;
5

6
    int x = q[l], i = l - 1, j = r + 1;
7
    // 下面用j做范围来递归时，x不能取到r，否则会有边界问题
8
    // i和j此处放在数组边界的两侧，防止后续越界，因为下面要先移动指针再判断，有可能会移出去
9
    while (i < j) // i和j迭代
10
    {
11
        do
12
            i++; // 向右移动i
13
        while (q[i] < x);
14
        do
15
            j--; // 向左移动j
16
        while (q[j] > x);
17
        if (i < j) // 两个指针不相遇时，swap
18
            swap(q[i], q[j]);
19
    }
20
    quick_sort(q, l, j);     // 处理区间【原数组左边界,j】的数据
21
    quick_sort(q, j + 1, r); // 处理区间【j+1,原数组右边界】的数据
22
}
23

24
// quick_sort(q,0,n-1)

1
void merge_sort(int arr[], int l, int r)
2
{
3
    if(l >= r) return;
4

5
    int mid = l + r >> 1; //确定分界点
6

7
    merge_sort(arr,l,mid);
8
    merge_sort(arr,mid+1,r); //递归进行排序，此时整个数组已经被分成了各段有序的小数组
9

10
    int k = 0, i = l,j = mid + 1; //定义双指针，i指向左半边起点，j指向右半边起点
11

12
    //归并，合二为一
13
    while(i <= mid && j <= r) //左半边和右半边不为空
14
    {
15
        if(arr[i] < arr[j]) tmp[k++] = arr[i++]; //比较i，j指向的数，把较小的数放到当前位置上并迭代指针
16
        else
17
            tmp[k++] = arr[j++]; // 注意别忘写else，算进等于的情况
18
    }
19

20
    //扫尾
21
    //当有一边没循环完而另一边已经停下的时候，直接把没循环完的那边接在后面
22
    while(i <= mid) tmp[k++] = arr[i++];
23
    while(j <= r) tmp[k++] = arr[j++];
24

25
    for(i = l, j = 0; i <= r; i++, j++) arr[i] = tmp[j]; //把临时存储的结果存回arr
26
}
27

28
//merge_sort(arr,0,n-1)

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
int arr[100010],tmp[100010];
5

6
ll merge_sort(int arr[], int l, int r)
7
{
8
    ll res = 0;
9
    if(l >= r) return 0;
10
    int mid = l + r >> 1;
11

12
    res += merge_sort(arr,l,mid);
13
    res += merge_sort(arr,mid+1,r);
14

15
    int k = 0, i = l, j = mid + 1;
16
    while(i <= mid && j <= r)
17
    {
18
        if(arr[i] <= arr[j]) tmp[k++] = arr[i++];
19
        else
20
        {
21
            tmp[k++] = arr[j++];
22
            res += mid - i + 1;
23
        }
24
    }
25

26
    while(i <= mid) tmp[k++] = arr[i++];
27
    while(j <= r) tmp[k++] = arr[j++];
28

29
    for(i = l, j = 0; i <= r; i ++, j ++) arr[i] = tmp[j];
30

31
    return res;
32

33
}
34
int main()
35
{
36
    int n;
37
    scanf("%d", &n);
38
    for(int i = 0; i < n; i ++)
39
    {
40
        scanf("%d", &arr[i]);
41
    }
42

43
    ll res = merge_sort(arr,0,n-1);
44
    cout << res << endl;
45
    return 0;
46
}

1
bool cmp(type &a,type &b)
2
{
3
    return a>b; //降序，第一个最大
4
    or
5
    return a<b; //升序，第一个最小
6
    //大的在前写大于，小的在前写小于
7
}

1
bool check(int x) {/* ... */} // 检查x是否满足某种性质
2

3
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
4
// 找最小索引（被查找数第一次出现的位置）
5
// 最大值最小
6
int bsearch_1(int l, int r)
7
{
8
    while (l < r)
9
    {
10
        int mid = l + r >> 1;
11
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
12
        else l = mid + 1;
13
    }
14
    return l;
15
}
16

17
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
18
// 找最大索引（被查找数最后一次出现的位置）
19
// 最小值最大
20
int bsearch_2(int l, int r)
21
{
22
    while (l < r)
23
    {
24
        int mid = l + r + 1 >> 1; // 补加1防止死循环
25
        if (check(mid)) l = mid;
26
        else r = mid - 1;
27
    }
28
    return l;
29
// 二分结束后，l和r相等，故return二者之一即可

1
string a, b;
2
    int A[1e6],B[1e6];
3
    cin >> a >> b;
4
    int lena = a.size(), lenb = b.size();
5
    for (int i = lena - 1; i >= 0; i--)
6
    {
7
        A[lena - i] = a[i] - '0';
8
    }
9
    for (int i = lenb - 1; i >= 0; i--)
10
    {
11
        B[lenb - i] = b[i] - '0';
12
    }
13
    //注意此写法A[0]和B[0]没存数，值为0，若使用此种方法，后面应该从1开始遍历

1
string a, b;
2
    vector<int> A, B;
3
    cin >> a >> b;
4
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
5
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');

1
#include <iostream>
2
#include <vector>
3
using namespace std;
4

5
bool cmp(vector<int> &A, vector<int> &B) //比较两个数谁大，以确定谁是被减数
6
{
7
    if(A.size() != B.size()) return A.size() > B.size();
8
    for(int i = A.size() - 1; i >= 0; i --)
9
        if(A[i] != B[i])
10
            return A[i] > B[i];
11
    return true;
12
}
13

14
vector<int> sub(vector<int> &A, vector<int> &B)
15
{
16
    vector<int> C;
17
    for(int i = 0, t = 0; i < A.size(); i++)
18
    {
19
        t = A[i] - t; //第i位A的值，考虑是否被前一位借走了1
20

21
        if(i < B.size()) t -= B[i]; //判断B在这一位上有没有数，有的话就减
22

23
        C.push_back((t + 10) % 10); //存这一位的结果，t>=0时输出t，t<0时输出(t+10)
24

25
        if(t < 0) t = 1; //若t小于0，则需要借位
26
        else t = 0;
27
    }
28

29
    **while(C.size() > 1 && C.back() == 0) C.pop_back(); //减法做完后，去掉前导0**
30
    return C;
31
}
32

33
int main()
34
{
35
    string a, b;
36
    vector<int> A, B;
37
    cin >> a >> b;
38
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
39
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
40

41
    if(cmp(A,B)) //比较A，B的大小
42
    {
43
        auto C = sub(A,B);
44
        for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
45
        cout << endl;
46
    }
47
    else //若A<B则算B-A，在输出时加负号
48
    {
49
        auto C = sub(B,A);
50
        cout << "-";
51
        for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
52
        cout << endl;
53
    }
54

55
    return 0;
56
}

1
// C = A * b, A >= 0, b > 0
2
vector<int> mul(vector<int> &A, int b)
3
{
4
    vector<int> C;
5
    int t = 0; //表示进位
6
    for (int i = 0; i < A.size() || t; i ++ ) //i循环完或t为0时停止循环，因此停止循环时t必为0
7
    {
8
        if (i < A.size()) t += A[i] * b; //每一位的值要加上上一位的进位
9
        C.push_back(t % 10); //取乘法运算的个位作为当前结果
10
        t /= 10;
11
    }
12
    while(C.size() > 1 && C.back() == 0) C.pop_back();//去掉前导0
13
    return C;
14
}

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4

5
using namespace std;
6

7
vector<int> div(vector<int> &A, int b, int &r) //传引用
8
{
9
    vector<int> C;
10
    r = 0;
11
    for(int i = A.size() - 1; i >= 0; i--)
12
    {
13
        r = r * 10 + A[i];
14
        C.push_back(r / b);
15
        r %= b;
16
    }
17

18
    **reverse(C.begin(), C.end());**
19

20
    while(C.size() > 1 && C.back() == 0) C.pop_back();
21
    return C;
22
}
23

24
int main()
25
{
26
    string a;
27
    vector<int> A;
28

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

33
    int r; //余数
34
    auto C = div(A, B, r);
35

36
    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i]; //注意倒着输出
37

38
    cout << endl << r << endl;
39

40
    return 0;
41
}