OI
an hour read (About 7278 words)

模板整理

一些模板。

数学

gcd

1
2
3
4
template <typename T>
T gcd(T a, T b) {
    return !b ? a : gcd(b, a % b);
}

exgcd

1
2
3
4
5
6
7
8
9
template <typename T>
void exgcd(T a, T b, T &g, T &x, T &y) {
    !b ? (g = a, x = 1, y = 0) : (exgcd(b, a % b, g, y, x), y -= a / b * x);
}

template <typename T>
void exgcd(T a, T b, T &x, T &y) {
    !b ? (x = 1, y = 0) : (exgcd(b, a % b, y, x), y -= a / b * x);
}

线性不定方程

$ax + by = c$，若 $c \equiv 0 \pmod {\gcd(a, b)}$，则方程存在整数解，否则没有，这里给出一组特解。

1
2
3
4
5
6
7
8
9
10
template <typename T>
inline bool linearEquation(T a, T b, T c, T &x, T &y) {
    T g;
    exgcd(a, b, g, x, y);
    if (c % g) return false;
    T k = c / g;
    x *= k;
    y *= k;
    return true;
}

线性同余方程

$ax \equiv b \pmod c$；
转化为不定方程 $ax + cy = b$。

1
2
3
4
5
6
7
8
9
10
template <typename T>
inline bool modularLinearEquation(T a, T b, T c, T &x) {
    T g, y;
    exgcd(a, c, g, x, y);
    if (b % g) return false;
    x *= b / g;
    c /= g;
    x = (x % c + c) % c;
    return true;
}

快速幂

1
2
3
4
5
6
inline int modPow(int a, int b, int mod) {
    int ret = 1;
    for (; b; b >>= 1, a = (unsigned long long)a * a % mod)
        if (b & 1) ret = (unsigned long long)ret * a % mod;
    return ret;
}

快速乘

long long 乘 long long 模 long long。

1
2
3
inline long long mul(long long a, long long b, long long c) {
    return (a * b - (long long)((long double)a / c * b) * c + c) % c;
}

乘法逆元

快速幂

用费马小定理。

1
2
3
inline int inv(int x, int mod) {
    return modPow(x, mod - 2, mod);
}

exgcd

1
2
3
4
5
inline int inv(int v, int mod) {
    int x, y;
    exgcd(v, mod, x, y);
    return (x % mod + mod) % mod;
}

递推预处理

1
2
3
4
5
inline void init(int n) {
    inv[1] = 1;
    for (int i = 2; i <= n; i++)
        inv[i] = (MOD - (unsigned long long)MOD / i) * inv[MOD % i] % MOD;
}

预处理阶乘逆元

1
2
3
4
5
6
7
inline void init(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = (unsigned long long)fac[i - 1] * i % MOD;
    inv[n] = modPow(fac[n], MOD - 2);
    for (int i = n - 1; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1ull) % MOD;
}

中国剩余定理

基本形式

$x \equiv a_i \pmod {m_i}$。 $x = \sum\limits_{i}a_iM_i M_i ^ {-1} \pmod {M}, M = \prod a_i, M_i = M / m_i$，$M_i ^ {-1}$ 为 $M_i$ 模 $m_i$ 的逆元，$m_i$ 两两互质。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void exgcd(int a, int b, int &x, int &y) {
    !b ? (x = 1, y = 0) : (exgcd(b, a % b, y, x), y -= a / b * x);
}

inline int inv(int v, int mod) {
    int x, y;
    exgcd(v, mod, x, y);
    return (x % mod + mod) % mod;
}

inline int crt(int *a, int *m, int n) {
    int ret = 0, M = 1, mi;
    for (int i = 0; i < n; i++) M *= m[i];
    for (int i = 0; i < n; i++) {
        mi = M / m[i];
        ret = (ret + (long long)a[i] * mi % M * inv(mi, m[i])) % M;
    }
    return ret;
}

扩展

$m_i$ 不要求两两互质，此时只能两两用 exgcd 合并。
$z \equiv a \pmod b$
$z \equiv c \pmod d$
则
$z = bx + a = dy + c$
即
$bx - dy = c - a$
用 exgcd 求解即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <typename T>
void exgcd(T a, T b, T &g, T &x, T &y) {
    !b ? (g = a, x = 1, y = 0) : (exgcd(b, a % b, g, y, x), y -= a / b * x);
}

template <typename T>
inline T excrt(T *a, T *m, int n) {
    T ret = a[0], M = m[0], g, x, y, t;
    for (int i = 1; i < n; i++) {
        exgcd(M, m[i], g, x, y);
        if ((a[i] - ret) % g) return -1;
        t = m[i] / g;
        x = ((long long)x * (a[i] - ret) / g % t + t) % t;
        ret += x * M;
        M *= t;
        ret %= M;
    }
    return ret;
}

BSGS

求 $A ^ x \equiv B \pmod C$。
这里直接写 EXBSGS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }

template <typename T>
void exgcd(T a, T b, T &x, T &y) {
    !b ? (x = 1, y = 0) : (exgcd(b, a % b, y, x), y -= a / b * x);
}

template <typename T>
inline T inv(T v, T mod) {
    T x, y;
    exgcd(v, mod, x, y);
    return (x % mod + mod) % mod;
}

inline int bsgs(int a, int b, int c) {
    int cnt = 0, d = 1, g;
    while ((g = gcd(a, c)) != 1) {
        if (b % g) return -1;
        b /= g;
        c /= g;
        cnt++;
        d = (long long)d * (a / g) % c;
    }
    b = (long long)b * inv(d, c) % c;
    int s = sqrt((double)c), p = 1;
    std::map<int, int> h;
    for (int i = 0; i < s; i++) {
        if (p == b) return i + cnt;
        h[(long long)p * b % c] = i;
        p = (long long)p * a % c;
    }
    int q = p;
    for (int i = s; i - s + 1 <= c - 1; i += s) {
        std::map<int, int>::iterator it = h.find(q);
        if (it != h.end()) return i - it->second + cnt;
        q = (long long)q * p % c;
    }
    return -1;
}

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*
 * 线性筛
 * @param n n
 * @param p 素数
 * @param cnt 储存素数个数
 * @param vis 是否为合数
 * @param mu 莫比乌斯函数
 * @param phi 欧拉函数
 * @param idx 最小质因子指数
 * @param sigma0 约数个数
 * @param sigma1 约数和
 * @param mul 包含最小质因子的约数和
 * @complexity O(n)
 */
inline void linearSieve(int n, int *p, int &cnt, bool *vis, int *mu, int *phi,
                        int *idx, int *sigma0, int *sigma1, int *mul) {
    mu[1] = 1;
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            p[cnt++] = i;
            mu[i] = -1;
            phi[i] = i - 1;
            idx[i] = 1;
            sigma0[i] = 2;
            sigma1[i] = i + 1;
            mul[i] = i + 1;
        }
        for (int j = 0, k; j < cnt && (k = i * p[j]) <= n; j++) {
            vis[k] = true;
            if (i % p[j] == 0) {
                mu[k] = 0;
                phi[k] = phi[i] * p[j];
                idx[k] = idx[i] + 1;
                mul[k] = mul[i] * p[j] + 1;
                sigma0[k] = sigma0[i] / (idx[i] + 1) * (idx[i] + 2);
                sigma1[k] = sigma1[i] / mul[i] * mul[k];
                break;
            } else {
                idx[k] = 1;
                mu[k] = -mu[i];
                phi[k] = phi[i] * (p[j] - 1);
                sigma0[k] = sigma0[i] * 2;
                mul[k] = p[j] + 1;
                sigma1[k] = sigma1[i] * (p[j] + 1);
            }
        }
    }
}

组合数

预处理阶乘和逆元

1
2
3
inline int nCr(int n, int r, int *fac, int *inv, int mod) {
    return (long long)fac[n] * inv[r] % mod * inv[n - r] % mod;
}

递推

1
2
3
4
5
6
template <typename T, size_t size>
inline void initCombination(T c[size][size], int n) {
    for (int i = 1; i <= n; i++) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}

Lucas

1
2
3
int lucas(int n, int r) {
    return r == 0 ? 1 : (long long)nCr(n % p, r % p) * lucas(n / p, r / p) % p;
}

Pollard-Rho

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
inline unsigned long long gen() {
    static unsigned long long x = 495;
    x ^= x >> 12;
    x ^= x << 25;
    x ^= x >> 27;
    return x * 0x2545F4914F6CDD1Dull;
}

const int PRIME[] = {3, 5, 7, 11, 13, 17, 19, 23, 29};

inline long long mul(long long a, long long b, long long c) {
    return (a * b - (long long)((long double)a / c * b) * c + c) % c;
}

inline long long modPow(long long a, long long b, long long c) {
    long long ret = 1;
    for (; b; b >>= 1, a = mul(a, a, c))
        if (b & 1) ret = mul(ret, a, c);
    return ret;
}

long long gcd(long long a, long long b) { return !b ? a : gcd(b, a % b); }

inline long long add(long long x, long long v, long long mod) {
    return x + v >= mod ? x + v - mod : x + v;
}

inline bool witness(long long v, long long p) {
    long long r = p - 1, s = 0, x;
    for (; ~r & 1; r >>= 1) s++;
    x = modPow(v, r, p);
    if (x == 1 || x == p - 1) return false;
    while (s--)
        if ((x = mul(x, x, p)) == p - 1) return false;
    return true;
}

inline bool millerRabin(long long p) {
    if (p == 2) return true;
    if (p < 2 || !(p & 1)) return false;
    for (int i = 0; i < 9; i++) {
        if (p == PRIME[i]) return true;
        if (witness(PRIME[i], p)) return false;
    }
    return true;
}

inline long long pollardRho(long long n, long long c) {
    long long k = 2, x = gen() % n, y = x, p = 1;
    for (long long i = 1; p == 1; i++) {
        x = add(mul(x, x, n), c, n);
        p = gcd(n, std::abs(y - x));
        if (i == k) {
            y = x;
            k <<= 1;
        }
    }
    return p;
}

void getFac(long long n, std::vector<long long> &fac) {
    if (millerRabin(n)) {
        fac.push_back(n);
        return;
    }
    long long t = n;
    while (t == n) t = pollardRho(t, gen() % (n - 1));
    getFac(t, fac);
    getFac(n / t, fac);
}

高斯消元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <typename T, size_t size>
inline bool gaussJordan(T a[size][size], int n) {
    for (int i = 0, idx; idx = i, i < n; i++) {
        for (int j = i + 1; j < n; j++)
            if (std::abs(a[j][i]) > std::abs(a[idx][i])) idx = j;
        if (std::abs(a[idx][i]) < EPS) return false;
        if (idx != i) std::swap_ranges(a[i] + i, a[i] + n + 1, a[idx] + i);
        for (int j = 0; j < n; j++)
            if (i != j)
                for (int k = n; k >= i; k--)
                    a[j][k] -= a[i][k] / a[i][i] * a[j][i];
    }
    for (int i = 0; i < n; i++) a[i][n] /= a[i][i];
    return true;
}

单纯形

随机初始化，过不了 Extra Test。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
const int MAXN = 25;
const int MAXM = 25;
const double INF = 1e15;
const double EPS = 1e-7;

// a[约束][变量]
double a[MAXM][MAXN], ans[MAXN];
int id[MAXN + MAXM], q[MAXN], n, m, t;

inline unsigned int gen() {
    static unsigned int x = 495;
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

inline void pivot(int l, int e) {
    std::swap(id[l + n], id[e]);
    double t = a[l][e];
    a[l][e] = 1;
    for (int i = 0; i <= n; i++) a[l][i] /= t;
    int p = 0;
    for (int i = 0; i <= n; i++)
        if (std::abs(a[l][i]) > EPS) q[++p] = i;
    for (int i = 0; i <= m; i++) {
        if (i != l && std::abs(a[i][e]) > EPS) {
            t = a[i][e];
            a[i][e] = 0;
            for (int j = 1; j <= p; j++) a[i][q[j]] -= t * a[l][q[j]];
        }
    }
}

inline bool init() {
    for (;;) {
        int l = 0, e = 0;
        for (int i = 1; i <= m; i++) {
            if (a[i][0] < -EPS && (!l || (gen() & 1))) {
                l = i;
            }
        }
        if (!l) break;
        for (int i = 1; i <= n; i++) {
            if (a[l][i] < -EPS && (!e || (gen() & 1))) {
                e = i;
            }
        }
        if (!e) {
            puts("Infeasible");
            return false;
        }
        pivot(l, e);
    }
    return true;
}

inline bool simplex() {
    for (;;) {
        int l = 0, e = 0;
        double min = INF;
        for (int i = 1; i <= n; i++) {
            if (a[0][i] > EPS) {
                e = i;
                break;
            }
        }
        if (!e) break;
        for (int i = 1; i <= m; i++) {
            if (a[i][e] > EPS && a[i][0] / a[i][e] < min) {
                l = i;
                min = a[i][0] / a[i][e];
            }
        }
        if (!l) {
            puts("Unbounded");
            return false;
        }
        pivot(l, e);
    }
    return true;
}

int main() {
    std::cin >> n >> m >> t;
    for (int i = 1; i <= n; i++) std::cin >> a[0][i];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) std::cin >> a[i][j];
        std::cin >> a[i][0];
    }
    for (int i = 0; i <= n; i++) id[i] = i;
    if (init() && simplex()) {
        printf("%.8f\n", -a[0][0]);
        if (t) {
            for (int i = 1; i <= m; i++) ans[id[n + i]] = a[i][0];
            for (register int i = 1; i <= n; i++) printf("%.8f ", ans[i]);
        }
    }
}

扩展埃筛

SuperOJ 1297

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>

const int MOD = 1e9 + 7;

typedef unsigned long long H;

inline int add(int x, int v) { return x + v >= MOD ? x + v - MOD : x + v; }

inline int dec(int x, int v) { return x - v < 0 ? x - v + MOD : x - v; }

int n, d, M;
std::vector<int> pre[2], suc[2], pr;

int rec(int res, int last, int mul) {
    int t = dec(res > M ? suc[1][n / res] : pre[1][res], pre[1][pr[last] - 1]);
    int ret = (H)t * mul % MOD;
    for (int i = last, p; i < (int)pr.size(); i++) {
        p = pr[i];
        if (p * p > res) break;
        for (int q = p, nres = res, nmul = mul * ((H)p + d) % MOD, pk = p;
             (H)p * q <= (H)res; q *= p) {
            ret = add(ret, rec(nres /= p, i + 1, nmul));
            pk = (H)pk * p % MOD;
            nmul = mul * ((H)pk + d) % MOD;
            ret = add(ret, nmul);
        }
    }
    return ret;
}

inline int solve() {
    M = sqrt(n);
    pr.reserve(M + 1);
    pre[0].resize(M + 1);
    pre[1].resize(M + 1);
    suc[0].resize(M + 1);
    suc[1].resize(M + 1);
    for (int i = 1, t; i <= M; i++) {
        pre[0][i] = i - 1;
        pre[1][i] = (i * (i + 1ull) / 2 - 1) % MOD;
        t = n / i;
        suc[0][i] = t - 1;
        suc[1][i] = (t * (t + 1ull) / 2 + MOD - 1) % MOD;
    }
    for (int p = 2; p <= M; p++) {
        if (pre[0][p] == pre[0][p - 1]) continue;
        pr.push_back(p);
        const int q = p * p, m = n / p;
        const int pcnt = pre[0][p - 1], psum = pre[1][p - 1];
        const int end = std::min(M, n / q);
        for (int i = 1, w = M / p; i <= w; i++) {
            suc[0][i] = dec(suc[0][i], dec(suc[0][i * p], pcnt));
            suc[1][i] = dec(suc[1][i], (H)dec(suc[1][i * p], psum) * p % MOD);
        }
        for (int i = M / p + 1; i <= end; i++) {
            suc[0][i] = dec(suc[0][i], dec(pre[0][m / i], pcnt));
            suc[1][i] = dec(suc[1][i], (H)dec(pre[1][m / i], psum) * p % MOD);
        }
        for (int i = M; i >= q; i--) {
            pre[0][i] = dec(pre[0][i], dec(pre[0][i / p], pcnt));
            pre[1][i] = dec(pre[1][i], (H)dec(pre[1][i / p], psum) * p % MOD);
        }
    }
    pr.push_back(M + 1);
    for (int i = 1; i <= M; i++) {
        pre[1][i] = (pre[1][i] + (H)d * pre[0][i]) % MOD;
        suc[1][i] = (suc[1][i] + (H)d * suc[0][i]) % MOD;
    }
    return n > 1 ? 1 + rec(n, 0, 1) : 1;
}

int main() {
    // freopen("sample/1.in", "r", stdin);
    std::cin >> n >> d;
    std::cout << solve();
}

线性基

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
unsigned char logs[256];

inline void init() {
    for (int i = 2; i < 256; i++) logs[i] = logs[i >> 1] + 1;
}

inline int logv(unsigned int v) {
    if (v >> 16) return (v >> 24) ? 24 + logs[v >> 24] : 16 + logs[v >> 16];
    return (v >> 8) ? 8 + logs[v >> 8] : logs[v];
}

const int MAXA = 31;

struct LinearBasis {
    unsigned int a[MAXA];

    inline void insert(unsigned int v) {
        for (int i; v;) {
            if (a[i = logv(v)]) {
                v ^= a[i];
            } else {
                a[i] = v;
                break;
            }
        }
    }
};

字符串

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline void get(char *s, int *f, int n) {
    for (int i = 1, j = 0; i < n; i++) {
        while (j && s[i] != s[j]) j = f[j - 1];
        if (s[i] == s[j]) j++;
        f[i] = j;
    }
}

inline bool kmp(char *s, char *t, int n, int m) {
    get(t, f, m);
    bool flag = false;
    for (int i = 0, j = 0; i < n; i++) {
        while (j && s[i] != t[j]) j = f[j - 1];
        if (s[i] == t[j]) j++;
        if (j == m) {
            flag = true;
            std::cout << i - m + 2 << '\n';
        }
    }
    return flag;
}

后缀数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
const int MAXN = 50000 + 9;

int sa[MAXN], ht[MAXN], rk[MAXN];
bool t[MAXN * 2 + 1];

inline bool islms(const int i, const bool *t) {
    return i > 0 && t[i] && !t[i - 1];
}

template <typename T>
inline void sort(T s, int *sa, const int len, const int sz, const int sigma,
                 bool *t, int *b, int *cb, int *p) {
    memset(b, 0, sizeof(int) * sigma);
    memset(sa, -1, sizeof(int) * len);
    for (int i = 0; i < len; i++) b[s[i]]++;
    cb[0] = b[0];
    for (int i = 1; i < sigma; i++) cb[i] = cb[i - 1] + b[i];
    for (int i = sz - 1; i >= 0; i--) sa[--cb[s[p[i]]]] = p[i];
    for (int i = 1; i < sigma; i++) cb[i] = cb[i - 1] + b[i - 1];
    for (int i = 0; i < len; i++)
        if (sa[i] > 0 && !t[sa[i] - 1]) sa[cb[s[sa[i] - 1]]++] = sa[i] - 1;
    cb[0] = b[0];
    for (int i = 1; i < sigma; i++) cb[i] = cb[i - 1] + b[i];
    for (int i = len - 1; i >= 0; i--)
        if (sa[i] > 0 && t[sa[i] - 1]) sa[--cb[s[sa[i] - 1]]] = sa[i] - 1;
}

template <typename T>
void sais(T s, int *sa, const int len, bool *t, int *b, int *b1,
          const int sigma) {
    int i, j, x, p = -1, cnt = 0, sz = 0, *cb = b + sigma;
    for (t[len - 1] = 1, i = len - 2; i >= 0; i--)
        t[i] = s[i] < s[i + 1] || (s[i] == s[i + 1] && t[i + 1]);
    for (i = 1; i < len; i++)
        if (t[i] && !t[i - 1]) b1[sz++] = i;
    sort(s, sa, len, sz, sigma, t, b, cb, b1);
    for (i = sz = 0; i < len; i++)
        if (islms(sa[i], t)) sa[sz++] = sa[i];
    for (i = sz; i < len; i++) sa[i] = -1;
    for (i = 0; i < sz; i++) {
        for (j = 0, x = sa[i]; j < len; j++) {
            if (p == -1 || s[x + j] != s[p + j] || t[x + j] != t[p + j]) {
                p = x;
                cnt++;
                break;
            } else if (j > 0 && (islms(x + j, t) || islms(p + j, t))) {
                break;
            }
        }
        sa[sz + (x >>= 1)] = cnt - 1;
    }
    for (i = j = len - 1; i >= sz; i--)
        if (sa[i] >= 0) sa[j--] = sa[i];
    int *s1 = sa + len - sz, *b2 = b1 + sz;
    if (cnt < sz)
        sais(s1, sa, sz, t + len, b, b1 + sz, cnt);
    else
        for (i = 0; i < sz; i++) sa[s1[i]] = i;
    for (i = 0; i < sz; i++) b2[i] = b1[sa[i]];
    sort(s, sa, len, sz, sigma, t, b, cb, b2);
}

template <typename T>
inline void getHeight(T s, const int n, int *sa, int *rk, int *ht) {
    for (int i = 1; i <= n; i++) rk[sa[i]] = i;
    for (int i = 0, j = 0, k = 0; i < n; ht[rk[i++]] = k)
        for (k ? k-- : 0, j = sa[rk[i] - 1]; s[i + k] == s[j + k]; k++)
            ;
}

AC 自动机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
char *cur;

struct Node *null;

struct Node {
    static const int NODE_SIZE;
    Node *c[SIGMA], *fail;

    Node() : fail(null) {
        for (int i = 0; i < SIGMA; i++) c[i] = null;
    }

    inline void *operator new(size_t) { return cur += NODE_SIZE; }
};

const int Node::NODE_SIZE = sizeof(Node);

char pool[MAXM * Node::NODE_SIZE];

Node *root;

inline Node *insert(const char *s) {
    Node *p = root;
    for (int idx; *s; s++) {
        if (p->c[idx = *s - 'a'] == null) p->c[idx] = new Node;
        p = p->c[idx];
    }
    return p;
}

Node *q[MAXM];

inline void build() {
    int qh = 0, qt = 0;
    q[qt++] = root;
    for (Node *p, *u; qh < qt;) {
        p = q[qh++];
        for (int i = 0; i < SIGMA; i++) {
            if (p->c[i] != null) {
                for (u = p->fail; u->c[i] == null;) u = u->fail;
                p->c[i]->fail = u->c[i];
                q[qt++] = p->c[i];
            } else {
                p->c[i] = p->fail->c[i];
            }
        }
    }
}

inline void init() {
    null = (Node *)pool;
    cur = pool;
    null->fail = null;
    root = new Node;
    for (int i = 0; i < SIGMA; i++) null->c[i] = root;
}

Manacher

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int p[MAXN * 2 + 1];
char s[MAXN * 2 + 1];

inline int manacher(char *t, int len) {
    int max = 0, pos = 0, n = 0, x = 0;
    s[0] = '$';
    for (int i = 0; i < len; i++) {
        s[++n] = '#';
        s[++n] = t[i];
    }
    s[++n] = '#';
    s[n + 1] = '\0';
    for (int i = 1; i <= n; i++) {
        x = max > i ? std::min(p[pos * 2 - i], max - i) : 1;
        while (s[i - x] == s[i + x]) x++;
        if (i + x > max) {
            max = i + x;
            pos = i;
        }
        p[i] = x;
    }
    return *std::max_element(p + 1, p + n + 1) - 1;
}

回文自动机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
struct PalindromicAutomation {
    enum { even, odd };

    int c[MAXN][SIGMA], fail[MAXN], len[MAXN], cnt[MAXN];

    int n, cur, last;
    char s[MAXN];

    PalindromicAutomation() {
        odd[fail] = even[fail] = odd;
        odd[len] = -1;
        s[n = 0] = -1;
        cur = 2;
        last = odd;
    }

    inline int get(int p) {
        while (s[n - p[len] - 1] != s[n]) p = p[fail];
        return p;
    }

    inline void extend(int x) {
        s[++n] = x;
        int &p = last;
        p = get(p);
        if (!p[c][x]) {
            int np = cur++;
            np[len] = p[len] + 2;
            np[fail] = get(p[fail])[c][x];
            p[c][x] = np;
        }
        p = p[c][x];
        p[cnt]++;
    }

    inline void count() {
        for (int i = cur - 1; i; i--) {
            i[fail][cnt] += i[cnt];
        }
    }
};

支持两端插入

HDU 5421

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
const int MAXN = 100000 * 2 + 9;
const int SIGMA = 26;

struct PalindromicAutomation {
    enum { even, odd };
    int c[MAXN][SIGMA], fail[MAXN], len[MAXN], endPos[MAXN];

    long long endPosSize;
    char s[MAXN];
    int l, r, cur, last[2];

    inline void init() {
        memset(s, -1, sizeof(s));
        memset(c, 0, sizeof(c));
        memset(fail, 0, sizeof(fail));
        memset(len, 0, sizeof(len));
        memset(endPos, 0, sizeof(endPos));
        odd[fail] = even[fail] = odd;
        odd[len] = -1;
        l = MAXN / 2;
        r = l - 1;
        cur = 2;
        endPosSize = 0;
        last[0] = last[1] = even;
    }

    inline int getL(int p) {
        while (s[l + p[len] + 1] != s[l]) p = p[fail];
        return p;
    }

    inline int getR(int p) {
        while (s[r - p[len] - 1] != s[r]) p = p[fail];
        return p;
    }

    inline void extendR(int x) {
        s[++r] = x;
        int &p = last[1];
        p = getR(p);
        if (!p[c][x]) {
            int np = cur++;
            np[len] = p[len] + 2;
            np[fail] = getR(p[fail])[c][x];
            np[endPos] = np[fail][endPos] + 1;
            p[c][x] = np;
        }
        p = p[c][x];
        endPosSize += p[endPos];
        if (r - l + 1 == p[len]) last[0] = p;
    }

    inline void extendL(int x) {
        s[--l] = x;
        int &p = last[0];
        p = getL(p);
        if (!p[c][x]) {
            int np = cur++;
            np[len] = p[len] + 2;
            np[fail] = getL(p[fail])[c][x];
            np[endPos] = np[fail][endPos] + 1;
            p[c][x] = np;
        }
        p = p[c][x];
        endPosSize += p[endPos];
        if (r - l + 1 == p[len]) last[1] = p;
    }
};

数据结构

带撤销并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int fa[MAXN];

struct Node {
    int u, v, fu, fv;

    Node(int u, int v, int fu, int fv) : u(u), v(v), fu(fu), fv(fv) {}
};

std::vector<Node> st;

inline void init(int n) { memset(fa, -1, sizeof(int) * (n + 1)); }

inline int get(int x) {
    while (fa[x] >= 0) x = fa[x];
    return x;
}

inline void put(int u, int v) {
    if ((u = get(u)) != (v = get(v))) {
        st.push_back(Node(u, v, fa[u], fa[v]));
        if (fa[u] > fa[v]) std::swap(u, v);
        fa[u] += fa[v];
        fa[v] = u;
    }
}

inline void undo(int x) {
    while ((int)st.size() > x) {
        fa[st.back().u] = st.back().fu;
        fa[st.back().v] = st.back().fv;
        st.pop_back();
    }
}

Treap

按权值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
const int MAXN = 300000 + 9;

inline unsigned int gen() {
    static unsigned int x = 495;
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

char *cur;

struct Node *null;

struct Node {
    static const int NODE_SIZE;
    Node *lc, *rc;
    unsigned int rk;
    int val, size;

    Node(int val) : lc(null), rc(null), rk(gen()), val(val), size(1) {}

    inline void maintain() { size = lc->size + rc->size + 1; }

    inline void *operator new(size_t) { return cur += NODE_SIZE; }
};

const int Node::NODE_SIZE = sizeof(Node);

char pool[MAXN * Node::NODE_SIZE];

Node *root;

Node *merge(Node *u, Node *v) {
    if (u == null) return v;
    if (v == null) return u;
    if (u->rk < v->rk) {
        u->rc = merge(u->rc, v);
        u->maintain();
        return u;
    } else {
        v->lc = merge(u, v->lc);
        v->maintain();
        return v;
    }
}

void split(Node *p, int v, Node *&l, Node *&r) {
    if (p == null) return (void)(l = r = null);
    if (v <= p->val) {
        split(p->lc, v, l, r);
        p->lc = r;
        r = p;
    } else {
        split(p->rc, v, l, r);
        p->rc = l;
        l = p;
    }
    p->maintain();
}

inline void insert(int v) {
    Node *l, *r;
    split(root, v, l, r);
    root = merge(l, merge(new Node(v), r));
}

inline void erase(int v) {
    Node *l, *r, *L, *R;
    split(root, v, l, r);
    split(r, v + 1, L, R);
    root = merge(merge(l, L->lc), merge(L->rc, R));
}

inline Node *select(int k) {
    Node *p = root;
    for (; p != null && p->lc->size + 1 != k;) {
        if (k <= p->lc->size) {
            p = p->lc;
        } else {
            k -= p->lc->size + 1;
            p = p->rc;
        }
    }
    return p;
}

inline int lowerRank(int v) {
    int ret = 0;
    for (Node *p = root; p != null;) {
        if (v <= p->val) {
            p = p->lc;
        } else {
            ret += p->lc->size + 1;
            p = p->rc;
        }
    }
    return ret;
}

inline int upperRank(int v) {
    int ret = 0;
    for (Node *p = root; p != null;) {
        if (v < p->val) {
            p = p->lc;
        } else {
            ret += p->lc->size + 1;
            p = p->rc;
        }
    }
    return ret;
}

按大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

const int MAXN = 300000 + 9;

inline unsigned int gen() {
    static unsigned int x = 495;
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

char *cur;

struct Node *null;

struct Node {
    static const int NODE_SIZE;
    Node *lc, *rc;
    unsigned int rk;
    int val, size;

    Node(int val) : lc(null), rc(null), rk(gen()), val(val), size(1) {}

    inline void maintain() { size = lc->size + rc->size + 1; }

    inline void *operator new(size_t) { return cur += NODE_SIZE; }
};

const int Node::NODE_SIZE = sizeof(Node);

char pool[MAXN * Node::NODE_SIZE];

Node *root;

Node *merge(Node *u, Node *v) {
    if (u == null) return v;
    if (v == null) return u;
    if (u->rk < v->rk) {
        u->rc = merge(u->rc, v);
        u->maintain();
        return u;
    } else {
        v->lc = merge(u, v->lc);
        v->maintain();
        return v;
    }
}

void split(Node *p, int k, Node *&l, Node *&r) {
    if (p == null) return (void)(l = r = null);
    if (k <= p->lc->size) {
        split(p->lc, k, l, r);
        p->lc = r;
        r = p;
    } else {
        split(p->rc, k - p->lc->size - 1, l, r);
        p->rc = l;
        l = p;
    }
    p->maintain();
}

inline int lowerRank(int v) {
    int ret = 0;
    for (Node *p = root; p != null;) {
        if (v <= p->val) {
            p = p->lc;
        } else {
            ret += p->lc->size + 1;
            p = p->rc;
        }
    }
    return ret;
}

inline int upperRank(int v) {
    int ret = 0;
    for (Node *p = root; p != null;) {
        if (v < p->val) {
            p = p->lc;
        } else {
            ret += p->lc->size + 1;
            p = p->rc;
        }
    }
    return ret;
}

inline Node *select(int k) {
    Node *p = root;
    for (; p != null && p->lc->size + 1 != k;) {
        if (k <= p->lc->size) {
            p = p->lc;
        } else {
            k -= p->lc->size + 1;
            p = p->rc;
        }
    }
    return p;
}

inline void insert(int v) {
    int k = lowerRank(v);
    Node *l, *r;
    split(root, k, l, r);
    root = merge(l, merge(new Node(v), r));
}

inline void erase(int v) {
    int k = lowerRank(v);
    Node *l, *r, *L, *R;
    split(root, k, l, r);
    split(r, 1, L, R);
    root = merge(l, R);
}

pb_ds tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>

typedef __gnu_pbds::tree<
    std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >,
    __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>
    RedBlackTree;

typedef __gnu_pbds::gp_hash_table<int, int> HashMap;

RedBlackTree d;
HashMap h;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    int n;
    std::cin >> n;
    for (int cmd, x; n--;) {
        std::cin >> cmd >> x;
        switch (cmd) {
            case 0: {
                d.insert(std::make_pair(x, ++h[x]));
                break;
            }
            case 1: {
                d.erase(std::make_pair(x, h[x]--));
                break;
            }
            case 2: {
                std::cout << d.find_by_order(x - 1)->first << '\n';
                break;
            }
            case 3: {
                std::cout << d.order_of_key(std::make_pair(x, 0)) << '\n';
                break;
            }
            case 4: {
                RedBlackTree::iterator it = d.lower_bound(std::make_pair(x, 0));
                if (it == d.begin()) {
                    std::cout << "-1\n";
                } else {
                    std::cout << (--it)->first << '\n';
                }
                break;
            }
            case 5: {
                RedBlackTree::iterator it =
                    d.upper_bound(std::make_pair(x, INT_MAX));
                if (it == d.end()) {
                    std::cout << "-1\n";
                } else {
                    std::cout << it->first << '\n';
                }
                break;
            }
        }
    }
}

可并堆

随机堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
inline unsigned int gen() {
    static unsigned int x = 495;
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

char *cur;

struct Node *null;

struct Node {
    static const int NODE_SIZE;
    Node *lc, *rc;
    int val;

    Node(int val) : lc(null), rc(null), val(val) {}

    inline void *operator new(size_t) { return cur += NODE_SIZE; }
};

const int Node::NODE_SIZE = sizeof(Node);

char pool[MAXN * Node::NODE_SIZE];

Node *merge(Node *u, Node *v) {
    if (u == null) return v;
    if (v == null) return u;
    if (u->val > v->val) std::swap(u, v);
    if (gen() & 1)
        u->lc = merge(u->lc, v);
    else
        u->rc = merge(u->rc, v);
    return u;
}

Node *root;

inline int pop() {
    int t = root->val;
    root = merge(root->lc, root->rc);
    return t;
}

inline void push(int val) { root = merge(root, new Node(val)); }

树链剖分

BZOJ 1036

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>

const int MAXN = 30000 + 9;
const int MAXM = 32768 * 2 + 1;

std::vector<int> g[MAXN];

typedef std::vector<int>::iterator Iterator;

inline void addEdge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}

int sz[MAXN], fa[MAXN], son[MAXN], dep[MAXN];
int top[MAXN], pos[MAXN], idx;
bool vis[MAXN];

void dfs1(int u) {
    vis[u] = true;
    dep[u] = dep[fa[u]] + 1;
    sz[u] = 1;
    for (Iterator p = g[u].begin(); p != g[u].end(); ++p) {
        if (!vis[*p]) {
            fa[*p] = u;
            dfs1(*p);
            if (sz[*p] > sz[son[u]]) son[u] = *p;
            sz[u] += sz[*p];
        }
    }
}

void dfs2(int u) {
    vis[u] = false;
    pos[u] = ++idx;
    top[u] = (u == son[fa[u]] ? top[fa[u]] : u);
    if (son[u]) dfs2(son[u]);
    for (Iterator p = g[u].begin(); p != g[u].end(); ++p)
        if (vis[*p]) dfs2(*p);
}

int M, sum[MAXM], max[MAXM];

inline void maintain(int k) {
    k[sum] = (k << 1)[sum] + (k << 1 | 1)[sum];
    k[max] = std::max((k << 1)[max], (k << 1 | 1)[max]);
}

inline void modify(int k, int v) {
    k += M;
    k[sum] = k[max] = v;
    for (k >>= 1; k; k >>= 1) maintain(k);
}

inline int querySum(int s, int t) {
    int ret = 0;
    for (s += M - 1, t += M + 1; s ^ t ^ 1; s >>= 1, t >>= 1) {
        if (~s & 1) ret += (s ^ 1)[sum];
        if (t & 1) ret += (t ^ 1)[sum];
    }
    return ret;
}

inline int queryMax(int s, int t) {
    int ret = INT_MIN;
    for (s += M - 1, t += M + 1; s ^ t ^ 1; s >>= 1, t >>= 1) {
        if (~s & 1) ret = std::max(ret, (s ^ 1)[max]);
        if (t & 1) ret = std::max(ret, (t ^ 1)[max]);
    }
    return ret;
}

inline int queryTreeSum(int u, int v) {
    int ret = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
        ret += querySum(pos[top[u]], pos[u]);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) std::swap(u, v);
    return ret + querySum(pos[v], pos[u]);
}

inline int queryTreeMax(int u, int v) {
    int ret = INT_MIN;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
        ret = std::max(ret, queryMax(pos[top[u]], pos[u]));
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) std::swap(u, v);
    return std::max(ret, queryMax(pos[v], pos[u]));
}

char cmd[13];

int main() {
    // freopen("sample/1.in", "r", stdin);
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    int n;
    std::cin >> n;
    for (int i = 1, u, v; i < n; i++) {
        std::cin >> u >> v;
        addEdge(u, v);
    }
    dfs1(1);
    dfs2(1);
    for (M = 1; M < n + 2;) M <<= 1;
    for (int i = 1, w; i <= n; i++) {
        std::cin >> w;
        sum[pos[i] + M] = max[pos[i] + M] = w;
    }
    for (int i = M - 1; i; i--) maintain(i);
    int q;
    std::cin >> q;
    for (int u, v; q--;) {
        std::cin >> cmd;
        std::cin >> u >> v;
        switch (cmd[1]) {
            case 'H': {
                modify(pos[u], v);
                break;
            }
            case 'M': {
                std::cout << queryTreeMax(u, v) << '\n';
                break;
            }
            case 'S': {
                std::cout << queryTreeSum(u, v) << '\n';
                break;
            }
        }
    }
    return 0;
}

BZOJ 1036

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include <bits/stdc++.h>

const int MAXN = 30000 + 9;

struct Node *null;

struct Node {
    Node *c[2], *fa, *top;
    int rev, val, sum, max;

    inline int relation() { return fa->c[1] == this; }

    inline void reverse() {
        rev ^= 1;
        std::swap(c[0], c[1]);
    }

    inline void pushDown() {
        if (rev) {
            c[0]->reverse();
            c[1]->reverse();
            rev = 0;
        }
    }

    inline void maintain() {
        sum = val + c[0]->sum + c[1]->sum;
        max = std::max(val, std::max(c[0]->max, c[1]->max));
    }

    inline void rotate(int f) {
        Node *o = fa;
        top = o->top;
        o->pushDown();
        pushDown();
        (fa = o->fa)->c[o->relation()] = this;
        (o->c[f] = c[!f])->fa = o;
        (c[!f] = o)->fa = this;
        o->maintain();
    }

    inline void splay() {
        int f;
        for (pushDown(); fa != null;) {
            f = relation();
            if (fa->fa == null) {
                rotate(f);
            } else if (f == fa->relation()) {
                fa->rotate(f);
                rotate(f);
            } else {
                rotate(f);
                rotate(!f);
            }
        }
        maintain();
    }

    inline void expose() {
        splay();
        if (c[1] != null) {
            c[1]->top = this;
            c[1]->fa = null;
            c[1] = null;
            maintain();
        }
    }

    inline bool splice() {
        splay();
        if (top == null) return false;
        top->expose();
        top->c[1] = this;
        fa = top;
        top = null;
        fa->maintain();
        return true;
    }

    inline void access() {
        for (expose(); splice();)
            ;
    }

    inline void evert() {
        access();
        splay();
        reverse();
    }

    inline void init(int v) {
        val = sum = max = v;
        c[0] = c[1] = fa = top = null;
    }
} pool[MAXN];

inline void link(int x, int y) {
    Node *u = pool + x, *v = pool + y;
    u->evert();
    u->top = v;
}

inline void cut(int x, int y) {
    Node *u = pool + x, *v = pool + y;
    u->expose();
    v->expose();
    if (u->top == v) u->top = null;
    if (v->top == u) v->top = null;
}

inline Node *split(int x, int y) {
    Node *u = pool + x, *v = pool + y;
    v->evert();
    u->access();
    u->splay();
    return u;
}

inline void update(int x, int v) {
    Node *u = pool + x;
    u->splay();
    u->val = v;
    u->maintain();
}

inline void init(int u, int val) { pool[u].init(val); }

char cmd[13];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    null = pool;
    null->c[0] = null->c[1] = null->fa = null->top = null;
    null->max = -0x3f3f3f3f;
    null->sum = 0;
    null->val = 0;
    int n;
    std::cin >> n;
    std::vector<std::pair<int, int> > g;
    g.resize(n - 1);
    for (int i = 0; i < n - 1; i++) std::cin >> g[i].first >> g[i].second;
    for (int i = 1, w; i <= n; i++) {
        std::cin >> w;
        init(i, w);
    }
    for (int i = 0; i < n - 1; i++) link(g[i].first, g[i].second);
    int q;
    std::cin >> q;
    for (int u, v; q--;) {
        std::cin >> cmd >> u >> v;
        switch (cmd[1]) {
            case 'H': {
                update(u, v);
                break;
            }
            case 'M': {
                std::cout << split(u, v)->max << '\n';
                break;
            }
            case 'S': {
                std::cout << split(u, v)->sum << '\n';
                break;
            }
        }
    }
    return 0;
}

LCT 求 LCA

1
2
3
4
5
6
7
8
9
10
inline int lca(int x, int y) {
    Node *u = pool + x, *v = pool + y;
    u->access();
    v->splay();
    if (v->top == null) return v - pool;
    v->access();
    u->splay();
    if (u->top == null) return u - pool;
    return u->top - pool;
}

虚树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
inline bool cmp(int u, int v) {
    return dfn[u] < dfn[v];
}

inline int build(int *p, int n) {
    std::sort(p, p + n, cmp);
    static int st[MAXN * 2 + 1];
    int top = 0, cnt = 0;
    for (int i = 0; i < n; i++)
        if (lca(p[i], p[cnt]) != p[cnt]) p[++cnt] = p[i];
    n = ++cnt;
    st[top++] = p[cnt++] = 1;
    for (int i = 0, u, l; i < n; i++) {
        l = lca(u = p[i], st[top - 1]);
        if (u == l) {
            st[top++] = u;
        } else {
            while (top > 1 && dep[st[top - 2]] >= dep[l]) {
                addEdge(st[top - 2], st[top - 1]);
                top--;
            }
            if (st[top - 1] != l) {
                addEdge(l, st[--top]);
                st[top++] = p[cnt++] = l;
            }
            st[top++] = u;
        }
    }
    for (int i = 0; i < top - 1; i++) addEdge(st[i], st[i + 1]);
    return cnt;
}

图论

最大流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
struct Maxflow {
    struct Node {
        int v, f, i;

        Node(int v, int f, int i) : v(v), f(f), i(i) {}
    };

    std::vector<Node> g[MAXN];
    int s, t, n, iter[MAXN], h[MAXN], gap[MAXN];

    inline void addEdge(int u, int v, int f) {
        g[u].push_back(Node(v, f, g[v].size()));
        g[v].push_back(Node(u, 0, g[u].size() - 1));
    }

    int dfs(int u, int flow) {
        if (u == t) return flow;
        int ret = 0;
        for (int &i = iter[u]; i < (int)g[u].size(); i++) {
            Node &p = g[u][i];
            if (p.f > 0 && h[u] > h[p.v]) {
                int df = dfs(p.v, std::min(flow - ret, p.f));
                p.f -= df;
                g[p.v][p.i].f += df;
                if ((ret += df) == flow || h[s] >= n) return ret;
            }
        }
        if (--gap[h[u]] == 0) h[s] = n;
        gap[++h[u]]++;
        iter[u] = 0;
        return ret;
    }

    inline int maxflow(int s, int t) {
        this->s = s;
        this->t = t;
        int ret = 0;
        memset(h, 0, sizeof(int) * n);
        memset(gap, 0, sizeof(int) * n);
        for (gap[0] = n; h[s] < n;) {
            memset(iter, 0, sizeof(int) * n);
            ret += dfs(s, INF);
        }
        return ret;
    }
};

费用流

dijkstra 的就是维护 $h$ 和 $d$，每次更新时 $w = d[u] + p.w + h[u] - h[p.v]$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

const int MAXN = 400 + 9;
const int INF = 0x3f3f3f3f;

template <typename T>
inline bool tense(T &x, const T v) {
    return (x > v) ? (x = v, true) : false;
}

struct Costflow {
    struct Node {
        int v, f, w, i;
        Node(int v, int f, int w, int i) : v(v), f(f), w(w), i(i) {}
    };

    std::vector<Node> g[MAXN];

    typedef std::vector<Node>::iterator Iterator;

    int s, t, n, iter[MAXN], que[MAXN * 3], h[MAXN];
    bool vis[MAXN];

    inline void addEdge(int u, int v, int f, int w) {
        g[u].push_back(Node(v, f, w, g[v].size()));
        g[v].push_back(Node(u, 0, -w, g[u].size() - 1));
    }

    inline void bellmanFord() {
        memset(h, 0x3f, sizeof(int) * (n + 1));
        int qh = 0, qt = 0;
        h[que[qt++] = s] = 0;
        for (int u; qh < qt;) {
            vis[u = que[qh++]] = false;
            for (Iterator p = g[u].begin(); p != g[u].end(); ++p)
                if (p->f > 0 && tense(h[p->v], h[u] + p->w) && !vis[p->v])
                    vis[que[qt++] = p->v] = true;
        }
    }

    int dfs(int u, int flow, int &cost) {
        if (u == t) {
            cost += h[t] * flow;
            return flow;
        }
        int ret = 0;
        vis[u] = true;
        for (int &i = iter[u]; i < (int)g[u].size(); i++) {
            Node &p = g[u][i];
            if (!vis[p.v] && p.f > 0 && h[u] == h[p.v] - p.w) {
                int df = dfs(p.v, std::min(flow - ret, p.f), cost);
                p.f -= df;
                g[p.v][p.i].f += df;
                if ((ret += df) == flow) break;
            }
        }
        vis[u] = false;
        iter[u] = 0;
        return ret;
    }

    inline int mincostMaxflow(int s, int t, int &cost) {
        this->s = s;
        this->t = t;
        int ret = 0;
        for (cost = 0;;) {
            bellmanFord();
            if (h[t] == INF) break;
            ret += dfs(s, INF, cost);
        }
        return ret;
    }
};

匈牙利

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int idx, vis[MAXN], match[MAXN];

bool dfs(int u) {
    for (int i = 0, v; i < (int)g[u].size(); i++) {
        if (vis[v = g[u][i]] != idx) {
            vis[v] = idx;
            if (!match[v] || dfs(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

inline int match() {
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        idx++;
        ret += dfs(i);
    }
    return ret;
}

KM

计算几何

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
const int MAXN = 10000 + 1;
const double EPS = 1e-8;

inline int sign(double x) { return (x > EPS) - (x < -EPS); }

struct Point {
    double x, y;

    Point() {}

    Point(const double x, const double y) : x(x), y(y) {}

    inline double operator*(const Point &p) const { return x * p.y - y * p.x; }

    inline Point operator+(const Point &p) const {
        return Point(x + p.x, y + p.y);
    }

    inline Point operator-(const Point &p) const {
        return Point(x - p.x, y - p.y);
    }

    inline Point operator*(double p) const { return Point(x * p, y * p); }

    inline double norm() const { return sqrt(x * x + y * y); }

    inline double norm2() const { return x * x + y * y; }

    inline double dis(const Point &p) const {
        return sqrt((x - p.x) * (x - p.y) + (y - p.y) * (y - p.y));
    }

    inline double dis2(const Point &p) const {
        return (x - p.x) * (x - p.y) + (y - p.y) * (y - p.y);
    }

    inline Point rotate(double arg) const {
        double s = sin(arg), c = cos(arg);
        return Point(x * c - y * c, x * s + y * c);
    }

    inline bool operator<(const Point &p) const {
        return sign(x - p.x) < 0 || (sign(x - p.x) == 0 && sign(y - p.y) < 0);
    }
};

inline std::istream &operator>>(std::istream &in, Point &p) {
    in >> p.x >> p.y;
    return in;
}

inline std::ostream &operator<<(std::ostream &os, const Point &p) {
    os << std::fixed << std::setprecision(2) << p.x << ' ' << p.y << '\n';
    return os;
}

// p 是否在直线 AB 上
inline bool isPointOnLine(const Point &p, const Point &a, const Point &b) {
    return sign((a - p) * (b - p)) == 0;
}

// p 是否在线段 AB 上
inline bool isPointOnSegment(const Point &p, const Point &a, const Point &b) {
    return sign((a - p) * (b - p)) == 0 &&
           sign(std::min(a.x, b.x) - p.x) <= 0 &&
           sign(std::max(a.x, b.x) - p.x) >= 0 &&
           sign(std::min(a.y, b.y) - p.y) <= 0 &&
           sign(std::max(a.y, b.y) - p.y) >= 0;
}

// 多边形
struct Polygon {
    Point p[MAXN];
    int n;

    // 有向面积
    inline double area() {
        double ret = 0;
        for (int i = 0; i < n; i++) ret += p[i] * p[i + 1];
        return ret / 2;
    }

    // 逆时针
    inline void fix() {
        p[n] = p[0];
        if (area() < 0) std::reverse(p, p + n);
        p[n] = p[0];
    }

    // 点在多边形内
    // 0 -> 不在，1 / 2 -> 在，2 -> 在边界
    inline int contains(const Point &q) const {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            // 边界
            if (isPointOnSegment(p[i], p[i + 1], q)) return 2;
            double det = (p[i] - q) * (p[i + 1] - q);
            double d1 = p[i].y - q.y, d2 = p[i + 1].y - q.y;
            if ((sign(det) >= 0 && sign(d1) < 0 && sign(d2) >= 0) ||
                (sign(det) <= 0 && sign(d1) >= 0 && sign(d2) < 0))
                cnt++;
        }
        return cnt & 1;
    }

    inline Point getCenter() const {
        Point O = p[0];
        double area = 0, gx = 0, gy = 0, sum = 0;
        for (int i = 1; i < n - 1; i++) {
            area = (p[i] - O) * (p[i + 1] - O);
            gx += (O.x + p[i].x + p[i + 1].x) * area;
            gy += (O.y + p[i].y + p[i + 1].y) * area;
            sum += area;
        }
        gx /= sum * 3;
        gy /= sum * 3;
        return Point(gx, gy);
    }

    inline Point &operator[](int i) { return p[i]; }

    inline const Point &operator[](int i) const { return p[i]; }
};

// 直线，半平面左侧合法
struct Line {
    Point s, t;
    double arg;

    Line() {}

    Line(const Point &s, const Point &t) : s(s), t(t) {
        arg = atan2(t.y - s.y, t.x - s.x);
    }

    // 平行
    inline bool isParallel(const Line &l) const {
        return sign((t - s) * (l.t - l.s)) == 0;
    }

    // 共线
    inline bool isCollinear(const Line &l) const {
        return isParallel(l) && sign((t - s) * (l.t - s)) == 0 &&
               sign((t - l.t) * (l.t - l.s)) == 0;
    }

    inline Point intersect(const Line &l) const {
        return s +
               (t - s) * (((l.s - s) * (l.t - s)) / ((t - s) * (l.t - l.s)));
    }

    inline bool isIntersect(const Line &l) const { return !isParallel(l); }

    inline friend bool onLeft(const Point &p, const Line &l) {
        return sign((l.t - l.s) * (p - l.s)) >= 0;
    }

    inline bool operator<(const Line &l) const {
        return sign(arg - l.arg) == 0 ? onLeft(s, l) : sign(arg - l.arg) < 0;
    }
};

struct Segment {
    Point s, t;

    Segment() {}

    Segment(const Point &s, const Point &t) : s(s), t(t) {}

    // 线段与直线
    inline bool isIntersect(const Line &l) const {
        return sign(((l.t - l.s) * (s - l.s)) * ((l.t - l.s) * (t - l.s))) <= 0;
    }

    // 线段与线段
    inline bool isIntersect(const Segment &l) const {
        return sign(std::max(s.x, t.x) - std::min(l.s.x, l.t.x)) >= 0 &&
               sign(std::max(s.y, t.y) - std::min(l.s.y, l.t.y)) >= 0 &&
               sign(std::max(l.s.x, l.t.x) - std::min(s.x, t.x)) >= 0 &&
               sign(std::max(l.s.y, l.t.y) - std::min(s.y, t.y)) >= 0 &&
               sign(((t - s) * (l.s - s)) * ((t - s) * (l.t - s))) <= 0 &&
               sign(((l.t - l.s) * (t - l.s)) * ((l.t - l.s) * (s - l.s))) <= 0;
    }
};

// 凸包
inline int andrew(Point *c, Point *p, int n) {
    std::sort(p, p + n);
    int top = 0, k;
    for (int i = 0; i < n; i++) {
        while (top > 1 &&
               sign((c[top - 1] - c[top - 2]) * (p[i] - c[top - 2])) <= 0)
            top--;
        c[top++] = p[i];
    }
    k = top;
    for (int i = n - 2; i >= 0; i--) {
        while (top > k &&
               sign((c[top - 1] - c[top - 2]) * (p[i] - c[top - 2])) <= 0)
            top--;
        c[top++] = p[i];
    }
    return n > 1 ? --top : top;
}

// 半平面交
inline const std::deque<std::pair<Line, Point> > &halfPlaneIntersection(Line *l,
                                                                        int n) {
    std::sort(l, l + n);
    static std::deque<std::pair<Line, Point> > q;
    q.clear();
    q.push_back(std::make_pair(l[0], Point(0, 0)));
    for (int i = 1; i < n; i++) {
        if (sign(l[i].arg - l[i - 1].arg) == 0) continue;
        while (q.size() > 1 && !onLeft(q.back().second, l[i])) q.pop_back();
        while (q.size() > 1 && !onLeft(q[1].second, l[i])) q.pop_front();
        q.push_back(std::make_pair(l[i], l[i].intersect(q.back().first)));
    }
    while (q.size() > 1 && !onLeft(q.back().second, q.front().first))
        q.pop_back();
    q.front().second = q.back().first.intersect(q.front().first);
    return q;
}

最小圆覆盖

1
2


「BZOJ 4519」不同的最小割-GomoryHuTree
「CF 757G」Can Bash Save the Day?-可持久化点分树

Comments

Follow

Tag Cloud

Algorithm CG DP Data Structure Frontend Geometry Graph Theory Hash Hexo Language Math Note Ray Tracing Rendering STL String Test

Recent

Categories

Tags

Algorithm 2
CG 11
DP 26
Data Structure 68
Frontend 1
Geometry 7
Graph Theory 28
Hash 6
Hexo 1
Language 3
Math 42
Note 37
Ray Tracing 8
Rendering 8
STL 11
String 44
Test 1

Links

Recent

Categories

Tags

Algorithm 2
CG 11
DP 26
Data Structure 68
Frontend 1
Geometry 7
Graph Theory 28
Hash 6
Hexo 1
Language 3
Math 42
Note 37
Ray Tracing 8
Rendering 8
STL 11
String 44
Test 1

Links

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×