408算法专题

线性表

顺序表

typedef struct {
    int data[Maxsize];
    int length;
} Sqlist;

//初始化顺序表
void Init(Sqlist &sq) {
    sq.length = 0;
    for (int i = 0; i < Maxsize; i ++ ) {
        sq.data[i] = 0;
    }
}

//判断顺序表是否为空
bool is_Empty(Sqlist sq) {
    if (sq.length == 0) {
        return true;
    } else {
        return false;
    }
}

//顺序表插入元素
bool Insert(Sqlist &sq, int x) {
    if (sq.length >= Maxsize) {
        return false;
    }
    sq.data[sq.length] = x;
    sq.length ++;
    return true;
}

//获取某个位置的元素值
bool get_Elem(Sqlist sq, int p, int &e) {
    if (p < 0 || p >= sq.length) {
        return false;
    } else {
        e = sq.data[p];
        return true;
    }
}

//输出顺序表
void show_sq(Sqlist sq) {
    for (int i = 0; i < sq.length; i ++ ) {
        int e;
        get_Elem(sq, i, e);
        cout << e << " \n"[i == sq.length - 1];
    }
}

//按值查找某个元素所在位置
int findElem(Sqlist sq, int x) {
    for (int i = 0; i < sq.length; i ++ ) {
        if (sq.data[i] == x) {
            return i;
        }
    }
    return -1;
}

//删除某个位置的元素
bool deleteElem(Sqlist &sq, int p, int &e) {
    if (p < 0 || p > sq.length) {
        return false;
    }
    e = sq.data[p];
    for (int i = p; i < sq.length - 1; i ++ ) {
        sq.data[i] = sq.data[i + 1];
    }
    sq.length --;
    return true;
}

//顺序表原地逆置
void reverse(Sqlist &sq) {
    for (int i = 0, j = sq.length - 1; i < j; i ++, j -- ) {
        swap(sq.data[i], sq.data[j]);
    }
}

链表

单链表（带头节点）

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode, *Linklist;

//初始化单链表，带头节点
bool InitList(Linklist &L) {
    L = (LNode *)malloc(sizeof(LNode));
    if (L == NULL) {
        return false;
    }
    L -> next = NULL;
    return true;
}

//按位序插入
bool ListInsert(Linklist &L, int position, int x) {
    if (position < 1) {
        return false;
    }
    LNode *p = L;
    int i = 0;
    while (p -> next && i < position - 1) {
        p = p -> next;
        i ++;
    }
    if (p == NULL) {
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s -> data = x;
    s -> next = p -> next;
    p -> next = s;
    return true;
}

//头插法建立单链表
bool CreateListFromHead(Linklist &L, vector<int> a, int n) {
    for (int i = 0; i < n; i ++ ) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        if (s == NULL) {
            return false;
        }
        s -> data = a[i];
        s -> next = L -> next;
        L -> next = s;
    }
    return true;
}

//尾插法建立单链表
bool CreateListFromTail(Linklist &L, vector<int> a, int n) {
    LNode *t = L;
    for (int i = 0; i < n; i ++ ) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        if (s == NULL) {
            return false;
        }
        s -> data = a[i];
        s -> next = t -> next;
        t -> next = s;
        t = s;
    }
    return true;
}

//按值查找
LNode* findElem(Linklist L, int e) {
    LNode *p = L;
    while (p -> next) {
        p = p -> next;
        if (p -> data == e) {
            return p;
        }
    }
    return NULL;
}

//按位查找
LNode* getElem(Linklist L, int position) {
    if (position < 1) {
        return NULL;
    }
    LNode *p = L;
    int i = 0;
    while (p && i <= position - 1) {
        p = p -> next;
        i ++;
    }
    return p;
}

//输出整个链表
void ShowLinklist(Linklist L) {
    LNode *p = L;
    while (p -> next) {
        p = p -> next;
        cout << p -> data << " ";
    }
    cout << "\n";
}

//指定节点前插
//注意，这里不需要传*&p也可以
bool Insert_prior(LNode *p, int e) {
    if (p == NULL) {
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s -> data = p -> data;
    s -> next = p -> next;
    p -> next = s;
    p -> data = e;
    return true;
}

//指定节点后插
bool Insert_next(LNode *p, int e) {
    if (p == NULL) {
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s -> data = e;
    s -> next = p -> next;
    p -> next = s;
    return true;
}

//求表长
int getLength(Linklist L) {
    int len = 0;
    LNode *p = L;
    while (p -> next) {
        p = p -> next;
        len ++;
    }
    return len;
}

//按位序删除
bool L_delete(Linklist &L, int position) {
    LNode *p = getElem(L, position - 1);
    if (p == NULL) {
        return false;
    }
    LNode *s = p -> next;
    p -> next = s -> next;
    free(s);
    return true;
}

//指定节点删除（无法删除最后一个节点）
bool deleteNode(LNode *p) {
    if (p -> next == NULL) {
        return false;
    }
    LNode *s = p -> next;
    p -> data = s -> data;
    p -> next = s -> next;
    free(s);
    return true;
}

//链表逆置
Linklist Inverse(Linklist L) {
    Linklist L_inverse;
    InitList(L_inverse);
    LNode *p = L;
    while (p -> next) {
        p = p -> next;
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s -> data = p -> data;
        s -> next = L_inverse -> next;
        L_inverse -> next = s;
    }
    return L_inverse;
}

//查找链表倒数第k个位置
LNode* getK(Linklist L, int k) {
    int length = 0;
    LNode *p = L;
    while (p -> next) {
        length ++;
        p = p -> next;
    }
    if (k > length) {
        return NULL;
    }
    int count = 0;
    p = L;
    while (p -> next) {
        p = p -> next;
        count ++;
        if (count == length - k + 1) {
            return p;
        }
    }
}

//删除值为x的元素
void delete_x(Linklist &L, int x) {
    LNode *p = L;
    while (p -> next != NULL) {
        LNode *s = p -> next;
        if (s -> data == x) {
            p -> next = s -> next;
            free(s);
            continue;
        }
        p = p -> next;
    }
}

//插入元素，保持链表升序
void insert_orderly(Linklist &L, int x) {
    LNode *p = L;
    while (p -> next != NULL) {
        LNode *pn = p -> next;
        if (pn -> data >= x) {
            break;
        } 
        p = pn;
    }
    LNode *s;
    s = (LNode *)malloc(sizeof(LNode));
    s -> data = x;
    s -> next = p -> next;
    p -> next = s;
}

//链表原地逆置
void reverseList(Linklist &L) {
    Linklist head;
    head = (LNode *)malloc(sizeof(LNode));
    head -> next = NULL;
    while (L -> next != NULL) {
        LNode *s = L -> next;
        L -> next = s -> next;
        s -> next = head -> next;
        head -> next = s;
    }
    L -> next = head -> next;
    free(head);
}

//将L拆成两个链表
int main() {
    Linklist LA, LB;
    InitList(LA);
    InitList(LB);

    LNode *ta = LA;
    LNode *tb = LB;

    LNode *p = L;
    int count = 0;
    while (p -> next) {
        LNode *s = p -> next;
        p -> next = s -> next;
        s -> next = NULL;
        count ++;
        if (count & 1) {
            ta -> next = s;
            ta = s;
        } else {
            tb -> next = s;
            tb = s;
        }
    }

    ShowLinklist(LA);
    ShowLinklist(LB);
}

//2019年真题(建议反复品味)
void change_list(Linklist &L) {
    LNode *middle, *p;
    p = L;
    middle = L;
    while (p -> next != NULL) {
        p = p -> next;
        middle = middle -> next;
        if (p -> next != NULL) {
            p = p -> next;
        }
    }
    LNode *temp = (LNode *)malloc(sizeof(LNode));
    temp -> next = NULL;
    while (middle -> next != NULL) {
        LNode *s = middle -> next;
        middle -> next = s -> next;
        s -> next = temp -> next;
        temp -> next = s;
    }
    middle -> next = NULL;
    LNode *head = (LNode *)malloc(sizeof(LNode));
    head -> next = NULL;
    LNode *tail = head;
    int cnt = 0;
    while (L -> next || temp -> next) {
        cnt ++;
        LNode *s;
        if (cnt & 1) {
            s = L -> next;
            L -> next = s -> next;
        } else {
            s = temp -> next;
            temp -> next = s -> next;
        }
        s -> next = NULL;
        tail -> next = s;
        tail = s;
    }
    L -> next = head -> next;
}

注意

• ==删除值为x的元素时，不要忘记continue，否则无法连续删除值为x的元素==
• ==链表原地逆置算法==

单链表（不带头节点）

重点是尾插法部分

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode, *Linklist;

//不带头节点
bool InitList(Linklist &L) {
    L = NULL;
    return true;
}

//按位序插入
bool InsertList(Linklist &L, int position, int x) {
    if (position < 1) {
        return false;
    }
    if (position == 1) {
        //插入第一个位置需要进行特殊处理
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s -> data = x;
        s -> next = L;
        L = s;
        return true;
    } 
    int i = 0;
    LNode *p = L;
    while (p && i < position - 2) {
        i ++;
        p = p -> next;
    }
    if (p == NULL) {
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s -> data = x;
    s -> next = p -> next;
    p -> next = s;
    return true;
}

//头插法建立单链表
bool CreateListFromHead(Linklist &L, vector<int> a, int n) {
    for (int i = 0; i < n; i ++ ) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        if (s == NULL) {
            return false;
        }
        s -> data = a[i];
        s -> next = L;
        L = s;
    }
    return true;
}

//尾插法建立单链表
bool CreateListFromTail(Linklist &L, vector<int> a, int n) {
    LNode *t; //此处不能直接定义为 t = L
    for (int i = 0; i < n; i ++ ) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s -> data = a[i];
        s -> next = NULL;
        if (L == NULL) {
            L = s;
            t = L;
        } else {
            t -> next = s;
            t = s;
        }
    }
    return true;
}

//按值查找
LNode* findElem(Linklist L, int e) {
    if (L == NULL) {
        return NULL;
    }
    LNode *p = L;
    while (p) {
        if (p -> data == e) {
            return p;
        }
        p = p -> next;
    }
    return NULL;
}

//按序查找
LNode* getElem(Linklist L, int position) {
    LNode *p = L;
    int i = 1;
    while (p && i < position) {
        i ++;
        p = p -> next;
    }
    return p;
}

//输出链表
void ShowList(Linklist L) {
    LNode *p = L;
    while (p) {
        cout << p -> data << " ";
        p = p -> next;
    }
}

//链表逆置
Linklist Inverse(Linklist L) {
    Linklist L_inverse;
    L_inverse = NULL;
    LNode *p = L;
    while (p) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s -> data = p -> data;
        if (L_inverse == NULL) {
            s -> next = NULL;
            L_inverse = s;
        } else {
            s -> next = L_inverse;
            L_inverse = s;
        }
        p = p -> next;
    }
    return L_inverse;
}

小寄巧

==没有头节点，可以自己创建一个头节点，返回答案时，去掉头节点==

//删除倒数第n个节点
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode *temp = (ListNode *)malloc(sizeof(ListNode));
    temp -> next = head;
    ListNode *fi = temp, *sec = temp;
    int x = n;
    while (x --) {
        sec = sec -> next;
    }
    while (sec -> next) {
        fi = fi -> next;
        sec = sec -> next;
    }
    fi -> next = fi -> next -> next;
    ListNode *res = temp -> next;
    free(temp);
    return res;
}

栈、队列

顺序栈

typedef struct{
    int data[MaxSize];
    int top;
}SqStack;

//顺序栈初始化
void InitSqStack(SqStack &s) {
    s.top = -1;
}

//插入
bool push(SqStack &s, int x) {
    if (s.top > MaxSize) {
        return false;
    }
    s.data[++s.top] = x;
    return true;
}

//出栈
bool pop(SqStack &s, int &e) {
    if (s.top < 0) {
        return false;
    }
    e = s.data[s.top--];
    return true;
}

//获取栈顶元素
bool getElem(SqStack s, int &e) {
    if (s.top < 0) {
        return false;
    }
    e = s.data[s.top];
    return true;
}

循环队列

相比于顺序队列，只需要修改一下入队出队的代码

typedef struct {
    int data[Maxsize];
    int front, rear;
}Queue;

void InitQueue(Queue &q) {
    q.front = 0;
    q.rear = 0;
}

bool push(Queue &q, int x) {
    if ((q.rear + 1) % Maxsize == q.front) {
        return false;
    }
    q.data[q.rear] = x;
    q.rear = (q.rear + 1) % Maxsize;
    return true;
}

bool pop(Queue &q, int &e) {
    if (q.rear == q.front) {
        return false;
    }
    e = q.data[q.front];
    q.front = (q.front + 1) % Maxsize;
    return true;
}

链式队列

typedef struct LinkNode{
    int data;
    struct LinkNode *next;
} LNode;

typedef struct{
    LNode *front, *rear;
}Queue;

//初始化链队
void InitQueue(Queue &q) {
    q.front = (LNode *)malloc(sizeof(LNode));
    q.rear = q.front;
    q.front -> next = NULL;
}

//入队
bool push(Queue &q, int e) {
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) {
        return false;
    }
    s -> data = e;
    s -> next = NULL;
    q.rear -> next = s;
    q.rear = s;
    return true;
}

//出队（注意出队后，若队列为空的处理）
bool pop(Queue &q, int  &e) {
    if (q.front == q.rear) {
        return false;
    }
    LNode *p = q.front -> next;
    e = p -> data;
    q.front -> next = p -> next;
    //注意此处，若队列为空，需要修改一下rear指针
    if (q.rear == p) {
        q.rear = q.front;
    }
    free(p);
    return true;
}

//判空
bool is_Empty(Queue q) {
    if (q.rear == q.front) {
        return true;
    } else {
        return false;
    }
}

图

//拓扑排序
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> edges(numCourses);
        vector<int> indgree(numCourses, 0);
        for (int i = 0; i < prerequisites.size(); i ++ ) {
          //邻接表存边
            edges[prerequisites[i][1]].push_back(prerequisites[i][0]);
          //有向边的终点入度 + 1
            indgree[prerequisites[i][0]] ++;
        }
        queue<int> q;
        int vis = 0;
        for (int i = 0; i < numCourses; i ++ ) {
            if (indgree[i] == 0) {
                q.push(i);
            }
        }
        while (q.size()) {
          //每次循环输出一个节点
            int now_vis = q.front();
            q.pop();
            vis ++;
          //当前节点输出，根据节点延伸出去的边，减少相邻点的入度
            for (int i = 0; i < edges[now_vis].size(); i ++ ) {
                if (--indgree[edges[now_vis][i]] == 0 ) {
                  //若是该点入度减为零，则使该点入队，等待输出
                    q.push(edges[now_vis][i]);
                }
            }
        }
        return vis == numCourses;
    }
};

//拓扑排序，输出拓扑排序结果
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> indgree(numCourses);
        vector<vector<int>> edges(numCourses);
        for (int i = 0; i < prerequisites.size(); i ++ ) {
            edges[prerequisites[i][1]].push_back(prerequisites[i][0]);
            indgree[prerequisites[i][0]] ++;
        }
        queue<int> q;
        vector<int> res;
        for (int i = 0; i < numCourses; i ++ ) {
            if (indgree[i] == 0) {
                q.push(i);
            }
        }
        while (q.size()) {
            int now_vis = q.front();
            q.pop();
            res.push_back(now_vis);
            for (int i = 0; i < edges[now_vis].size(); i ++ ) {
                if (--indgree[edges[now_vis][i]] == 0) {
                    q.push(edges[now_vis][i]);
                }
            }
        }
        return res.size() == numCourses ? res : vector<int> ();
    }
};

//dfs求连通块数量
class Solution {
private:
    int m, n;
public:
    void dfs(int i, int j, vector<vector<char>> &grid) {
        if (grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        if (i + 1 < m) {
            dfs(i + 1, j, grid);
        }
        if (j + 1 < n) {
            dfs(i, j + 1, grid);
        }
        if (i - 1 >= 0) {
            dfs(i - 1, j, grid);
        }
        if (j - 1 >= 0) {
            dfs(i, j - 1, grid);
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        int res = 0;
        m = grid.size();
        n = grid[0].size();
        for (int i = 0; i < m; i ++ ) {
            for (int j = 0; j < n; j ++ ) {
                if (grid[i][j] == '1') {
                    res ++;
                    dfs(i, j, grid);
                }
            }
        }
        return res;
    }
};

树

//结构体定义
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
}

//中序遍历（前序遍历和后续遍历换一下res修改顺序即可）
void inOrder(TreeNode *Node, vector<int> &res) {
    if (Node == NULL) {
        return;
    }
    inOrder(Node -> left, res);
    res.push_back(Node -> val);
    inOrder(Node -> right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    inOrder(root, res);
    return res;
}

//层序遍历（参考leetcode官方解答，建议反复观看）
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (root == NULL) {
        return res;
    }
    queue<TreeNode *> q;
    q.push(root);
    while (!q.empty()) {
        //将当前一层节点访问完之后，再开启下一轮循环
        //这样就不需要通过二元组建立哈希映射来判断当前节点是哪一层了
        int currentNum = q.size();
        res.push_back(vector<int> ());
        for (int i = 0; i < currentNum; i ++ ) {
            TreeNode *s = q.front();
            q.pop();
            res.back().push_back(s -> val);
            if (s -> left) {
                q.push(s -> left);
            }
            if (s -> right) {
                q.push(s -> right);
            }
        }
    }
    return res;
}

//求树的深度
int maxDepth(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    int depth = max(maxDepth(root -> left), maxDepth(root -> right)) + 1;
    return depth;
}

//求是否存在指定路径和的从根节点到叶子结点的路径
bool hasPathSum(TreeNode* root, int targetSum) {
    if (root == nullptr) {
        return false;
    }
    if (root -> left == nullptr && root -> right == nullptr) {
        return targetSum == root -> val;
    }
    return hasPathSum(root -> left, targetSum - root -> val) || hasPathSum(root -> right, targetSum - root -> val);
}

//判断树是否左右对称(节点成对push，成对检查)
class Solution {
public:
    bool check(TreeNode *u, TreeNode *v) {
        queue<TreeNode *> q;
        q.push(u);
        q.push(v);
        while (q.size()) {
            auto r1 = q.front();
            q.pop();
            auto r2 = q.front();
            q.pop();
            if (!r1 && !r2) {
                continue;
            }
            if ((!r1 || !r2) || (r1 -> val != r2 -> val)) {
                return false;
            }
            q.push(r1 -> left);
            q.push(r2 -> right);

            q.push(r1 -> right);
            q.push(r2 -> left);
        }
        return true;
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

//将一颗二叉树左右翻转
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return root;
        }
        TreeNode *right = invertTree(root -> left);
        TreeNode *left = invertTree(root -> right);
        root -> left = left;
        root -> right = right;
        return root;
    }
};

查找

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 0; i < n; i ++ ) {
        cin >> a[i];
    }
    while (m -- ) {
        int x;
        cin >> x;
        int i = 0, j = n - 1;
      //找左边界
        while (i < j) {
            int mid = i + j >> 1;
            if (a[mid] < x) {
                i = mid + 1;
            } else {
                j = mid;
            }
        }
        if (a[i] != x) {
            cout << "-1 -1\n";
            continue;
        } else {
            cout << i << " ";
        }
        i = 0, j = n - 1;
      //找右边界
        while (i < j) {
            int mid = i + j + 1 >> 1;
            if (a[mid] <= x) {
                i = mid;
            } else {
                j = mid - 1;
            }
        }
        cout << i << "\n";
    }
    return 0;
}

排序算法

//插入排序(稳定)
void insertSort(vector<int> &a, int n) {
 for (int i = 1; i < n; i ++ ) {
     if (a[i] < a[i - 1]) {
         int temp = a[i];
         int j;
         for (j = i - 1; j >= 0 && a[j] > temp; j -- ) {
             a[j + 1] = a[j];
         }
         a[j + 1] = temp;
     }
 }
}

//希尔排序(不稳定)
void shellSort(vector<int> &a, int n) {
 for (int d = n / 2; d >= 1; d /= 2) {
     for (int i = d; i < n; i ++ ) {
         if (a[i] < a[i - d]) {
             int temp = a[i];
             int j;
             for (j = i - d; j >= 0 && a[j] > temp; j -= d) {
                 a[j + d] = a[j];
             }
             a[j + d] = temp;
         }
     }
 }
}

//冒泡排序(稳定)
void bubbleSort(vector<int> &a, int n) {
 for (int i = 0; i < n; i ++ ) {
     for (int j = n - 1; j > 0; j -- ) {
         if (a[j] < a[j - 1]) {
             swap(a[j], a[j - 1]);
         }
     }
 }
}

//快速排序(不稳定)
void quickSort(vector<int> &a, int l, int r) {
 if (l >= r - 1) {
     return;
 }
 int i = l - 1, j = r, x = a[(l + r) >> 1];
 while (i < j) {
     //这里使用do while循环，保证每次的i和j一定会更新
     //防止a[i] = a[j] = x，导致i和j都不会更新，陷入死循环
     do {
         i ++;
     } while (a[i] < x);
     do {
         j --;
     } while (a[j] > x);
     if (i < j) {
         swap(a[i], a[j]);
     }
 }
 quickSort(a, l, i);
 quickSort(a, i, r);
}

//简单选择排序(不稳定，交换过程可能导致不稳定)
void selectSort(vector<int> &a, int n) {
 for (int i = 0; i < n - 1; i ++ ) {
     int min = i;
     for (int j = min + 1; j < n; j ++ ) {
         if (a[j] < a[min]) {
             min = j;
         }
     }
     swap(a[min], a[i]);
 }
}

//小根堆下坠
void downMinHeap(vector<int> &a, int u, int n) {
 int t = u;
 if (u * 2 <= n && a[t] > a[u * 2]) {
     t = u * 2;
 }
 if (u * 2 + 1 <= n && a[t] > a[u * 2 + 1]) {
     t = u * 2 + 1;
 }
 if (t != u) {
     swap(a[t], a[u]);
     downMinHeap(a, t, n);
 }
}

//大根堆下坠
void downMaxHeap(vector<int> &a, int u, int n) {
 int t = u;
 if (u * 2 <= n && a[t] < a[u * 2]) {
     t = u * 2;
 }
 if (u * 2 + 1 <= n && a[t] < a[u * 2 + 1]) {
     t = u * 2 + 1;
 }
 if (t != u) {
     swap(a[t], a[u]);
     downMaxHeap(a, t, n);
 }
}

//建立小根堆(数组下标从1开始，方便寻找双亲和孩子)
void buildMinHeap(vector<int> &a, int n) {
 for (int i = n / 2; i > 0; i -- ) {
     downMinHeap(a, i, n);
 }
}

//建立大根堆(数组下标从1开始，方便寻找双亲和孩子)
void buildMaxHeap(vector<int> &a, int n) {
 for (int i = n / 2; i > 0; i -- ) {
     downMaxHeap(a, i, n);
 }
}

//堆排序(从小到大, 不稳定)
void heapSort(vector<int> &a, int n) {
 for (int i = n; i > 1; i -- ) {
     swap(a[1], a[i]);
     downMaxHeap(a, 1, i - 1);
 }
}

//归并排序(稳定)
void mergeSort(vector<int> &a, int l, int r) {
 if (l >= r - 1) {
     return;
 }
 int mid = (l + r) >> 1;
 mergeSort(a, l, mid);
 mergeSort(a, mid, r);
 vector<int> temp;
 int k = 0, i = l, j = mid;
 while (i < mid && j < r) {
     if (a[i] <= a[j]) {
         temp.push_back(a[i ++ ]);
     } else {
         temp.push_back(a[j ++ ]);
     }
 }
 while (i < mid) {
     temp.push_back(a[i ++ ]);
 }
 while (j < r) {
     temp.push_back(a[j ++ ]);
 }
 for (int p = l; p < r; p ++ ) {
     a[p] = temp[p - l];
 }
}

//求逆序对
void inversePair(vector<int> &a, int l, int r, long long &res) {
 if (l >= r - 1) {
     return;
 }
 int mid = (l + r) >> 1;
 inversePair(a, l, mid, res);
 inversePair(a, mid, r, res);
 vector<int> temp;
 int k = 0, i = l, j = mid;
 while (i < mid && j < r) {
     if (a[i] <= a[j]) {
         temp.push_back(a[i ++ ]);
     } else {
         res += mid - i;
         temp.push_back(a[j ++ ]);
     }
 }
 while (i < mid) {
     temp.push_back(a[i ++ ]);
 }
 while (j < r) {
     temp.push_back(a[j ++ ]);
 }
 for (int p = l; p < r; p ++ ) {
     a[p] = temp[p - l];
 }
}