算法小站中和算法竞赛相关内容的头文件

依赖头文件

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
#include <unordered_map>

using namespace std;
typedef long long ll;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

// ============================================================== //

线段树延迟标记模版

class segTree {
public:
    struct node {
        int l, r;
        int sum1, sum2;
        int tag1, tag2;

        void apply1(int v) {
            tag1 += v;
            sum1 += v * (r-l+1);
        }
        void apply2(int v) {
            tag2 += v;
            sum2 += v * (r-l+1);
        }
    };

    inline void push(int p) {
        if (t[p].l != t[p].r && t[p].tag1) {
            t[p<<1].apply1(t[p].tag1);
            t[p<<1 | 1].apply1(t[p].tag1);
            t[p].tag1 = 0;
        }
        if (t[p].l != t[p].r && t[p].tag2) {
            t[p<<1].apply2(t[p].tag2);
            t[p<<1 | 1].apply2(t[p].tag2);
            t[p].tag2 = 0;
        }
    }
    inline void pull(int p) {
        int lc = p<<1, rc = p<<1 | 1;
        t[p].sum1 = t[lc].sum1 + t[rc].sum1;
        t[p].sum2 = t[lc].sum2 + t[rc].sum2;
    }

    void change(int p, const int l, const int r, int add1, int add2) {
        if (l <= t[p].l && t[p].r <= r) {
            t[p].apply1(add1), t[p].apply2(add2);
            return;
        }

        push(p);
        int mid = (t[p].l + t[p].r) >> 1;
        if (l <= mid) change(p<<1, l, r, add1, add2);
        if (r > mid) change(p<<1 | 1, l, r, add1, add2);

        pull(p);
    }

    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r;
        if (l >= r) return;
        int mid = (l+r) >> 1;
        if (l <= mid) build(p<<1, l, mid);
        if (r > mid) build(p<<1 | 1, mid+1, r);
    }

    void query(int p, const int C) {
        if (t[p].l == t[p].r) {
            printf("%d %d\n", t[p].sum1, t[p].sum2);
            return;
        }
        push(p);

        int mid = (t[p].l + t[p].r) >> 1;
        if (C <= mid) query(p<<1, C);
        else query(p<<1 | 1, C);
    }

    int n;
    vector<node> t;

    segTree() = default;
    segTree(int _n) : n(_n) {
        assert(n > 0);
        t.resize(n << 2);
    }
    void clear() {
        fill(t.begin(), t.end(), node());
    }
};

如果有多组数据
const int maxn = 100000 + 10;
segTree seg(maxn);

void init() {
    seg.clear();
}

int main() {
    while (T--) {
        init();
    }
}

主席树模版

询问区间 $[u, v]$ 中 $\leqslant k$ 的元素有多少个
主席树如果出现 $MLE$，空间一般取 $O(n) = 20\cdot n$

class wsegTree {
public:
    struct node {
        int l, r;
        int sum;
    };

    int n;
    int tot;
    vector<node> t;

    wsegTree() = default;
    wsegTree(int _n) : n(_n) {
        assert(n > 0);
        tot = 0;
        t.resize(n * 20);
    }
    void clear() {
        tot = 0;
        fill(t.begin(), t.end(), node());
    }

    int build(int l, int r) {
        int u = ++tot;
        if (l >= r) return u;
        int mid = (l + r) >> 1;
        t[u].l = build(l, mid);
        t[u].r = build(mid+1, r);
        return u;
    }

    int change(int pre, int l, int r, int x, int v) {
        // find [l, r] = [x, x]
        int u = ++tot;
        t[u] = t[pre];
        t[u].sum = t[pre].sum + v;
        if (l >= r) return u;
        int mid = (l + r) >> 1;
        if (x <= mid)  t[u].l = change(t[pre].l, l, mid, x, v);
        else t[u].r = change(t[pre].r, mid+1, r, x, v);
        return u;
    }
    int query(int i, int j, int l, int r, int k) {
        if (l >= r) return t[j].sum - t[i].sum;
        int res = 0, mid = (l + r) >> 1;
        if (k <= mid) res = query(t[i].l, t[j].l, l, mid, k);
        else {
            res += t[t[j].l].sum - t[t[i].l].sum;
            res += query(t[i].r, t[j].r, mid + 1, r, k);
        }
        return res;
    }
};

wsegTree wseg(maxn);
int root[maxn];

模 P 下的运算

算法竞赛有关的计数问题，经常需要我们求解 $\bmod \ P$ 意义下的结果
这里将运算封装如下

constexpr int P = 998244353;

int norm(int x) {
    if (x < 0) x += P;
    if (x >= P) x -= P;
    return x;
}

template<class T>
T power(T a, int b) {
    T res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res *= a;
        a *= a;
    }
    return res;
}

struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}

    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P-x));
    }
    Z &operator *= (const Z &rhs) {
        x = (ll)(x) * rhs.x % P;
        return *this;
    }
    Z &operator += (const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator -= (const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator /= (const Z &rhs) {
        return *this *= rhs.inv();
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P-2);
    }
    friend Z operator* (const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+ (const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator- (const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/ (const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
};

高精度封装

在算法竞赛有关的问题中，特别是计数问题，也经常需要用到高精度
高精度坑很多，这里也封装成结构体

struct Int {
    static constexpr int B = 10;
    vector<int> X;
    int size() const {
        return (int)X.size();
    }

    Int(int x = 0) {
        while (x) {
            X.push_back(x % B), x /= B;
        }
    }

    Int(string str) {
        reverse(str.begin(), str.end());
        for (auto u : str) X.push_back(u-'0');
    }

    friend Int operator+ (const Int &lhs, const Int &rhs) {
        if (lhs.size() < rhs.size()) return rhs + lhs;
        Int res;

        int t = 0;
        for (int i = 0; i < lhs.size(); i++) {
            t += lhs.X[i];
            if (i < rhs.size()) t += rhs.X[i];
            res.X.push_back(t % B), t /= B;
        }
        if (t) res.X.push_back(t);
        while (res.X.size() > 1 && res.X.back() == 0) res.X.pop_back();
        return res;
    }

    friend Int operator- (const Int &lhs, const Int &rhs) {
        Int res;
        int t = 0;
        for (int i = 0; i < lhs.size(); i++) {
            t = lhs.X[i] - t;
            if (i < rhs.size()) t -= rhs.X[i];
            res.X.push_back((t + B) % B);

            if (t < 0) t = 1;
            else t = 0;
        }
        while (res.X.size() > 1 && res.X.back() == 0) res.X.pop_back();
        return res;
    }

    friend Int operator* (const Int &lhs, int b) {
        Int res;
        int t = 0;
        for (int i = 0; i < lhs.X.size() || t; i++) {
            if (i < lhs.X.size()) t += lhs.X[i] * b;
            res.X.push_back(t % B), t /= B;
        }
        return res;
    }

    friend Int operator/ (const Int &lhs, int b) {
        Int res;
        int r = 0;
        for (int i = lhs.X.size()-1; i >= 0; i--) {
            r = r * B + lhs.X[i];
            res.X.push_back(r / b), r %= b;
        }
        reverse(res.X.begin(), res.X.end());
        while (res.X.size() > 1 && res.X.back() == 0) res.X.pop_back();
        return res;
    }

    friend Int operator* (const Int &lhs, const Int &rhs) {
        Int res;
        res.X.resize(lhs.size() + rhs.size() + B);
        fill(res.X.begin(), res.X.end(), 0);

        for (int i = 0; i < lhs.size(); i++) {
            for (int j = 0; j < rhs.size(); j++) {
                res.X[i+j] += lhs.X[i] * rhs.X[j];
            }
        }
        for (int i = 0; i < res.X.size(); i++) {
            if (res.X[i] >= B) res.X[i+1] += res.X[i] / B, res.X[i] %= B;
        }

        while (res.X.size() > 1 && res.X.back() == 0) res.X.pop_back();
        return res;
    }

    friend Int operator/ (const Int& lhs, const Int &rhs) {
        int dv = lhs.size() - rhs.size();
        assert(dv >= 0);

        Int res;
        res.X.resize(dv+1);
        fill(res.X.begin(), res.X.end(), 0);

        // append suffix zero
        Int a = lhs, b = rhs;
        reverse(b.X.begin(), b.X.end());
        for (int i = 0; i < dv; i++) b.X.push_back(0);
        reverse(b.X.begin(), b.X.end());

        for (int i = 0; i <= dv; i++) {
            while (b < a) {
                a = a-b;
                res.X[dv-i]++;
            }
            b.X.erase(b.X.begin());
        }
        while (res.X.size() > 1 && res.X.back() == 0) res.X.pop_back();
        return res;
    }

    friend bool operator< (const Int &lhs, const Int &rhs) {
        if (lhs.size() < rhs.size()) return true;
        if (lhs.size() > rhs.size()) return false;

        if (vector<int>(lhs.X.rbegin(), lhs.X.rend()) <= vector<int>(rhs.X.rbegin(), rhs.X.rend())) return true;
        return false;
    }
    void out() {
        reverse(X.begin(), X.end());
        for (auto x : X) printf("%d", x);
        printf("\n");
    }
};

Int max_int(const Int &A, const Int &B) {
    if (A < B) return B;
    else return A;
}

状态哈希

在动态规划，图论问题中，经常需要进行状态压缩，对某个阶段进行状态编码
不妨设这个阶段的状态表示为 $A(u, c, \cdots)$
此时可以用 $\text{unordered map}$ 状态哈希，对压缩后的状态进行编码

int tot = 0;
unordered_map<A, int, hashfun, eqfun> mp;

inline int get(const A &cur) {
    return mp[cur] ? mp[cur] : (mp[cur] = ++tot);
}

具体来说，$\text{hashfun}$ 需要自己写，要注意避免哈希冲突，一般情况如下

class A {
public:
    int u, c;
    A(int u = 0, int c = 0) : u(u), c(c) {}
    bool operator< (const A &rhs) const {
        return u < rhs.u || (u == rhs.u && c < rhs.c);
    }
};

inline int Hash(const A &a) {
    return a.u * 1003 + a.c;
}

struct hashfun {
    int operator() (const A &a) const {
        return Hash(a);
    }
};

struct eqfun {
    bool operator() (const A &lhs, const A &rhs) const {
        return lhs.u == rhs.u && lhs.c == rhs.c;
    }
};

unordered_map<A, int, hashfun, eqfun> mp;
int tot = 0;

inline int get(const A &a) {
    return mp[a] ? mp[a] : (mp[a] = ++tot);
}

使用 lambda 表达式简化代码

[capture list] (parameter list) -> return type {function body}

捕获列表

有时候我们需要使用来自函数体之外的变量，此时需要用到捕获列表
来使用定义在函数体之外的变量，如果我们需要修改这个变量，用值捕获，否则用引用捕获

[=] 值捕获，[&]引用捕获

void biggies(vector<string> &words, vector<string>::size_type sz, 
             ostream &os = cout, char c = ' ')
{
    for_each(words.begin(), words.end(), 
        [&, c](const string &s) { os << s << c; });
    // os 隐式捕获，引用捕获，c 显式捕获，值捕获

    for_each(words.begin(), words.end(),
        [=, &os](const string &s) { os << s << c; });
    // c 隐式捕获，值捕获，os 显式捕获，引用捕获
}

混合使用显式捕获或是隐式捕获的时候，参数列表第一个必须是 [&], [=]

返回函数对象

function<int(int, int)> get = [](int i, int j) { return i * j; };

函数接收两个int类型的变量作为参数，返回一个int类型的变量

典型应用

比如用 kruskal 求最小生成树，需要用到并查集，并查集代码就可以作为 lambda 表达式来写

int pa[maxn];

void kruskal() {
    // ...
    function <int(int)> get = [&](int x) {
        return x == pa[x] ? x : pa[x] = get(pa[x]);
    } 

    for (int i = 1; i <= m; i++) {
        int x = get(e[i].u), y = get(e[i].v);
        if (x == y) continue;
        pa[x] = y;
    }
}

还有就是排序

deque<Person> coll;

sort(coll.begin(), coll.end(), 
    [] (const Person &p1, const Person &p2) {
        return p1.lastname() < p2.lastname() ||
               (p1.lastname() == p2.lastname() &&
                p1.firstname() < p2.firstname());
    });

状态压缩

$x$ 的 $k$ 位取反

x ^= (pow(2, k) - 1);

枚举 $x$ 所有的子集 $y$

x = (1<<k)-1;

for (int y = x; y; y = (y-1) & x) {
    y is subset of x
}