Template

Sunny郭 · 2023-10-20 08:10:41 · 个人记录

LCT

struct LCT {
    int f[N], c[N][2], s[N], t[N];
    #define f(x) f[x]
    #define lc(x) c[x][0]
    #define rc(x) c[x][1]
    #define get(x) (c[f[x]][1] == x)
    #define nt(x) (lc(f[x]) == x || rc(f[x]) == x)
    void up(int x) {s[x] = s[lc(x)] ^ s[rc(x)] ^ v[x];}
    void move(int x) {swap(lc(x), rc(x)), t[x] ^= 1;}
    void dw(int x) {
        if(t[x]) {
            if(lc(x)) move(lc(x));
            if(rc(x)) move(rc(x));
            t[x] = 0;
        }
    }
    void upd(int x) {
        if(nt(x)) upd(f[x]);
        dw(x);
    }
    void rot(int x) {
        int y = f(x), z = f(y), k = get(x), w = c[x][!k];
        if(nt(y)) c[z][get(y)] = x;
        c[y][k] = w, c[x][!k] = y;
        if(w) f(w) = y; 
        f(x) = z, f(y) = x;
        up(y);
    }
    void splay(int x) {
        upd(x);
        for(; nt(x); rot(x)) if(nt(f(x)))
            rot(get(f(x)) ^ get(x) ? x : f(x));
        up(x);
    }
    void access(int x) {
        for(int p=0; x; x=f(p=x))
            splay(x), rc(x) = p, up(x);
    }
    void maker(int x) {
        access(x), splay(x);
        if(t[x]) t[x] = 0; else move(x);
    }
    int find(int x) {
        access(x), splay(x);
        while(lc(x)) dw(x), x = lc(x);
        splay(x); return x;
    }
    void link(int x, int y) {
        maker(x);
        if(find(y) != x) f[x] = y;
    }
    void split(int x, int y) {
        maker(x), access(y), splay(y);
    }
    void cut(int x, int y) {
        split(x, y);
        if(lc(y) != x || lc(x) != rc(x)) return;
        f(x) = lc(y) = 0, up(y);
    }
} lct;

KMP

struct KMP {
    int d[N];
    void Kmp(char *a, char *b) {
        int i, j=0, n = strlen(a + 1), m = strlen(b + 1);
        for(i=2; i<=m; i++) {
            while(j && b[j+1] != b[i]) j = d[j];
            if(b[j + 1] == b[i]) j++;
            d[i] = j;
        }
        for(j=0,i=1; i<=n; i++) {
            while(j && b[j+1] != a[i]) j = d[j];
            if(b[j + 1] == a[i]) j++;
            if(j == m) printf("%d\n", i - m + 1);
        }
    }
} kmp;

Manacher

struct manacher {
    char s[N<<1]; 
    int n = 0, ans = 0, r, p[N<<1];
    void init(char *c) {
        s[++n] = '#';
        for(i=1; c[i]; i++) s[++n] = c[i], s[++n] = '#';
        s[++n] = '>';
        for(i=2; i<n; i++) {
            p[i] = i < r ? min(r - i, p[m * 2 - i]) : 1;
            while(s[i - p[i]] == s[i + p[i]]) p[i]++;
            if(i + p[i] > r) r = i + p[i], m = i;
            ans = max(ans, p[i]);
        }
    }
} M;

笛卡尔树

struct Treap {
    int lc[N], rc[N], st[N];
    void init(int *a) {
        int i, t = 0, k;
        for(i=1; i<=n; i++) {
            k = t;
            while(k && a[st[k]] > a[i]) k--;
            if(k) rc[st[k]] = i;
            if(k ^ t) lc[i] = st[k + 1];
            st[t=++k] = i;
        }
    }
} T;

康拓展开

struct Cantor {
    int ans = 1, f[N];
    void init(int *a, int n) {
        int i;
        for(f[0]=i=1; i<N; i++) f[i] = 1ll * f[i-1] * i % M;
        for(i=1; i<=n; i++) {
            T.add(a[i], 1);
            ans = (ans + 1ll * f[n - i] * (a[i] - T.ask(a[i])) % M) % M;
        }
    }
} cantor;

Flow

const int N = 5007, inf = (1<<31)-1;
struct Flow {
    int E = 1, S, T, h[N], e[N], v[N];
    queue<int> q;
    struct Yoi {
        int b, c, n;
    } d[N << 1];
    void add(int a, int b, int c) {
        d[++E] = {b, c, h[a]}, e[a] = h[a] = E;
        d[++E] = {a, 0, h[b]}, e[b] = h[b] = E;
    }
    int bfs() {
        memset(v, 0, sizeof v);
        v[S] = 1, q.push(S);
        int a, b, i;
        while(q.size()) {
            a = q.front(), q.pop();
            for(i=h[a]=e[a]; i; i=d[i].n) {
                b = d[i].b;
                if(!v[b] && d[i].c > 0) v[b] = v[a] + 1, q.push(b);
            }
        }
        return v[T];
    }
    int dfs(int a, int w) {
        if(a == T) return w;
        int b, c, s = 0, k;
        for(int&i=h[a]; i&&w; i=d[i].n) {
            b = d[i].b, c = min(d[i].c, w);
            if(c && v[b] == v[a] + 1) {
                s += k = dfs(b, c), w -= k;
                d[i].c -= k, d[i^1].c += k;
            }
        }
        return s ? s : v[a] = 0;
    }
    ll dinic() {
        ll res = 0;
        while(bfs()) res += dfs(S, inf);
        return res;
    }
} F;