• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

省选常用模板

开发技术 开发技术 2周前 (04-06) 8次浏览

图论

SCC

void tarjan(int u) {
    static int top = 0;
    low[u] = dfn[u] = ++tim;
    stk[++top] = u; in[u] = 1;
    for (int i = G1.head[u]; i != -1; i = G1.nxt[i]) {
        int v = G1.to[i];
        if (!dfn[v]) tarjan(v), checkMin(low[u], low[v]);
        else if(in[v]) checkMin(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        scc += 1;
        do {
            bel[stk[top]] = scc;
            in[stk[top]] = 0;
            val[scc] += V[stk[top]];
            cost[scc] += W[stk[top]];
            top -= 1;
        } while(stk[top + 1] != u);
    }
}

v-BCC & 广义圆方树

int tim, top, dfn[MAXN], low[MAXN], stk[MAXN];
void tarjan(int u) {
    static int x; dfn[u] = low[u] = ++tim; stk[++top] = u;
    for (int i = G.head[u]; i != -1; i = G.nxt[i]) {
        int v = G.to[i];
        if (!dfn[v]) {
            tarjan(v); checkMin(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                rst.tot += 1; rst.add_edge(rst.tot, u);
                do {
                    x = stk[top--];
                    rst.add_edge(rst.tot, x);
                } while(x != v);
            }
        } else checkMin(low[u], dfn[v]);
    }
}
rst.tot = n;

maxflow

struct Dinic {
    int maxflow, cur[MAXN], dep[MAXN]; queue<int> q;

    bool bfs() {
        for (int i = 1; i <= tot; i++) cur[i] = G.head[i], dep[i] = -1;
        q.push(S); dep[S] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = G.head[u]; i != -1; i = G.nxt[i]) {
                int v = G.to[i];
                if (dep[v] == -1 && G.flow[i])
                    dep[v] = dep[u] + 1, q.push(v);
            }
        }
        return dep[T] != -1;
    }

    int dfs(int u, int flow) {
        if (u == T) {maxflow += flow; return flow;}
        int low, used = 0;
        for (int &i = cur[u]; i != -1; i = G.nxt[i]) {
            int v = G.to[i];
            if (dep[v] == dep[u] + 1 && G.flow[i]) {
                if (low = dfs(v, min(flow - used, G.flow[i]))) {
                    G.flow[i] -= low; G.flow[i ^ 1] += low; used += low;
                    if (used == flow) break;
                }
            }
        }
        return used;
    }

    int solve() {while(bfs()) dfs(S, INF); return maxflow;}
} dinic;

MCMF

struct EK {
    int cost, dis[MAXN], in[MAXN], pre[MAXN], id[MAXN];

    bool spfa() {
        for (int i = 1; i <= tot; i++) dis[i] = INF, in[i] = 0;
        queue<int> q; q.push(S); dis[S] = 0; in[S] = 1;
        while (!q.empty()) {
            int u = q.front(); q.pop(); in[u] = 0;
            for (int i = G.head[u]; i != -1; i = G.nxt[i]) {
                int v = G.to[i];
                if (dis[v] > dis[u] + G.cost[i] && G.flow[i]) {
                    dis[v] = dis[u] + G.cost[i]; pre[v] = u; id[v] = i;
                    if (!in[v]) in[v] = 1, q.push(v);
                }
            }
        }
        return dis[T] != INF;
    }

    int solve() {
        cost = 0;
        while (spfa()) {
            int t = INF;
            for (int u = T; u != S; u = pre[u])
                checkMin(t, G.flow[id[u]]);
            for (int u = T; u != S; u = pre[u])
                G.flow[id[u]] -= t, G.flow[id[u] ^ 1] += t;
            cost += t * dis[T];
        }
        return cost;
    }
} ek;

虚树

struct VirtualTree {
    static const int MAXM = MAXN;
    int top, stk[MAXM], mark[MAXM];
    vector<int> G[MAXN], bac;

    static bool cmp(const int &x, const int &y) {return dfn[x] < dfn[y];}

    void insert(int u) {
    	if (top <= 1) {stk[++top] = u; return;}
        int lca = rst.get_lca(u, stk[top]);
        if (lca == stk[top]) {stk[++top] = u; return;}
        while (top > 1 && rst.dfn[lca] <= rst.dfn[stk[top - 1]])
            G[stk[top - 1]].push_back(stk[top]), top -= 1;
        if (lca != stk[top]) 
            G[lca].push_back(stk[top]), stk[top] = lca, bac.push_back(lca);
        stk[++top] = u;
    }

    void build(int n, vector<int> &vec) {
        sort(vec.begin(), vec.end(), cmp); top = 0;
        if (vec[0] != 1) stk[++top] = 1, bac.push_back(1);
        for (int i = 0; i < n; i++) 
            insert(vec[i]), mark[vec[i]] = 1, bac.push_back(vec[i]);
		for (int i = 1; i < top; i++) G[stk[i]].push_back(stk[i + 1]);
    }

    void clear() {
        for (int &u : bac) G[u].clear(), mark[u] = 0;
        bac.clear(); ans = 0;
    }
} vt;

最短路

int n, m, s, dis[MAXN], vis[MAXN];
void dijkstra(int s) {
    for (int i = 1; i <= n; i++) dis[i] = INF;
    priority_queue<pii, vector<pii>, greater<pii> > q;
    dis[s] = 0; q.emplace(0, s);
    while (!q.empty()) {
        int u = q.top().second; q.pop();
        if (vis[u]) continue; vis[u] = 1;
        for (int i = G.head[u]; i != -1; i = G.nxt[i]) {
            int v = G.to[i];
            if (dis[v] > dis[u] + G.w[i]) {
                dis[v] = dis[u] + G.w[i];
                q.emplace(dis[v], v);
            }
        }
    }
}

点分治/点分树

struct Tree {
    int rt, root, size[MAXN], maxpart[MAXN], vis[MAXN], par[MAXN]; Graph E;

    void get_root(int u, int fa, int sz) {
        size[u] = 1; maxpart[u] = 0;
        for (int i = G.head[u]; i != -1; i = G.nxt[i]) {
            int v = G.to[i]; if (v == fa || vis[v]) continue;
            get_root(v, u, sz); size[u] += size[v]; checkMax(maxpart[u], size[v]);
        }
        checkMax(maxpart[u], sz - size[u]);
        if (!rt || maxpart[u] < maxpart[rt]) rt = u;
    }

    void build_tree(int u) {
        vis[u] = 1;
        for (int i = G.head[u]; i != -1; i = G.nxt[i]) {
            int v = G.to[i]; if (vis[v]) continue;
            rt = 0; get_root(v, u, size[v]);
            E.add_edge(u, rt); par[rt] = u; build_tree(rt);
        }
    }

    void build(int n) {
        rt = 0; get_root(1, 0, n);
        root = rt; build_tree(rt);
    }
} T;

长链剖分

// CF 150E
void dfs1(int u, int fa) {
    for (int i = G.head[u]; i != -1; i = G.nxt[i]) {
        int v = G.to[i]; if (v == fa) continue; dfs1(v, u); 
        if (len[v] > len[son[u]]) son[u] = v, wson[u] = G.w[i];
    }
    len[u] = len[son[u]] + 1; par[u] = fa;
}

void dfs2(int u) {
    dfn[u] = ++tim; if (son[u]) dfs2(son[u]);
    for (int i = G.head[u]; i != -1; i = G.nxt[i]) {
        int v = G.to[i];
        if (v != son[u] && v != par[u]) dfs2(v); 
    }
}

void dfs(int u, int mid, int &flag) {
    T.modify(1, 1, tim, dfn[u], {0, u});
    if (!son[u]) return; dfs(son[u], mid, flag); if (flag) return;
    T.modify(1, 1, tim, dfn[u] + 1, dfn[u] + len[u] - 1, wson[u] >= mid ? 1 : -1);
    pii p = T.query(1, 1, tim, dfn[u] + L, dfn[u] + min(len[u] - 1, R));
    if (p.first >= 0) {flag = 1; res = {u, p.second}; return;}
    for (int i = G.head[u]; i != -1; i = G.nxt[i]) {
        int v = G.to[i]; if (v == par[u] || v == son[u]) continue;
        dfs(v, mid, flag); if (flag) return;
        int w = G.w[i] >= mid ? 1 : -1;
        for (int j = 1; j <= len[v]; j++) {
            pii x = T.query(1, 1, tim, dfn[v] + j - 1); x.first += w;
            pii y = T.query(1, 1, tim ,dfn[u] + max(0, L - j), dfn[u] + min(len[u] - 1, R - j));
            if (x.first + y.first >= 0) {res = {x.second, y.second}; flag = 1; return;}
        }
        for (int j = 1; j <= len[v]; j++) {
            pii x = T.query(1, 1, tim, dfn[v] + j - 1); x.first += w;
            T.modify(1, 1, tim, dfn[u] + j, x);
        }
    }
}

数学

二次剩余/n次剩余

杜教筛

int get_mu(int x) {
	if (x < N) return mu[x];
	if (valmu[x]) return valmu[x];
	int res = 1;
	for (int l = 2, r; l <= x; l = r + 1) {
		r = x / (x / l);
		res -= (r - l + 1) * get_muu(x / l);
	}
	valmuu[x] = res; return res;
}

ll get_phi(int x) {
	if (x < N) return phi[x];
	if (valphi[x])
		return valphi[x];
	ll res = 1ll * x * (x + 1) / 2;
	for (int l = 2, r; l <= x; l = r + 1) {
		r = x / (x / l);
		res -= (ll)(r - l + 1) * get_phi(x / l);
	}
	valphi[x] = res; return res;
}

min25筛

(sum sigma_0(i)^k)

void Init(int n) {
    for (int i = 2; i <= n; i++) {
        if (!np[i]) p[++pcnt] = i;
        for (int j = 1; j <= pcnt; j++) {
            if (i * p[j] > n) break;
            np[i * p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }
    for (int i = 1; i <= pcnt; i++) sp0[i] = i;
    for (int i = 1; i <= 50; i++) powe[i] = power(i, K);
}

int& get_id(ll x) {return x <= lim ? ind1[x] : ind2[n / x];}
int get_fp() {return powe[2];}
int get_fpk(int k) {return powe[k + 1];}

int S(ll x, int y) {
    if (x < p[y]) return 0;
    int res = sub(g[get_id(x)], (ll)sp0[y] * get_fp() % MOD);
    for (int i = y + 1; i <= pcnt && (ll)p[i] * p[i] <= x; i++) {
        ll t = p[i];
        for (int e = 1; t <= x; e += 1, t = t * p[i])
            addmod(res, (ll)get_fpk(e) * (S(x / t, i) + (e != 1)) % MOD);
    }
    return res;
}

void Solve() {
    scanf("%lld%d", &n, &K); lim = sqrt(n); Init(lim);
    for (ll l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l); a[++tot] = n / l;
        g[tot] = (a[tot] - 1) % MOD; get_id(n / l) = tot;
    }
    for (int j = 1; j <= pcnt; j++)
        for (int i = 1; i <= tot && (ll)p[j] * p[j] <= a[i]; i++)
            submod(g[i], sub(g[get_id(a[i] / p[j])], j - 1));
    for (int i = 1; i <= tot; i++) g[i] = (ll)g[i] * get_fp() % MOD;
    printf("%dn", add(S(n, 0), 1));
}

Powerful_number

(f(p^k)=p^k(p^k-1))

void Init(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!np[i]) p[++tot] = i, phi[i] = i - 1;
        for (int j = 1; j <= tot; j++) {
            if (i * p[j] > n) break;
            np[i * p[j]] = 1;
            if (i % p[j] == 0) {phi[i * p[j]] = phi[i] * p[j]; break;}
            phi[i * p[j]] = phi[i] * phi[p[j]];
        }
    }
    for (int i = 1; i <= n; i++) preG1[i] = add(preG1[i - 1], (ll)i * phi[i] % MOD); 
}

int calc(ll l, ll r) {return (ll)((l + r) % MOD) * ((r - l + 1) % MOD) % MOD * inv2 % MOD;}

int sum_G(ll x) {
    if (x <= lim) return preG1[x];
    if (preG2[n / x]) return preG2[n / x];
    int res = (ll)(x % MOD) * ((x + 1) % MOD) % MOD * ((2 * x + 1) % MOD) % MOD * inv6 % MOD;
    for (ll l = 2, r; l <= x; l = r + 1) {
        r = x / (x / l);
        submod(res, (ll)calc(l, r) * sum_G(x / l) % MOD);
    }
    return preG2[n / x] = res;
}

int cnt;
void dfs(int d, ll m, int h) {
    if (d > tot || m * p[d] > n) {
    	cnt += 1;
        addmod(ans, (ll)h * sum_G(n / m) % MOD);
        return;
    }
    ll t = (ll)p[d] * p[d]; dfs(d + 1, m, h);
    for (int i = 2; m * t <= n; t *= p[d], i += 1)
        dfs(d + 1, m * t, (ll)(t % MOD) * (p[d] - 1) % MOD * (i - 1) % MOD * h % MOD);
}

// Solve(1, 1, 1)

CRT & EXCRT

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {x = 1, y = 0; return a;}
    ll g = exgcd(b, a % b, x, y), t = x;
    x = y; y = t - a / b * y; return g;
}

ll CRT(int *a, int *b, int n) { // x % a = b
    ll prod = 1, res = 0;
    for (int i = 1; i <= n; i++) prod *= a[i];
    for (int i = 1; i <= n; i++) {
        ll prodi = prod / a[i], x, y;
        exgcd(prodi, a[i], x, y);
        x = (x % a[i] + a[i]) % a[i];
        res += prodi * b[i] * x;
    }
    return res % prod;
}

ll EXCRT(ll *a, ll *b, int n) { // x % a = b
    ll prod = a[1], res = b[1];
    for (int i = 2; i <= n; i++) {
        ll c = ((b[i] - res) % a[i] + a[i]) % a[i], x, y;
        ll d = exgcd(prod, a[i], x, y);
        if (c % d) return -1;
        x = mul(x, c / d, a[i]);
        res += prod * x; prod *= a[i] / d;
        res = (res % prod + prod) % prod;
    }
    return res;
}

BSGS & ExBSGS

ll get_inv(ll a, ll p) {
    ll x, y; exgcd(a, p, x, y);
    return (x % p + p) % p;
}

map<int, int> mp;
int BSGS(int a, int b, int p) {
    int t = ceil(sqrt(p)); mp.clear();
    for (int i = 0, x = b; i <= t; i += 1, x = (ll)x * a % p) mp[x] = i;
    int at = power(a, t);
    for (int i = 1, x = at; i <= t; i += 1, x = (ll)x * at % p)
        if (mp.count(x)) return i * t - mp[x];
    return -1;
}

ll ExBSGS(ll a, ll b, ll p){
	if (b == 1 || p == 1) return 0;
	ll g = gcd(a, p), b1 = b, p1 = p, cnt = 0;
	while (g > 1) {
		if (b1 % g != 0) return -1;
		cnt += 1; p1 = p1 / g;
		b1 = b1 / g * get_inv(a / g, p1) % p1;
		g = gcd(a, p1);
	}
	ll res = BSGS(a, b1, p1);
	return (res == -1 ? -1 : res + cnt);
}

Luc++as & ExLucas

int Lucas(int x, int y) {
    if (!y) return 1;
    return (ll)binom(x % p, y % p) * Lucas(x / p, y / p) % p;
}

int fac_mod(ll n, int p, int mod) { // mod = p ^ k
    if (!n) return 1;
    ll ans = 1;
    for (int i = 2; i <= mod; i++)
        if (i % p) ans = ans * i % mod;
    ans = power(ans, n / mod, mod);
    for (int i = 2; i <= n % mod; i++)
        if (i % p) ans = ans * i % mod;
    return ans * fac_mod(n / p, p, mod) % mod;
}

ll calc_num(ll n, int p) {
    ll cnt = 0;
    for (ll i = p; i <= n; i *= p) cnt += n / i;
    return cnt;
}

int get_inv(ll a, int p) {
    ll x, y; exgcd(a, p, x, y);
    return (x % p + p) % p;
}

int binom(ll n, ll m, int p, int mod) { // mod = p ^ k
    if (n < m) return 0;
    ll a = fac_mod(n, p, mod), b = fac_mod(m, p, mod), c = fac_mod(n - m, p, mod);
    ll cnt = calc_num(n, p) - calc_num(m, p) - calc_num(n - m, p);
    return a * get_inv(b, mod) % mod * get_inv(c, mod) % mod * power(p, cnt, mod) % mod;
}

ll ExLucas(ll n, ll m, int p) {
    static int a[MAXN], b[MAXN];
    int t = p, tot = 0;
    for (int i = 2; i * i <= t; i++) {
        if (t % i == 0) {
            int x = 1; tot += 1;
            while (t % i == 0) x *= i, t /= i;
            a[tot] = x; b[tot] = binom(n, m, i, x);
        }
    }
    if (t > 1) {
        tot += 1; a[tot] = t;
        b[tot] = binom(n, m, t, t);
    }
    return CRT(a, b, tot);
}

NTT

namespace Poly {
    const int N = 20, MAXN = (1 << N) + 5, G = 3, mod = 998244353, inv2 = (mod + 1) / 2;
    int rev[MAXN], w[MAXN], wn[N];
    
    void InitNTT(int n) {
        wn[n] = power(G, (mod - 1) / (1 << n)); memset(rev, 0, sizeof(rev));
        for (int i = n - 1; i >= 1; i--) wn[i] = (ll)wn[i + 1] * wn[i + 1] % mod;
        for (int i = 1, t = 1; i < (1 << n); i <<= 1, t += 1) {
            w[i] = 1; 
            for (int j = 1; j < i; j++) 
                w[i + j] = (ll)w[i + j - 1] * wn[t] % mod;
        }
    }

    int Init(int n) {
        int len = 1; while (len < n) len <<= 1; return len;
    }

    void NTT(poly &a, int flag) {
        int n = a.size(); static int x, y;
        for (int i = 0; i < n; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (n >> 1));
		for (int i = 0; i < n; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
        for (int i = 2, mid = 1; i <= n; i <<= 1, mid <<= 1) {
            for (int j = 0;j < n; j += i) {
                for (int k = j; k < j + mid; k++) {
                    x = a[k], y = (ll)a[k + mid] * w[k - j + mid] % mod;
                    a[k] = add(x, y); a[k + mid] = sub(x, y);
                }
            }
        }
        if (flag == -1) {
            reverse(a.begin() + 1, a.begin() + n); int invn = inv(n);
            for (int i = 0; i < n; i++) a[i] = (ll)a[i] * invn % mod;
        }
    }

    poly operator * (const poly &A, const poly &B) {
        int n = A.size(), m = B.size();
        if (n < 5 || m < 5) {
            poly a; a.resize(n + m - 1);
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    addmod(a[i + j], (ll)A[i] * B[j] % mod);
            return a;
        }
        int len = Init(n + m); poly a = A, b = B;
        a.resize(len), b.resize(len); NTT(a, 1); NTT(b, 1);
        for (int i = 0; i < len; i++) a[i] = (ll)a[i] * b[i] % mod;
        NTT(a, -1); a.resize(n + m - 1); return a;
    }
}

拉格朗日插值

int lagrange(int *A, int n, int x) {
    static int pre[MAXN], suf[MAXN]; int res = 0;
    pre[0] = suf[n + 1] = 1;
    for (int i = 1; i <= n; i++) pre[i] = (ll)pre[i - 1] * (x - i) % MOD;
    for (int i = n; i >= 1; i--) suf[i] = (ll)suf[i + 1] * (x - i) % MOD;
    for (int i = 1; i <= n; i++) {
        int x = (ll)A[i] * pre[i - 1] % MOD * suf[i + 1] % MOD;
        int y = (ll)ifac[i - 1] * ifac[n - i] % MOD;
        if ((n - i) & 1) submod(res, (ll)x * y % MOD);
        else addmod(res, (ll)x * y % MOD);
    }
    return res;
}

线代

Gauss

void Gauss(int n) {
    for (int i = 1; i <= n; i++) {
        int p = i;
        for (int j = i + 1; j <= n; j++)
            if (abs(a[p][i]) < abs(a[j][i])) p = j;
        if (i != p) swap(a[p], a[i]); double t = a[i][i];
        for (int j = i; j <= n + 1; j++) a[i][j] /= t;
        for (int j = 1; j <= n; j++) {
            if (j == i) continue; t = a[j][i];
            for (int k = i; k <= n + 1; k++)
                a[j][k] -= a[i][k] * t;
        }
    }
    for (int i = 1; i <= n; i++) printf("%.5fn", a[i][n + 1]);
}

Matrix-Tree 定理

有根树删去第 (i) 行求行列式就是以 (i) 为根

void add_edge(int u, int v, int w) { // directed graph
    submod(a[u][v], w); addmod(a[v][v], w);
}

int get_det(int n) {
    int res = 1, sign = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            while (a[j][i]) {
                int t = a[i][i] / a[j][i];
                for (int k = i; k <= n; k++)
                    submod(a[i][k], (ll)t * a[j][k] % MOD);
                swap(a[i], a[j]); sign *= -1;
            }
        }
        if (!a[i][i]) return 0;
        res = (ll)res * a[i][i] % MOD;
    }
    return (res * sign + MOD) % MOD;
}

FWT

void FWT_OR(int *a, int n, int flag) {
    for (int i = 2; i <= n; i <<= 1) {
        int mid = (i >> 1);
        for (int j = 0; j < n; j += i) {
            for (int k = j; k < j + mid; k++) {
                if (~flag) addmod(a[k + mid], a[k]);
                else submod(a[k + mid], a[k]);
            }
        }
    }
}

void FWT_AND(int *a, int n, int flag) {
    for (int i = 2; i <= n; i <<= 1) {
        int mid = (i >> 1);
        for (int j = 0; j < n; j += i) {
            for (int k = j; k < j + mid; k++) {
                if (~flag) addmod(a[k], a[k + mid]);
                else submod(a[k], a[k + mid]);
            }
        }
    }
}

void FWT_XOR(int *a, int n, int flag) {
    for (int i = 2; i <= n; i <<= 1) {
        int mid = (i >> 1);
        for (int j = 0; j < n; j += i) {
            for (int k = j; k < j + mid; k++) {
                int x = add(a[k], a[k + mid]), y = sub(a[k], a[k + mid]);
                if (~flag) a[k] = x, a[k + mid] = y;
                else a[k] = (ll)x * inv2 % MOD, a[k + mid] = (ll)y * inv2 % MOD;
            }
        }
    }
}

数据结构

平衡树

struct FHQTreap {
    int tot, rt, pool_top, son[MAXN][2], size[MAXN], rnd[MAXN], val[MAXN], pool[MAXN];

    void push_up(int x) {size[x] = size[son[x][0]] + size[son[x][1]] + 1;}
    
    void split1(int k, int v, int &x, int &y) {
        if (!k) {x = y = 0; return;}
        if (val[k] <= v) x = k, split1(son[k][1], v, son[k][1], y);
        else y = k, split1(son[k][0], v, x, son[k][0]); push_up(k);
    }

    void split2(int k, int v, int &x, int &y) {
        if (!k) {x = y = 0; return;}
        if (v <= size[son[k][0]]) y = k, split2(son[k][0], v, x, son[k][0]);
        else x = k, split2(son[k][1], v - size[son[k][0]] - 1, son[k][1]);
        push_up(k);
    }

    int merge(int x, int y) {
        if (!x || !y) return x | y;
        if (rnd[x] < rnd[y]) {
            son[x][1] = merge(son[x][1], y);
      		push_up(x); return x;
        } else {
            son[y][0] = merge(x, son[y][0]);
      		push_up(y); return y;
        }
    }

    int newnode(int v) {
        int x = pool_top ? pool[pool_top--] : ++tot;
        size[x] = 1; val[x] = v; rnd[x] = rand();
        son[x][0] = son[x][1] = 0; return x;
    }

    void insert(int v) {
        static int x, y; split1(rt, v, x, y);
        rt = merge(merge(x, newnode(v)), y);
    }

    void remove(int v) {
        static int x, y, z; split1(rt, v, x, z); split1(x, v - 1, x, y); if (!y) return;
        pool[++pool_top] = y; rt = merge(merge(x, merge(son[y][0], son[y][1])), z);
    }

    int rank(int v) {
        static int x, y; split1(rt, v - 1, x, y);
        int res = size[x] + 1; rt = merge(x, y); return res;
    }

    int find(int x, int v) {
        while (1) {
            if (v <= size[son[x][0]]) x = son[x][0];
            else if (v == size[son[x][0]] + 1) return x;
            else v -= size[son[x][0]] + 1, x = son[x][1];
        }
    }

    int prev(int v) {
        static int x, y; split1(rt, v - 1, x, y);
        int res = val[find(x, size[x])]; rt = merge(x, y); return res;
    } 

    int next(int v) {
        static int x, y; split1(rt, v, x, y);
        int res = val[find(y, 1)]; rt = merge(x, y); return res;
    }

    int kth(int x) {return val[find(rt, x)];}
} fhq;

可持久化平衡树

struct FHQ_Trep {
    static const int MAXM = MAXN;
    int tot, pool_top, son[MAXM][2], pool[MAXM], rnd[MAXM], val[MAXM], size[MAXM];

    #define lson(x) son[x][0]
    #define rson(x) son[x][1]

    void push_up(int k) {size[k] = size[lson(k)] + size[rson(k)] + 1;}
    void copy(int x, int y) {lson(x) = lson(y); rson(x) = rson(y); rnd[x] = rnd[y]; val[x] = val[y]; size[x] = size[y];}
    int new_node() {return pool_top ? pool[pool_top--] : ++tot;}
    int new_node(int v) {int k = new_node(); size[k] = 1; val[k] = v; rnd[k] = rand(); lson(k) = rson(k) = 0; return k;}
    void remove_node(int k) {pool[++pool_top] = k;}

    void split(int k, int v, int &x, int &y) {
        if (!k) {x = y = 0; return;}
        if (val[k] <= v) {
            x = new_node(); copy(x, k);
            split(rson(x), v, rson(x), y);
            push_up(x);
        } else {
            y = new_node(); copy(y, k);
            split(lson(y), v, x, lson(y));
            push_up(y);
        }
    }

    int merge(int x, int y) {
        if (!x || !y) return x | y;
        if (rnd[x] < rnd[y]) {
            int k = new_node(); copy(k, x);
            rson(k) = merge(rson(k), y);
            push_up(k); return k;
        } else {
            int k = new_node(); copy(k, y);
            lson(k) = merge(x, lson(k));
            push_up(k); return k;
        }
    }

    void insert(int &rt, int v) {
        static int x, y; split(rt, v, x, y);
        rt = merge(merge(x, new_node(v)), y);
    }

    void remove(int &rt, int v) {
        static int x, y, z; split(rt, v, x, z); split(x, v - 1, x, y); if (!y) return; 
        remove_node(y); rt = merge(merge(x, merge(lson(y), rson(y))), z);
    }

    int get_rank(int &rt, int v) {
        static int x, y; split(rt, v - 1, x, y);
        int res = size[x] + 1; rt = merge(x, y); return res;
    }

    int find(int k, int v) {
        while (1) {
            if (v <= size[lson(k)]) k = lson(k);
            else if (v == size[lson(k)] + 1) return k;
            else v -= size[lson(k)] + 1, k = rson(k);
        }
    }

    int get_prev(int &rt, int v) {
        static int x, y; split(rt, v - 1, x, y); if (!x) return INT_MIN;
        int res = val[find(x, size[x])]; rt = merge(x, y); return res;
    }

    int get_next(int &rt, int v) {
        static int x, y; split(rt, v, x, y); if (!y) return INT_MAX;
        int res = val[find(y, 1)]; rt = merge(x, y); return res;
    }

    int get_kth(int &rt, int v) {return val[find(rt, v)];}
} fhq;

LCT

// dynamic MST
struct LCT {
    static const int MAXM = MAXN << 1;
    int tot, top, fa[MAXM], son[MAXM][2], maxid[MAXM], rev[MAXM], stk[MAXM], id[MAXM];

    #define lson(x) son[x][0]
    #define rson(x) son[x][1]

    int get_son(int x) {return rson(fa[x]) == x;}
    int is_root(int x) {return lson(fa[x]) != x && rson(fa[x]) != x;}
    void apply_rev(int x) {swap(lson(x), rson(x)); rev[x] ^= 1;}
    void push_down(int x) {if (rev[x]) apply_rev(lson(x)), apply_rev(rson(x)), rev[x] = 0;}
    void connect(int x, int p, int c) {fa[x] = p; son[p][c] = x;}

    void push_up(int x) {
        maxid[x] = id[x];
        if (lson(x) && e[maxid[lson(x)]].w > e[maxid[x]].w) maxid[x] = maxid[lson(x)];
        if (rson(x) && e[maxid[rson(x)]].w > e[maxid[x]].w) maxid[x] = maxid[rson(x)];
    }

    void rotate(int x) {
        int y = fa[x], z = fa[y], yson = get_son(x), zson = get_son(y);
        int b = son[x][yson ^ 1]; fa[x] = z;
        if (!is_root(y)) connect(x, z, zson);
        connect(b, y, yson); connect(y, x, yson ^ 1);
        push_up(y); push_up(x);
    }

    void splay(int x) {
        top = 0; stk[++top] = x;
        for (int u = x; !is_root(u); u = fa[u]) stk[++top] = fa[u];
        for (int i = top; i >= 1; i--) push_down(stk[i]);
        while (!is_root(x)) {
            int y = fa[x];
            if (!is_root(y))
                rotate(get_son(x) == get_son(y) ? y : x);
            rotate(x);
        }
    }

    void access(int x) {
        for (int y = 0; x; y = x, x = fa[x])
            splay(x), rson(x) = y, push_up(x);
    }

    int make_root(int x) {access(x); splay(x); apply_rev(x);}
    void split(int x, int y) {make_root(x); access(y); splay(y);}
    void link(int x, int y) {make_root(x); fa[x] = y;}
    void cut(int x, int y) {split(x, y); fa[x] = lson(y) = 0;}
    void modify(int x, int y) {maxid[x] = id[x] = y;}
    int query(int x, int y) {split(x, y); return maxid[y];}

    int find(int x) {
        access(x); splay(x); push_down(x);
        while (lson(x)) x = lson(x), push_down(x);
        splay(x); return x;
    }

} lct;

字符串

SAM

普通 SAM

struct SAM {
    static const int MAXM = MAXN << 1;
    int tot, last, tim, fa[MAXM], len[MAXM], son[MAXM][26];

    SAM() {last = tot = 1;}

    void extend(int c) {
        static int p, q, np, nq; p = last; 
        last = np = ++tot; len[np] = len[p] + 1;
        for (; p && !son[p][c]; p = fa[p]) son[p][c] = np;
        if (!p) {fa[np] = 1; return;} q = son[p][c];
        if (len[q] == len[p] + 1) {fa[np] = q; return;}
        nq = ++tot; memcpy(son[nq], son[q], sizeof(son[nq]));
        len[nq] = len[p] + 1; fa[nq] = fa[q]; fa[q] = fa[np] = nq;
        for (; p && son[p][c] == q; p = fa[p]) son[p][c] = nq;
    }
} sam;

广义 SAM

struct SAM {
    static const int MAXM = MAXN << 1;
    int tot, last, fa[MAXM], son[MAXM][26], len[MAXM];

    SAM () {last = tot = 1;}

    void extend(int c) {
        static int p, q, np, nq; p = last;
        if (son[p][c]) {
            q = son[p][c];
            if (len[q] == len[p] + 1) {last = q; return;}
            nq = ++tot; memcpy(son[nq], son[q], sizeof(son[nq]));
            len[nq] = len[p] + 1; fa[nq] = fa[q]; fa[q] = nq;
            for (; p && son[p][c] == q; p = fa[p]) son[p][c] = nq;
            last = nq; return;
        }
        last = np = ++tot; len[np] = len[p] + 1;
        for (; p && !son[p][c]; p = fa[p]) son[p][c] = np;
        if (!p) {fa[np] = 1; return;} q = son[p][c];
        if (len[q] == len[p] + 1) {fa[np] = q; return;}
        nq = ++tot; memcpy(son[nq], son[q], sizeof(son[nq]));
        len[nq] = len[p] + 1; fa[nq] = fa[q]; fa[q] = fa[np] = nq;
        for (; p && son[p][c] == q; p = fa[p]) son[p][c] = nq;
    }
} sam;

KMP

void KMP() {
	scanf("%s%s", s + 1, t + 1); // print position that t appears in s
    n = strlen(s + 1); m = strlen(t + 1); nxt[1] = 0;
    for(int i = 2, j = 0; i <= m; i++) {
        while (j && t[i] != t[j + 1]) j = nxt[j];
        if (t[i] == t[j + 1]) j += 1; nxt[i] = j;
    }
    for (int i = 1, j = 0; i <= n; i++) {
        while (j && t[j + 1] != s[i]) j = nxt[j];
        if (s[i] == t[j + 1]) j += 1;
        if (j == m) printf("%dn", i - m + 1), j = nxt[j];
    }
}

AC自动机

struct ACAutomation {
    static const int MAXM = MAXN;
    int tot, son[MAXM][10], fail[MAXM], end[MAXM];

    // index start at 0 !!!

    void insert(char *s) {
        int n = strlen(s + 1), u = 0;
        for (int i = 1; i <= n; i++) {
            int c = s[i] - '0';
            if (!son[u][c]) son[u][c] = ++tot;
            u = son[u][c];
        }
        end[u] = 1;
    }

    void build() {
        queue<int> q;
        for (int c = 0; c < 10; c++) if (son[0][c]) q.push(son[0][c]);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int c = 0; c < 10; c++) {
                int v = son[u][c];
                if (v) fail[v] = son[fail[u]][c], end[v] |= end[fail[v]], q.push(v);
                else son[u][c] = son[fail[u]][c];
            }
        }
    }
} ac;

manac++her

struct Manacher{
    int pos[MAXN], len[MAXN]; char tmp[MAXN];
    
    int build(char *s) {
        int m = 0, n = strlen(s + 1), res = 0; tmp[++m] = '@';
        for (int i = 1; i <= n; i++) tmp[++m] = '#', tmp[++m] = s[i], pos[m] = i;
        tmp[++m] = '#'; tmp[++m] = '$';
        int p = 0, mx = 0;
        for (int i = 1; i <= m; i++) {
            len[i] = i < mx ? min(mx - i, len[p * 2 - i]) : 1;
            while (tmp[i - len[i]] == tmp[i + len[i]]) len[i] += 1;
            if (i + len[i] > mx) mx = i + len[i], p = i;
        }
    }
} manacher;

杂项

WQS二分

// CF 739E
bool check2(db x, db y) {
    for (int i = 1; i <= n; i++) f[i] = cnt1[i] = cnt2[i] = 0;
    for (int i = 1; i <= n; i++) {
        f[i] = f[i - 1]; cnt1[i] = cnt1[i - 1], cnt2[i] = cnt2[i - 1];
        if (f[i - 1] + p[i] - x - eps > f[i]) {
            f[i] = f[i - 1] + p[i] - x;
            cnt1[i] = cnt1[i - 1] + 1; cnt2[i] = cnt2[i - 1];
        }
        if (f[i - 1] + u[i] - y - eps > f[i]) {
            f[i] = f[i - 1] + u[i] - y;
            cnt1[i] = cnt1[i - 1]; cnt2[i] = cnt2[i - 1] + 1;
        }
        if (f[i - 1] + u[i] + p[i] - p[i] * u[i] - x - y - eps > f[i]) {
            f[i] = f[i - 1] + u[i] + p[i] - p[i] * u[i] - x - y;
            cnt1[i] = cnt1[i - 1] + 1; cnt2[i] = cnt2[i - 1] + 1;
        }
    }
    return cnt2[n] <= b;
}

bool check1(db x, db &y) {
    db l = 0, r = 1;
    for (int i = 1; i <= 50; i++) {
        db mid = (l + r) / 2.0;
        if (check2(x, mid)) r = mid;
        else l = mid;
    }
    y = l; return cnt1[n] <= a;
}

db Solve() {
    db l = 0, r = 1, tl;
    for (int i = 1; i <= 50; i++) {
        db mid = (l + r) / 2.0;
        if (check1(mid, tl)) r = mid;
        else l = mid;
    }
    return f[n] + l * a + tl * b;
}

动态凸包

// CF 70D
struct Convex {
    map<int, int> up,down;

    ll cross(int x1, int y1, int x2, int y2) {return (ll)x1 * y2 - (ll)y1 * x2; }

    bool query_up(int x,int y) { // check if (x, y) inside convex 
        auto pos = up.lower_bound(x); if (pos == up.end()) return false;
        if (pos->first == x) return y <= pos->second;
        if (pos == up.begin()) return false; auto pre = prev(pos);
        return cross(x - pre->first, y - pre->second, pos->first - pre->first, pos->second - pre->second) >= 0;
    }

    bool query_down(int x, int y) {
        auto pos = down.lower_bound(x); if (pos == down.end()) return false;
        if (pos->first == x) return y >= pos->second;
        if (pos == down.begin()) return false; auto pre = prev(pos);
        return cross(x - pre->first, y - pre->second, pos->first - pre->first, pos->second - pre->second) <= 0;
    }

    bool query(int x, int y) {return query_down(x, y) && query_up(x, y);}

    void insert_up(int x, int y) {
        if (query_up(x, y)) return; up[x] = y;
        auto pos = up.find(x), nxt = next(pos);
        if (nxt != up.end()) {
            auto nxtt = next(nxt);
            while (nxtt != up.end()) {
                if (cross(nxt->first - x, nxt->second - y, nxtt->first - x, nxtt->second - y) >= 0)
                    up.erase(nxt), nxt = nxtt, nxtt = next(nxtt);
                else break;
            }
        }
        if (pos != up.begin()) {
            auto pre = prev(pos);
            while (pre != up.begin()) {
                auto pree = prev(pre);
                if (cross(pre->first - x, pre->second - y, pree->first - x, pree->second - y) <= 0)
                    up.erase(pre), pre = pree;
                else break;
            }
        }
    }

    void insert_down(int x, int y) {
        if (query_down(x, y)) return; down[x] = y;
        auto pos = down.find(x), nxt = next(pos);
        if (nxt != down.end()){
            auto nxtt = next(nxt);
            while (nxtt != down.end()) {
                if(cross(nxt->first - x, nxt->second - y, nxtt->first - x, nxtt->second - y) <= 0)
                    down.erase(nxt), nxt = nxtt, nxtt = next(nxtt);
                else break;
            }
        }
        if (pos != down.begin()) {
            auto pre = prev(pos);
            while(pre != down.begin()) {
                auto pree = prev(pre);
                if(cross(pre->first - x, pre->second - y, pree->first - x, pree->second - y) >= 0)
                    down.erase(pre), pre = pree;
                else break;
            }
        }
    }

    void insert(int x, int y) {insert_up(x, y); insert_down(x, y);}
} C;

程序员灯塔
转载请注明原文链接:省选常用模板
喜欢 (0)