在此处输入标题

未分类

Treap

# define u t[x]
# define lc ch[0]
# define rc ch[1]
# define tc ch[d]
# define vc ch[!d]
struct Tr {
    int ch[2], w;
    unsigned pri;
    void set (int _w) { w = _w, pri = my_rand (); }
};
void rot (int &x, bool d) { int y = u.tc; u.tc = o.vc, o.vc = x; upd (x); upd (x = y); }
void ins (int &x, int w) {
    if (!x) { t[++ tsz].set (w); return; }
    if (u.w == w) return;
    bool d = w > u.w;
    ins (u.tc, w);
    t[u.tc].pri > u.pri ? rot (x, d) : upd (x);
}
void del (int &x, int w) {
    assert (x);
    if (u.w == w) {
        bool d = urtc.pri > ulfc.pri;
        if (!u.tc) { x = 0; return; }
        rot (x, d), del (u.vc, w);
    } else del (u.ch[w > u.w], w);
    upd (x);
}

Link-Cut Tree

# define u t[x]
# define o t[y]
# define p u.par
# define lc ch[0]
# define rc ch[1]
# define tc ch[d]
# define vc ch[!d]
int sgn (int x) { return t[p].rc == x ? 1 : t[p].lc == x ? 0 : -1; }
void sc (int x, int y, bool d) { u.tc = y, o.par = x; }
void fix (int x) { if (~sgn (x)) fix (p); dw (x); }
void rot (int x, bool d) {
    int y = p, z = o.par;
    if (~sgn (y)) sc (z, x, sgn (y)); else p = z;
    sc (y, u.vc, d), sc (x, y, !d), upd (y);
}
int splay (int x) {
    fix (x); int t0, t1, y;
    while (~(t0 = sgn (x))) {
        if (~(t1 = sgn (y = p))) rot (t0 ^ t1 ? x : y, t0), rot (x, t1);
        else rot (x, t0);
    }
    return upd (x), x;
}
int acs (int _x) { for (int x = _x, y = 0; x; upd (y = x), x = p) splay (x), u.rc = y; return splay (_x); }
# define us t[acs (x)]
void evt (int x) { us.frev (); }
void link (int x, int y) { evt (x), p = y; }
void cut (int x) { t[us.lc].par = 0, u.lc = 0; }
void cut (int x, int y) { evt (x), cut (y); }

KD-Tree

# define u t[x]
# define lc ch[0]
# define rc ch[1]
struct Kd { int ch[2], minX, maxX, minY, maxY; };
int build (int l, int r, bool d) {
    if (l > r) return 0;
    int x = (l + r) >> 1;
    FOR (i, l, r) {
        u.minX = min (u.minX, p[i].x);
        u.maxX = max (u.maxX, p[i].x);
        u.minY = min (u.minY, p[i].y);
        u.maxY = max (u.maxY, p[i].y);
    }
    nth_element (p + l, p + x, p + r + 1, d ? cmpY : cmpX);
    u.lc = build (l, x - 1, !d);
    u.rc = build (x + 1, r, !d);
    return x;
}

Leftist Heap

# define u t[x]
# define o t[y]
# define ulfc u.lc
# define urtc u.rc
struct Le { int lc, rc, d; };
int merge (int x, int y) {
    if (!x || !y) return x + y;
    if (u.w > o.w) swap (x, y);
    u.rc = merge (u.rc, y);
    if (ulfc.d < urtc.d) swap (u.lc, u.rc);
    u.d = urtc.d + 1;
    return x;
}

Tarjan

SCC

void tarjan (int x) {
    low[x] = dfn[x] = ++ dsz;
    REP_G (i, x) {
        if (!dfn[v]) tarjan (v), low[x] = min (low[x], low[v]);
        else if (!del[v]) low[x] = min (low[x], dfn[v]);
    }
    if (dfn[x] == low[x]) {
        ++ bsz; int y;
        do { bel[y = stk[top --]] = bsz, del[y] = true; } while (y != x);
    }
}

Undirected Graph

void tarjan (int x, int fi) {
    REP_G (i, x) if (i != fi) {
        if (!dfn[v]) tarjan (v, i ^ 1), low[x] = min (low[x], low[v]);
        else if (!del[v]) low[x] = min (low[x], dfn[v]);
    }
}

Suffix Array

void build_sa (char *s) {
    REP (i, n) ++ c[x[i] = s[i]];
    REP (i, m) c[i] += c[i - 1];
    REP_D (i, n) sa[c[x[i]] --] = i;
    for (int k = 2, p = 0; m < n; k <<= 1, m = p) {
        REP (i, m) c[i] = 0; c[0] = p = 0;
        REP (i, n) if (sa[i] - k > 0) y[++ p] = sa[i] - k;
        FOR (i, n - k + 1, n) y[++ p] = i;
        REP (i, n) ++ c[x[y[i]]];
        REP (i, m) c[i] += c[i - 1];
        REP_D (i, n) sa[x[y[i]] --] = y[i];
        for (p = 1, sa[y[1]] = ; )
    }
}

Suffix Automaton

# define u sam[x]
# define v sam[x].tr[c]
# define vn sam[v]
# define o sam[y]
# define w sam[z]
struct Sam { int tr[26], par, l; Sam () { CLR (tr, -1); } };
void init () { sam[ssz = lst = 1].par = -1; }
int extend (int x, int c) {
    int z = ++ ssz; w.l = u.l + 1;
    for (; x != -1 && v == -1; x = u.par) v = z;
    if (x == -1) w.par = 1;
    else if (u.l + 1 == vn.l) w.par = v;
    else {
        int y = ++ ssz, _v = v;
        o = vn, o.l = u.l + 1, w.par = vn.par = y;
        for (; x != -1 && v == _v; x = u.par) v = y;
    }
    return z;
}

Fast Fourier Transform

void fft (int *a, int n, int ty) {
    for (int i = n >> 1, j = 1, k; j < n - 1; ++ j) {
        if (i > j) swap (a[i], a[j]);
        for (k = n >> 1; k <= i; k >>= 1) i ^= k;
        i ^= k;
    }
    for (int m = 2; m <= n; m <<= 1) {
        int h = m >> 1, wm = pr (g, (mod - 1) / m * (ty == 1 ? 1 : (m - 1)));
        for (int i = 0; i < n; i += m) {
            int w = 1;
            for (int j = i; j < i + h; ++ j) {
                int u = a[j], v = 1ll * w * a[j + h] % mod;
                a[j] = (u + v) % mod;
                a[j + h] = (u - v + mod) % mod;
                w = 1ll * w * wm % mod;
            }
        }
    }
    if (ty == -1) { int iv = pr (n, mod - 2); REP_0 (i, n) a[i] = 1ll * a[i] * iv % mod; }
}