图论
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;
程序员灯塔
转载请注明原文链接：省选常用模板
转载请注明原文链接：省选常用模板
