板子们

数据结构

线段树

单点修改,区间和

ll tree[maxn << 2];
void build(int l, int r, int v) { memset(tree, v, sizeof(tree)); }
void update(int root, int left, int right, int pos, int k) {
    if (pos < left || pos > right)
        return;
    if (left == right) {
        tree[root] += k;
        return;
    }
    int mid = (left + right) >> 1;
    update(lson, left, mid, pos, k);
    update(rson, mid + 1, right, pos, k);
    tree[root] = tree[lson] + tree[rson];
}

ll query(int root, int left, int right, int ql, int qr) {
    if (qr < left || ql > right)
        return 0;
    if (ql <= left && right <= qr)
        return tree[root];
    int mid = (left + right) >> 1;
    return query(lson, left, mid, ql, qr) + query(rson, mid + 1, right, ql, qr);
}
ll qu(int l, int r) { return query(1, 0, maxn, l, r); }
void up(int p, int k) { update(1, 0, maxn, p, k); }

树论

支配树

truct node {
    vector<int> e[maxn];
    inline void add(int u, int v) { e[u].push_back(v); }
} a, b, c, d;

int dfn[maxn], id[maxn], dfa[maxn], sdom[maxn], idom[maxn], fa[maxn],
    mindfn[maxn], cnt;

void dfs(int u) {
    dfn[u] = ++cnt;
    id[cnt] = u;
    for (int i : a.e[u]) {
        if (dfn[i]) {
            continue;
        }
        dfa[i] = u;
        dfs(i);
    }
}

int find(int x) {
    if (x == fa[x]) {
        return x;
    }
    int tmp = find(fa[x]);
    if (dfn[sdom[mindfn[fa[x]]]] < dfn[sdom[mindfn[x]]]) {
        mindfn[x] = mindfn[fa[x]];
    }
    return fa[x] = tmp;
}

void zp() {
    for (int i = cnt; i > 1; i--) {
        int u = id[i];
        for (int v : b.e[u]) {
            if (!dfn[v]) {
                continue;
            }
            find(v);
            if (dfn[sdom[mindfn[v]]] < dfn[sdom[u]]) {
                sdom[u] = sdom[mindfn[v]];
            }
        }
        c.add(sdom[u], u);
        fa[u] = dfa[u];
        u = fa[u];
        for (int v : c.e[u]) {
            find(v);
            sdom[mindfn[v]] == u ? idom[v] = u : idom[v] = mindfn[v];
        }
    }
    for (int i = 2; i <= cnt; i++) {
        int u = id[i];
        if (idom[u] != sdom[u]) {
            idom[u] = idom[idom[u]];
        }
    }
}

void zp_write(int n) {
    for (int i = 2; i <= n; i++) {
        d.add(idom[i], i);
    }
}

数学

快速乘,快速幂

ll qm(ll a, ll b, ll c) {
    long long ans = 0, res = a;
    while (b) {
        if (b & 1)
            ans = (ans + res) % c;
        res = (res + res) % c;
        b >>= 1;
    }
    return (ll)ans;
}
ll mul(ll a, ll b) { return (ll)(__int128(a) * b % MOD); }
ll qp(ll a, ll b, ll c) {
    ll ans = 1, res = a;
    while (b) {
        if (b & 1)
            ans = qm(ans, res, c);
        res = qm(res, res, c);
        b >>= 1;
    }
    return ans;
}

素数

//前置:快速乘,快速幂
//保证long long内结果准确
ll prime[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
bool Miller_Rabin(ll x) {
    ll i, j, k;
    ll s = 0, t = x - 1;
    if (x == 2)
        return true;
    if (x < 2 || !(x & 1))
        return false;
    while (!(t & 1)) {
        s++;
        t >>= 1;
    }
    for (i = 0; i < 6 && prime[i] < x; ++i) {
        ll a = prime[i];
        ll b = qp(a, t, x);
        for (j = 1; j <= s; ++j) {
            k = qm(b, b, x);
            if (k == 1 && b != 1 && b != x - 1)
                return false;
            b = k;
        }
        if (b != 1)
            return false;
    }
    return true;
}

逆元

ll modInverse(ll a, ll p) { return qp(a, p - 2ll, p); }

计算几何

极角排序

struct Vector {
    int x, y;
};
Vector pp[maxn], vc[maxn];

inline double dc(Vector a, Vector b) {
    return 1.0 * a.x * b.y - 1.0 * a.y * b.x;
}

inline int xs(Vector a) {
    if (a.x >= 0 && a.y > 0)
        return 1;
    if (a.x < 0 && a.y >= 0)
        return 2;
    if (a.x <= 0 && a.y < 0)
        return 3;
    if (a.x > 0 && a.y <= 0)
        return 4;
}

bool operator<(const Vector &a, const Vector &b) {
    Vector p1 = a;
    Vector p2 = b;
    int l1, l2;
    l1 = xs(p1);
    l2 = xs(p2);
    return l1 == l2 ? dc(a, b) > 0 ? 1 : 0 : l1 < l2;
}
comments powered by Disqus