常用算法模板

#include <bits/stdc++.h>

using namespace std;

/***********************************************************************
 * 基础算法:高精度,二分查找,前缀和,排序                                   *
 * 数据结构:双端队列,dsu,整数哈希,链表,队列,栈,字符串哈希,string,树,vector *
 * , Pair                                                              *
************************************************************************/

class Bigint // 高精度
{
    public:

    int len;
    int a[100005];

    bigint(int x = 0)
    {
        len = 0;
        while ( x )
        {
            len ++;
            a[len] = x % 10;
            x /= 10;
        }
    }

    void flatten(int L)
    {
        len = L;
        for ( int i = 1 ; i <= len ; ++ i )
        {
            a[i + 1] += a[i] / 10;
            a[i] %= 10;
        }
        while ( len > 1 && a[len] == 0 )
        {
            len --;
        }
    }

    void print()
    {
        for ( int i = len ; i >= 1 ; -- i )
        {
            cout << a[i];
        }
        cout << endl;
    }

    void input()
    {
        string s;
        cin >> s;
        len = s.length();
        for ( int i = s.length() ; i >= 1 ; -- i )
        {
            a[i] = s[s.length() - i] - '0';
        }
    }

    int &operator[](int i)
    {
        return a[i];
    }

    bool operator<(bigint b)
    {
        if ( len != b.len )
        {
            return len < b.len;
        }
        for ( int i = len ; i ; -- i )
        {
            if ( a[i] != b[i] )
            {
                return a[i] < b[i];
            }
        }
        return 0;
    }

    bool operator>(bigint b)
    {
        if ( len != b.len )
        {
            return len > b.len;
        }
        for ( int i = len ; i ; -- i )
        {
            if ( a[i] != b[i] )
            {
                return a[i] > b[i];
            }
        }
        return 0;
    }

    bool operator==(bigint b)
    {
        if ( len != b.len )
        {
            return false;
        }
        for ( int i = len ; i ; -- i )
        {
            if ( a[i] != b[i] )
            {
                return false;
            }
        }
        return 1;
    }

    bigint operator+(bigint b)
    {
        int len = max(len, b.len);
        bigint c;
        for ( int i = 1 ; i <= len ; ++ i )
        {
            c[i] += a[i] + b[i];
        }
        c.flatten(len + 1);
        return c;
    }

    bigint operator-(bigint b)
    {
        int len = max(len, b.len);
        bigint c;
        for ( int i = 1 ; i <= len ; ++ i )
        {
            c[i] += a[i] - b[i];
        }
        c.flatten(len);
        return c;
    }

    bigint operator*(bigint b)
    {
        int len = len + b.len;
        bigint c;
        for ( int i = 1 ; i <= len ; ++ i )
        {
            for ( int j = 1 ; j <= b.len ; ++ j )
            {
                c[i + j - 1] += a[i] * b[j];
            }
        }
        c.flatten(len + 1);
        return c;
    }
};

class Binary_search
{
    public:

    int n;
    int a[100005];
    void init()
    {
        n = 0;
        memset(a, 0, sizeof(a));
    }

    int lowerbound(int x)
    {
        int l = 1, r = n;
        while ( l < r )
        {
            int mid = l + r >> 1;
            if ( a[mid] < x )
            {
                l = mid + 1;
            }else
            {
                r = mid;
            }
        }
        return a[l] == x ? l : -1;
    }

    int upperbound(int x)
    {
        int l = 1, r = n;
        while ( l < r )
        {
            int mid = l + r + 1 >> 1;
            if ( a[mid] <= x )
            {
                l = mid;
            }else
            {
                r = mid - 1;
            }
        }
        return a[l] == x ? l : -1;
    }
};

class Prefix_sum // 前缀和
{
    public:

    int n;
    int a[100005];
    int sum[100005];

    void resize(int sz)
    {
        n = sz;
    }

    void init()
    {
        n = 0;
        memset(a, 0, sizeof(a));
        memset(sum, 0, sizeof(sum));
    }

    void init_sum()
    {
        for ( int i = 1 ; i <= n ; ++ i )
        {
            sum[i] = sum[i - 1] + a[i];
        }
    }

    int query(int l, int r)
    {
        init_sum();
        return sum[r] - sum[l - 1];
    }
};

class Sort // 排序
{
    public:

    int n;
    int a[100005];
    int t[100005];

    void quick_sort(int l, int r)
    {
        if ( l >= r )
        {
            return;
        }
        int mid = l + r >> 1;
        int i = l - 1, j = r + 1;
        int x = a[mid];
        while ( i < j )
        {
            do i ++; while (a[i] < x);
            do j --; while (a[j] > x);
            if ( i < j )
            {
                swap(a[i], a[j]);
            }
        }
        quick_sort(l, j);
        quick_sort(j + 1, r);
    }

    void merge_sort(int l, int r)
    {
        if ( l >= r )
        {
            return;
        }
        int mid = l + r >> 1;
        merge_sort(l, mid);
        merge_sort(mid + 1, r);
        int i = l, j = mid + 1;
        int k = 1;
        while ( i <= mid && j <= r )
        {
            if ( a[i] < a[j] )
            {
                t[k] = a[i];
                k ++;
                i ++;
            }else
            {
                t[k] = a[j];
                k ++;
                j ++;
            }
        }
        while ( i <= mid )
        {
            t[k ++] = a[i ++];
        }
        while ( j <= r )
        {
            t[k ++] = a[j ++];
        }
        for ( int i = l, j = 1 ; i <= r ; i ++, j ++ )
        {
            a[i] = t[j];
        }
    }
};

class Deque // 双端队列
{
    public:

    int head = 50000, tail = 49999;
    int que[100005];

    int size()
    {
        return tail - head + 1;
    }

    bool empty()
    {
        return !size();
    }

    void clear()
    {
        head = 50000;tail = 49999;
    }

    int front()
    {
        return que[head];
    }

    int back()
    {
        return que[tail];
    }

    void push_back(int x)
    {
        que[++ tail] = x;
    }

    void pop_back()
    {
        tail --;
        if ( tail - head + 1 < 0 )
        {
            tail ++;
        }
    }

    void push_front(int x)
    {
        que[-- head] = x;
    }

    void pop_front()
    {
        head ++;
        if ( tail - head + 1 < 0 )
        {
            head --;
        }
    }

    int* begin()
    {
        return que + head;
    }

    int* end()
    {
        return que + tail;
    }

    void print()
    {
        for ( int i = head ; i <= tail ; ++ i )
        {
            cout << que[i] << ' ';
        }
    }
};

class dsu // 并查集
{
    public:

    int n;
    int size[100005];
    int fa[100005];

    int find(int x) // 最早祖先
    {
        if ( x == fa[x] )
        {
            return x;
        }else
        {
            return fa[x] = find(fa[x]);
        }
    }

    void merge(int a, int b) // 合并
    {
        int aa = find(a), bb = find(b);
        if ( aa != bb )
        {
            fa[aa] = bb;
            size[bb] += size[aa];
        }
    }

    bool query_1(int a, int b) // 是否在同一个集合
    {
        return find(a) == find(b);
    }

    int query_2(int a) // 集合的大小
    {
        return size[find(a)];
    }

    void init()
    {
        for ( int i = 1 ; i <= n ; ++ i )
        {
            size[i] = 1;
            fa[i] = i;
        }
    }
};

class integer_hash // 整数哈希
{
    public:

    vector<int> v[10005];

    int h(int x) // 哈希函数
    {
        return (x % 10000 + 10000) % 10000;
        // 防止负数溢出
    }

    void insert(int x)
    {
        int hash = h(x);
        v[hash].push_back(x);
    }

    bool query(int x)
    {
        int hash = h(x);
        for ( int i = 0 ; i < v[hash].size() ; ++ i )
        {
            if ( v[hash][i] == x )
            {
                return true;
            }
        }
        return false;
    }
};

class LinkedList // 链表
{
    public:

    int v[100005];
    int ne[100005];
    int id = 0;

    int get(int i) // List[i]
    {
        int p = 0;
        for ( int q = 0 ; q < i ; ++ q, p = ne[p]);
        return p;
    }

    void insert(int i, int e) // 在i后插入e
    {
        ne[++ id] = ne[i];
        ne[i] = id;
        v[id] = e;
    }

    void remove(int i) // 删除ne[i]
    {
        ne[i] = ne[ne[i]];
    }

    int Length() // size
    {
        int j = 0;
        for ( int i = ne[0] ; i ; i = ne[i], ++ j );
        return j;
    }
};

class Queue // 队列
{
    public:

    int head = 0, tail = -1; // [head, tail]
    int que[100005];

    int size()
    {
        return tail - head + 1;
    }

    bool empty()
    {
        return !size();
    }

    void push(int x)
    {
        que[++ tail] = x;
    }

    int front()
    {
        return que[head];
    }

    int back()
    {
        return que[tail];
    }

    void pop()
    {
        head ++;
    }
};

class Stack // 栈
{
    public:

    int top = 0;
    int st[100005];

    void push(int x)
    { 
        top ++;
        st[top] = x;
    }

    void pop()
    {
        top --;
        if ( top == -1 )
        {
            top ++;
        }
    }

    int size()
    {
        return top;
    }

    bool empty()
    {
        return top == 0 ? 1 : 0;
    }

    int query_top()
    {
        return st[top];
    }
};

class string_hash // 字符串哈希
{
    public:

    string s;
    int l;
    int h[100005];
    int p[100005];

    void init()
    {
        l = s.length();
        p[0] = 1;
        for ( int i = 1 ; i <= l ; ++ i )
        {
            p[i] = p[i - 1] * 131;
            h[i] = h[i - 1] * 131 + s[i - 1];
        }
    }

    int gethash(int l, int r)
    {
        return h[r] - h[l - 1] * p[r - l + 1];
    }
};

class String // 字符串
{
    public:

    int len = 0;
    char c[100005];

    void init(char* x)
    {
        memset(c, 0, sizeof(c));
        len = strlen(x);
        for ( int i = 0 ; i < len ; ++ i )
        {
            c[i] = x[i];
        }
    }

    int length()
    {
        return len;
    }

    bool empty()
    {
        return !len;
    }

    void clear()
    {
        len = 0;
    }

    String substr(int x, int y)
    {
        String ans;
        for ( int i = x, j = 0 ; j < y ; j ++, i ++)
        {
            ans.len ++;
            ans.c[i] = c[j];
        }
        return ans;
    }

    char* c_str()
    {
        return c;
    }

    void print()
    {
        for ( int i = 0 ; i < len ; ++ i )
        {
            cout << c[i];
        }
        cout << endl;
    }

    char operator[](int i)
    {
        return c[i];
    }

    String operator+(String b)
    {
        String x;
        x.len = len + b.len;
        for ( int i = 0 ; i < len ; ++ i )
        {
            x.c[i] = c[i];
        }
        for ( int i = len ; i < len + b.len ; ++ i )
        {
            x.c[i] = b.c[i - len];
        }
        return x;
    }
};

class tree // 树
{
    public:

    int val[10005];
    vector<int> s[10005];

    int Degree(int i)
    {
        return s[i].size();
    }

    int depth(int x)
    {
        int ans = 1;
        for ( auto i : s[x] )
        {
            ans = max(ans, depth(i) + 1);
        }
        return ans;
    }

    void add(int i, int j) // i -> j
    {
        s[i].push_back(j);
    }

    void Print_BFS()
    {
        queue<int> q;
        q.push(1);
        while ( !q.empty() )
        {
            int tp = q.front();
            q.pop();
            cout << tp << ' ';
            for ( auto i : s[tp] )
            {
                q.push(i);
            }
        }
    }

    void Print_Pre_Order(int i) // 前序遍历
    {
        cout << i << ' ';
        for ( auto j : s[i] )
        {
            Print_Pre_Order(j);
        }
    }

    void Print_Post_Order(int i) // 后序遍历
    {
        for ( auto j : s[i] )
        {
            Print_Pre_Order(j);
        }
        cout << i << ' ';
    }
};

class Vector // 可变长数组
{
    public:

    int sz;
    int a[100005];

    int size()
    {
        return sz;
    }

    bool empty()
    {
        return sz == 0 ? 1 : 0;
    }

    void clear()
    {
        sz = 0;
    }

    void push_back(int x)
    {
        sz ++;
        a[sz] = x;
    }

    void pop_back()
    {
        sz --;
        if ( sz == -1 )
            sz ++;
    }

    int* begin()
    {
        return a + 1;
    }

    int* end()
    {
        return a + sz;
    }

    int front()
    {
        return a[1];
    }

    int back()
    {
        return a[sz];
    }

    void print()
    {
        for ( int i = 1 ; i <= sz ; ++ i )
        {
            cout << a[i] << ' ';
        }
        cout << endl;
    }

    int operator[](int i)
    {
        return a[i];
    }
};

class Pair // STL pair
{
    public:

    int first, second;

    void make_pair(int _first = 0, int _second = 0)
    {
        first = _first;
        second = _second;
    }

    bool operator<(Pair b)
    {
        return first != b.first ? first < b.first : second < b.second;
    }
};

更新日志

$2023.08.17$ 增加了STL pair