板子

数论

\(exgcd : a * x + b * y = gcd(a, b), 输出 : x, y, gcd(a, b)\)

LL gcd(LL a, LL b) {return (b == 0) ? a : gcd(b, a % b);
}
LL lcm(LL a, LL b) {return a * b / gcd(a, b);
}
LL power(LL a, LL b, LL P) {LL res = 1;for (a %= P; b; a = a * a % P, b /= 2) {if (b % 2) res = res * a % P;}return res;
}
LL exgcd(LL a, LL b, LL &x, LL &y) { // a * x + b * y = gcd(a, b)if (!b) {x = 1, y = 0;return a;}LL d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}
template<typename T>
int CRT(T& a, T& p, int n){ /* CRT */LL P = 1, res = 0;for(int i = 0; i < n; i++) P *= p[i];for(int i = 0; i < n; i++) {int c = P / p[i], x, y;exgcd(c, p[i], x, y);	if (x < 0) x += p[i];res = (res + 1LL* a[i] * c % P * x % P ) % P;}return res;
}

std::vector<int> modeq(int a, int b, int p) { /* a * x = b (mod p) */std::vector<int> res;LL x, y;int d = exgcd(b, a % b, x, y);if (b % d > 0) return res;int e = (x * (b / d)) % p;for (int i = 0; i < d; i++) {res.emplace_back((e + i * (p / d)) % p);}return res;
}
LL BSGS(LL a, LL b, LL p) {b = (b % p + p) % p;if (1 % p == b % p) return 0; // > 0 注释std::map<LL,LL> mp;LL t = sqrt(p) + 1;LL w = 1;for (int i = 0; i < t; i++) {mp[b * w % p] = i;w = w * a % p;}a = power(a, t, p);LL x = 1;for (int i = 1; i <= t; i++) {x = x * a % p;if (mp.find(x) != mp.end()) {return i * t - mp[x];}}return -1;
}
LL exBSGS(LL a, LL b, LL p) { /* a ^ x = b (mod p) */b = (b % p + p) % p;if (1 % p == b % p) return 0; // > 0 注释LL x, y;LL d = exgcd(a, p, x, y);if (d > 1) {if (b % d) return -1;exgcd(a / d,p / d, x, y);return exBSGS(a, b / d * x, p / d) + 1;}return BSGS(a, b, p);
}

斯特林数

n个不同元素分成m个非空集合的方案数，集合内是无序的, 如有序 不需要 * invfac[m]

无序 ： \(Stirling = \sum_{i = 0} ^ {m} (-1) ^ {i} * C_{m} ^ {i} * (m - i) ^ {n}\) 无序 : \(Stirling / m!\)

LL Stirling(int n, int m) { LL res = 1;for (int i = 0, cur = 1; i <= m; i++) {res = (res + cur * C(m, i) % P * power(m - i, n) % P + P) % P;cur = - cur;}return res * invfac[m];
}

组合数

\(1^{-1} ≡ 1 \ (mod\ P),\ k = P / i, r = P \% i\)

$k * i + r ≡ 0\ (mod\ P),\ k * r ^ {-1} + i ^ {-1} ≡ 0\ (mod\ P) $

\(i ^ {-1} ≡ - k * r ^ {-1},\ i ^ {-1} ≡ - P / i * (P \% i) ^ {-1}\)

const LL N = 5E6;
const LL P = 998244353;LL fac[N + 1], inv[N + 1], invfac[N + 1];struct Comb {Comb () {fac[0] = fac[1] = inv[1] = invfac[0] = invfac[1] = 1;for (int i = 2; i <= N; i++) {fac[i] = fac[i - 1] * i % P;inv[i] = - P / i * inv[P % i] % P + P;invfac[i] = invfac[i - 1] * inv[i] % P;}}
} comb;LL C(int n, int m) {if (m < 0 || m > n) return 0;return fac[n] * invfac[n - m] % P * invfac[m] % P;
}

\(C_{i} ^ {0} = 1, C_{i} ^ {j} = C_{i - 1} ^ {j - 1} + C_{i - 1} ^ {j}\)

const int N = 2500;
const int P = 998244353;LL c[N + 1][N + 1]; struct Comb {Comb() {c[0][0] = 1;for (int i = 1; i <= N; i++) {c[i][0] = 1;for (int j = 1; j <= i; j++) {c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P;}}}
} comb;LL C(int n, int m) {if (m < 0 || m > n) return 0;return c[n][m];
}

\(lucas_{n} ^ {m} = lucas_{n / p} ^ {m / p} * C_{n \% p} ^ {m \% p}\)

// a,b 1e18 | p  1E5
LL power(LL a, LL b, LL P) {LL res = 1;for (a %= P; b; a = a * a % P, b /= 2) {if (b % 2) res = res * a % P;}return res;
}
LL C(LL n, LL m, LL p) {LL x = 1, y = 1;for (int i = n, j = 1; j <= m; i--, j++) {x = x * i % p;y = y * j % p;}return x * power(y, p - 2, p) % p;
}
LL lucas(LL n, LL m, LL p) { if (m < 0 || m > n) return 0;if (n < p && m < p) return C(n, m, p);return C(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
}

树状数组

\(a[p] = \sum_{i = 1} ^ {p} d_i\)

\(sum[p] = \sum_{i = 1} ^ {p} d_i * (p + 1) - \sum_{i = 1} ^ {p} i * d_i\)

struct Fenwick {int n;std::vector<LL> c1, c2;Fenwick (int n) : n(n), c1(n + 2), c2(n + 2) {}void modify(LL p ,LL x) {for (LL t = p; p <= n; p += p & -p) {c1[p] += x;c2[p] += x * t;}}LL query(LL p) {LL res = 0;for (LL t = p; p > 0; p -= p & -p) {res += c1[p] * (t + 1) - c2[p];}return res;}
};

struct Fenwick {int n, m;std::vector<std::vector<LL>> c1, c2, c3, c4;Fenwick (int n, int m) :n(n), m(m),c1(n + 1, std::vector<LL>(m + 1, 0)), c2(n + 1, std::vector<LL>(m + 1, 0)),c3(n + 1, std::vector<LL>(m + 1, 0)), c4(n + 1, std::vector<LL>(m + 1, 0)) {}void inc(int x, int y, LL k) {for (LL tx = x, ty = y; x <= n; x += x & -x) {for (y = ty; y <= m; y += y & -y) {c1[x][y] += k;c2[x][y] += k * tx;c3[x][y] += k * ty;c4[x][y] += k * tx * ty;}}}LL que(int x, int y) {LL res = 0;for (LL tx = x, ty = y; x <= n; x += x & -x) {for (y = ty; y <= m; y += y & -y) {res += c1[x][y] * (tx + 1) * (ty + 1);res -= c2[x][y] * (ty + 1);res -= c3[x][y] * (tx + 1);res += c4[x][y];}}return res;}LL query(int x1, int y1, int x2, int y2) {return que(x2, y2) - que(x1 - 1, y2) - que(x2, y1 - 1) + que(x1 - 1, y1 - 1);}LL add(int x1, int y1, int x2, int y2, LL k) {inc(x1, y1, k), inc(x1, y2 + 1, -k), inc(x2 + 1, y1, -k), inc(x2 + 1, y2 + 1, k);}
};

template<typename T, T inf>
struct Fenwick {int n;std::vector<T> aux, c;T chose(T a, T b) {return std::min(a, b);}Fenwick (int n) : n(n), aux(n + 1, inf), c(n + 1, inf) {};void inc(int p, T x) {for (aux[p] = x; p <= n; p += p & -p) {c[p] = aux[p];for (LL i = 1; i < (p & -p); i *= 2) {c[p] = chose(c[p], c[p - i]);}}}T que (int l, int r) {LL res = inf;while(l <= r) {for (res = chose(res, aux[r]), r--; l <= r - (r & -r); r -= (r & -r)) {res = chose(res, c[r]);}}return res;};
};
using fenwick = Fenwick<LL, (LL)(1E9)>;

线段树

#define ls p * 2 
#define rs p * 2 + 1
#define mid (l + r) / 2
#define ill if (ql > r || qr < l)
#define leg if (ql <= l && qr >= r)

// 动态开点线段树
#define ls lson[p]
#define rs rson[p]const int N = 7E7;
int lson[N + 1], rson[N + 1];
LL seg[N + 1], tag[N + 1];
int idx = 1;
void pd(int p, int l, int r) {if (tag[p]) {if (!ls) ls = ++idx;if (!rs) rs = ++idx;int mid = (l + r) / 2;seg[ls] += 1LL * (mid - l + 1) * tag[p];seg[rs] += 1LL * (r - mid) * tag[p];tag[ls] += tag[p];tag[rs] += tag[p];tag[p] = 0;}   
}
void inc(int p, int l, int r, int ql, int qr, int x) {if (ql <= l && qr >= r) {seg[p] += 1LL * (r - l + 1) * x;tag[p] += x;return ;}pd(p, l, r);int mid = (l + r) / 2;if (ql <= mid) {if (!ls) ls = ++idx;inc(ls, l, mid, ql, qr, x);}if (qr > mid) {if (!rs) rs = ++idx;inc(rs, mid + 1, r, ql, qr, x);}seg[p] = seg[ls] + seg[rs];
}
const LL inf = 0;
LL que(int p, int l, int r, int ql, int qr) {if (!p || ql > r || qr < l) return inf;if (ql <= l && qr >= r) return seg[p];pd(p, l, r);int mid = (l + r) / 2;return que(ls, l, mid, ql, qr) + que(rs, mid + 1, r, ql, qr);
}

// 线段树分治         
int n;
struct Dsu{int n, top;std::vector<int> fa, siz, stk;Dsu (int n = 4E5 + 10) : n(n), fa(n + 1), siz(n + 1, 1), stk(2E6), top(0){std::iota(fa.begin(), fa.end(), 0);};int find(int x) {while (x != fa[x]) x = fa[x];return x;}void merger(int x, int y) {x = find(x), y = find(y);if (x == y) return;if (siz[x] < siz[y]) {std::swap(x, y);}stk[++top] = y;fa[y] = x;siz[x] += siz[y];}void undo() {if (!top) return;int y = stk[top--];siz[fa[y]] -= siz[y];fa[y] = y;}
} dsu;
#define ls (p * 2)
#define rs (p * 2 + 1)
const int N = 2E5;
std::vector<std::pair<int,int>> seg[4 * N + 1];
void inc(int p, int l, int r, int ql, int qr, int u, int v) {if (ql > r || qr < l) return;if (ql <= l & qr >= r) {seg[p].push_back({u, v});return ;}int mid = (l + r) / 2;inc(ls, l, mid, ql, qr, u, v);inc(rs, mid + 1, r, ql, qr, u, v);
};int ans[N + 1];
void dfs(int p, int l, int r) {int tp = dsu.top;for (auto [u, v] : seg[p]) {u = dsu.find(u);v = dsu.find(v);if (u == v) {for (int i = l; i <= r; i++) ans[i] = 0;while (dsu.top > tp) dsu.undo();return;}dsu.merger(u, n + v);dsu.merger(v, n + u);}if (l == r) {ans[l] = 1;return ;}int mid = (l + r) / 2;dfs(ls, l, mid);dfs(rs, mid + 1, r);while (dsu.top > tp) dsu.undo();
}

主席树

// Usage : 
//   1. const int m = init(n); 
//   2. query : [l, r] : que(root[l - 1], root[r], 1, m, k);
namespace PerSegTree{const int N = 2E5;int idx, a[N], rk[N], root[N], siz[N << 5], L[N << 5], R[N << 5];int build(int l, int r) {int rt = ++idx;if (l == r) return rt;int mid = (l + r) / 2;L[rt] = build(l, mid);R[rt] = build(mid + 1, r);return rt;	}int inc(int pre,int l,int r,int x){int rt = ++idx;L[rt] = L[pre], R[rt] = R[pre];siz[rt] = siz[pre] + 1;if (l == r) return rt;int mid = (l + r) / 2;if (x <= mid) L[rt] = inc(L[pre], l, mid, x);else R[rt] = inc(R[pre], mid + 1, r, x);return rt;}int que(int u, int v, int l, int r, int k){if (l == r) return rk[l];int x = siz[L[v]] - siz[L[u]];int mid = (l + r) / 2;if (x >= k) return que(L[u], L[v], l, mid, k);return que(R[u], R[v], mid + 1, r, k - x);}int init(const int & n) {memcpy(rk + 1, a + 1, n * sizeof(int));std::sort(rk + 1, rk + n + 1);int m = std::unique(rk + 1, rk + n + 1) - (rk + 1);root[0] = build(1, m);for (int i = 1; i <= n; i++) {int t = std::lower_bound(rk + 1, rk + m + 1, a[i]) - rk;root[i] = inc(root[i - 1], 1, m, t);}return m;}
}
using namespace PerSegTree;

※重链剖分

const int N = 3e4 + 10;
struct HeavyPathDecomposition {int son[N], fa[N], siz[N], dep[N], dfn[N], top[N], rnk[N];Segtree<Info> seg;int cnt = 0, n;HeavyPathDecomposition (std::vector<std::vector<int>> &G, std::vector<int> &w, int u,int n_) {n = n_;dep[u] = 1;dfs1(G, u);dfs2(G, u, u, 0);for (int i = 1; i <= cnt; i++) {seg.modify(1, 1, n, i, w[rnk[i]]);}}void dfs1(std::vector<std::vector<int>> &G, int u) {siz[u] = 1;for (int v : G[u]){if(dep[v]) continue;fa[v] = u;dep[v] = dep[u] + 1;dfs1(G, v);siz[u] += siz[v];if(siz[v] > siz[son[u]]) son[u] = v;}}void dfs2(std::vector<std::vector<int>> &G, int u, int f, int pre) {top[u] = f;dfn[u] = ++ cnt;rnk[cnt] = u;if (!son[u]) return;dfs2(G, son[u], f, u);for (int v : G[u]) {if(v == son[u] || v == pre) continue;dfs2(G, v, v, u);}}int querysum(int x, int y) { /* sum/max/min/gcd... */LL res = 0, fx = top[x], fy = top[y];while (fx != fy) {if (dep[fx] >= dep[fy]) {res += seg.query(1, 1, n, dfn[fx], dfn[x]).sum,fx = top[x = fa[fx]];} else {res += seg.query(1, 1, n, dfn[fy], dfn[y]).sum,fy = top[y = fa[fy]];}    }if (dfn[x] < dfn[y]) res += seg.query(1, 1, n, dfn[x], dfn[y]).sum;else res += seg.query(1, 1, n, dfn[y], dfn[x]).sum;return res;}
};

※网络流

const int N = 210, M = 11000;
template<typename T> 
struct FlowGraph {int s, t, vtot, etot, dis[N], cur[N], h[N];struct edge {int v, nxt;T f;} e[M];void add(int u, int v, T f, T f2 = 0) {e[etot] = {v, h[u], f}; h[u] = etot++;e[etot] = {u, h[v], f2}; h[v] = etot++;}bool bfs() {for (int i = 1; i <= vtot; i++) {dis[i] = 0;cur[i] = h[i];}std::queue<int> q;q.push(s); dis[s]=1;while (!q.empty()) {int u = q.front(); q.pop();for (int i = h[u]; ~i; i = e[i].nxt) {int v = e[i].v;if (e[i].f > 0 && !dis[v]) {dis[v] = dis[u] + 1;if (v == t) return true;q.push(v);}}} return false;}T dfs(int u, T m) {if (u == t) return m;T flow = 0;for (int i = cur[u]; ~i; cur[u] = i = e[i].nxt) {if (e[i].f && dis[e[i].v] == dis[u] + 1) {T f = dfs(e[i].v, std::min(m, e[i].f));e[i].f -= f;e[i^1].f += f;m -= f;flow += f;if (!m) break;}}if (!flow) dis[u] = -1;return flow;}T dinic() {T flow = 0;while (bfs()) flow += dfs(s, std::numeric_limits<T>::max());return flow;}FlowGraph (int vtot_, int s_, int t_) {vtot = vtot_; s = s_; t = t_;for (int i = 1; i <= vtot; i++) h[i] = -1;}
};
const int N = 4010, M = 30010;
struct FlowGraph {int h[N], pre[N], vis[N], etot = 0, vtot, s, t;LL mf[N], d[N];struct edge {int v;LL c, w;int next;} e[M];void add (int u, int v, LL f, LL w) {e[etot] = {v, f, w, h[u]}; h[u] = etot++;e[etot] = {u, 0, -w, h[v]}; h[v] = etot++;}bool spfa() {memset(d, 0x3f, sizeof d);memset(mf, 0, sizeof mf);std::queue<int > q;q.push(s);mf[s] = 1E9, d[s] = 0;while (q.size()) {int u = q.front();q.pop();vis[u] = 0;for (int i = h[u]; ~i; i = e[i].next) {int v = e[i].v;if (d[v] > d[u] + e[i].w && e[i].c) {d[v] = d[u] + e[i].w;mf[v] = std::min(mf[u], e[i].c);pre[v] = i;if (!vis[v]++) q.push(v);}}} return mf[t] > 0;}std::pair<int, int> EK() {LL flow = 0,sum = 0;while (spfa()) {int v = t;while (v != s) {int i = pre[v];e[i].c -= mf[t];e[i ^ 1].c += mf[t];v  = e[i ^ 1].v;}flow += mf[t];sum += mf[t] * d[t];}return {flow, sum};}FlowGraph (int vtot_, int s_, int t_) {vtot = vtot_; s = s_; t = t_;for (int i = 1; i <= vtot; i++) h[i] = -1;}
};

LCA

    std::vector<int> dep(n + 1);std::vector f(21, std::vector<int>(n + 1));auto dfs = [&](auto self, int u, int fa) ->void{dep[u] = dep[fa] + 1, f[0][u] = fa;for (int j = 1; j <= 20; j++) f[j][u] = f[j - 1][f[j - 1][u]];for (int v : g[u]) {if (v == fa) continue;self(self, v, u);}};dfs(dfs, 1, 0);auto lca = [&](int x, int y) -> int{if (dep[x] < dep[y]) std::swap(x, y);for (int i = 20; i >= 0; i--) if (dep[f[i][x]] >= dep[y]) x = f[i][x];if (x == y) return x;for (int i = 20; i >= 0; i--)if (f[i][x] != f[i][y]) x = f[i][x], y = f[i][y];return f[x][0];};

tarjan

    // tarja缩点int top = 0, cnt = 0, tot = 0;std::vector g(n + 1, std::vector<int>());std::vector<int> low(n + 1), dfn(n + 1), scc(n + 1), siz(n + 1), stk(n + 1), inst(n + 1);auto tarjan = [&](auto self, int x) {low[x] = dfn[x] = ++tot;stk[++top] = x;inst[x] = 1;for (auto v : g[x]) {if(!dfn[v]) {self(self, v);low[x] = std::min(low[x], low[v]);}else if(inst[v]) {low[x] = std::min(low[x], dfn[v]);}}if(dfn[x] == low[x]) {cnt ++;for (int y = -1; y != x; top--) {scc[y = stk[top]] = cnt;siz[cnt]++;inst[y] = 0;}}};

    // tarjan 割边int idx = 0;std::vector<int> dfn(n + 1), low(n + 1), fa(n + 1), need(m + 1, 1);auto tarjan = [&](auto self, int u) ->void{dfn[u] = low[u] = ++idx;for (const auto& [v, id]: g[u]) {if (!dfn[v]) {fa[v] = u;self(self, v);low[u] = std::min(low[u], low[v]);if (low[v] > dfn[u]) need[id] = 0;} else if (v != fa[u]){low[u] = std::min(low[u], dfn[v]);}}};tarjan(tarjan, 1);

素数筛

const int N = 1e7 + 10;
int phi[N];
std::vector<int>p;
std::bitset<N>np;
void Euler(int n) {for (int i = 2; i <= n; i++){if(!np[i]) {p.emplace_back(i);phi[i] = i - 1;}for (int j : p) {if (i * j > n) break;np[i * j] = 1;if (j % i == 0) {phi[j * i] = phi[i] * j;break;} else {phi[j * i] = phi[i] * phi[j];	}}}
}

※莫比乌斯函数

\(\mu(n) = \begin{cases} 1 & n=1 \\ 0 & n 含有相同质因子 \\ (-1)^k& k为不同质因子的个数 \end{cases} \)

const int N = 1E6 + 10;
int p[N], vis[N], mu[N];
int tot;
void Getmu(int n) {mu[1] = 1;for (int i = 2; i <= n; i++) {if (!vis[i]) {p[++tot] = i;mu[i] = -1;}for (int j = 1; i * p[j] <= n; j++) {int m = i * p[j];vis[m] = 1;if (i % p[j] == 0) {mu[m] = 0;break;} else {mu[m] = - mu[i];}}}
}

线性基

    static LL zero = 0, p[64], b[64];auto ins = [&](LL x){if (x == 0) return zero++;for (LL i = 62; i >= 0; i--) {if ((x & (1LL << i)) == 0) continue;if (p[i] == 0) return p[i] = x;                x ^= p[i];}return 0LL;};auto check = [&] (LL x) {for (LL i = 62; i >= 0; i--) {if ((x & (1LL << i) == 0)) continue;if (p[i] == 0) return false;x ^= p[i]; }return true;};auto getmx = [&]() {LL res = 0;for (LL i = 62; i >= 0; i--) {if((res ^ p[i]) > res) res ^= p[i];}return res;};auto getmi = [&]() {if(zero) return 0LL;for (LL i = 0; i <= 62; i++) {if (p[i]) return p[i];}return 0LL;};auto que = [&](LL k) {if (!(k -= zero)) return 0LL;LL res = 0, cnt = 0;for (LL i = 0; i <= 62; i++) {for (LL j = i - 1; ~j; j--) {if (p[i] & (1LL << j)) p[i] ^= p[j];}if (p[i]) b[cnt++] = p[i];}if (k >= (1LL << cnt)) return -1LL;for (LL i = 0; i < cnt; i++) {if (k & (1LL << i)) res ^= b[i];}return res;};

马拉车

template<class T>
int manacher(const T& s) { // -2 -1 ch -1 -3const int n = s.size();std::vector<int> m(2 * n + 3, -1), f(2 * n + 3);for (int i = 1; i <= n; i++) m[i * 2] = s[i - 1];m[0] = -2, m[2 * n + 2] = -3;for (int i = 1, l = 2, r = 2; i < 2 * n + 2; i++) {if (i <= r) f[i] = std::min(f[l + r - i], r - i + 1);while (m[i - f[i]] == m[i + f[i]]) f[i]++; f[i]--;if (i + f[i] >= r) l = i - f[i], r = i + f[i];}return *std::max_element(f.begin(), f.end());
}

※AC自动机

//计数版本
const int N = 2e6+10;
int idx; 
int tr[N][26];
std::vector<int> G[N];
int e[N], fail[N], sum[N];
int insert(std::string s){int p = 0;for (char ch : s) {int j = ch-'a';if(!tr[p][j]) tr[p][j] = ++idx;p = tr[p][j];}return p;
}
int find(std::string s) { int p = 0;int sz = s.size();for (int i = 0; i < sz; i++) {int c = s[i] - 'a';if (!nxt[p][c]) return 0;p = nxt[p][c];}return p;
}
void build(){std::queue<int>q;for (int i = 0;i < 26; i++) {if(tr[0][i]) q.push(tr[0][i]);}while(!q.empty()) {int u = q.front();q.pop();for (int i = 0; i < 26; i++){int &v = tr[u][i];if (v) {fail[v] = tr[fail[u]][i];q.push(v);}else v = tr[fail[u]][i];}}for (int i = 1;i <= idx; i++) G[fail[i]].emplace_back(i);
}
void dfs(int u){for (int v : G[u]){dfs(v);sum[u] += sum[v];}
}
void query(string s){int j = 0;for (char ch:s){j = tr[j][ch - 'a'];sum[j] ++;}dfs(0);
}

ST表

struct ST{int n;std::vector<std::vector<int>> st;ST(const std::vector<int>& a) {n = a.size() - 1;st.assign(22, std::vector<int>(n + 1));st[0] = a;for (int j = 1; j <= 21; j++) {for (int i = 1; i + (1 << j) - 1 <= n; i++) {st[j][i] = std::max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);}};};int query(int l, int r) {int k = log2(r - l + 1);return std::max(st[k][l], st[k][r - (1 << k) + 1]);};
};

最短路

	const LL inf = 1E18;const int s = 1;std::vector<bool> vis(n + 1, 0);std::vector<LL > dis(n + 1, inf);std::priority_queue<std::pair<LL, int>> q;q.push({0, s});dis[s] = 0;while (q.size() != 0) {auto [w, u] = q.top();q.pop();if (vis[u]) continue;vis[u] = 1;for (const auto& [v, w] : G[u]) {if (dis[u] + w < dis[v]) {dis[v] = dis[u] + w;q.push({-dis[v], v});}}}

	const LL inf = 1E18;const int s = 1;std::vector<LL>dis( n + 1, inf);auto spfa = [&](int s){std::vector<int> cn(n + 1, 0);std::vector<bool> inq(n + 1);std::queue<int> q;q.push(s);dis[s] = 0;while(!q.empty()){int u = q.front();q.pop();inq[u] = 0;for(const auto& [v,w] : G[u]){if(dis[v] > dis[u] + w){dis[v] = dis[u] + w;if(!inq[v]){if(++cn[v] > n) return false;q.push(v);inq[v]=1;}}}}return true;};

※树上启发式合并

std::vector<int> G[N];
int L[N], R[N], siz[N];
int dfn[N], tot;
void dfs1(int u, int fa) {siz[u] = 1;L[u] = ++tot;dfn[tot] = u;for (int v:G[u]){if(v == fa) continue;dfs1(v,u);size[u] += siz[v];if(siz[v] > sz[son[u]]) son[u] = j;}R[u] = tot;
}
void dfs2(int u, int fa, int remove) {for (int v:G[u]) {if(v == son[u]||v == fa) continue;dfs2(v, u, 1);}if(son[u]) dfs2(son[u], u, 0); for (int v : G[u]){if(v == son[u] || v == fa) continue;for (int i = L[v]; i <= R[v]; i++) add(dfn[i]);dfs2(v,u,1);}update(u, 1);ans[u] = sum;if(remove) {for(int i = L[u]; i <= R[u]; i++) del(dfn[i]);maxv = sum = 0;}
}

哈希Hash

template<LL b, LL P>
struct Hash {size_t n;std::string s;std::vector<LL> h, pw;Hash (const std::string &s) :s(s), n(s.size()), h(n + 1), pw(n + 1, 1){for (int i = 1; i <= n; i++) {pw[i] = pw[i - 1] * b % P;h[i] = (h[i - 1] * b % P + s[i - 1]) % P;}}void append(char ch) {s.push_back(ch);pw.push_back(pw.back() * b % P);h.push_back((h.back() * b % P + ch) % P);}void append(std::string s) {for (char ch : s) append(ch);}LL query(int l, int r) {l++, r++; return (h[r] - h[l - 1] * pw[r - l + 1] % P + P) % P;}
};
using hash = Hash<(LL)29, (LL)998244353>;
using hsah = Hash<(LL)131, (LL)1E9 + 7>;

KMP

std::vector<int> kmp(std::string s) {int n = s.size();std::vector<int> f(n + 1);for (int i = 1, j = 0; i < n; i++) {while (j && s[i] != s[j]) {j = f[j];}j += (s[i] == s[j]);f[i + 1] = j;}return f;	
}// matchint match = 0;   for (int i = 0, j = 0; i < m; i++) {while (j > 0 && s[j] != t[i]) {j = nxt[j];}j += (s[j] == t[i]);if (j == n) {match++;j = nxt[j];}}// matchauto nxt = kmp(t + "#" + s);int match = std::count(nxt.begin(), nxt.end(), t.size());

※Z函数

std::vector<int> exkmp(std::string s) { // Z[i] : 以与s[i] 与 s[0]的lcp (in : base 0, out : base 1)int n = s.size();std::vector<int> z(n + 1);for (int i = 1, L = 0, R = -1; i < n; i++) {int j = 0;if (i <= R) {int k = i - L + 1;j = std::min(z[k], R - i + 1);}while (i + j < n && s[j] == s[i + j]) {j++;}if (i + j - 1 > R) {L = i, R = i + j - 1;}z[i + 1] = j;}return z;
}

std::vector<int> Ex_KMP(const std::string &s, const std::string &t) {int n = s.size();int m = t.size();std::vector<int> z = Z_Function(s);std::vector<int> p(m);for (int i = 0, l = 0, r = -1; i < m; i++) {if (i <= r && z[i - l] < r - i + 1) {p[i] = z[i - l];} else {p[i] = std::max(0, r - i + 1);while (p[i] < n && i + p[i] < m && s[p[i]] == t[i + p[i]]) p[i]++;if (i + p[i] - 1 > r) l = i, r = i + p[i] - 1;}}return p;
}

※最小表示法

std::string getMin(std::string s) {int n = s.size();s += s;int i = 0, j = 1;while (j < n) {int k = 0;while (k < n && s[i + k] == s[j + k]) k++;if (s[i + k] < s[j + k]) j += k + 1;else i += k + 1;if (i == j) j++;if (i > j) std::swap(i, j);}return s.substr(i, n);
}

SuffixArray

const int N = 1E7 + 10;
int x[N], y[N], c[N], sa[N], rk[N], lcp[N];
template<class T>
void SuffixArray(const T &s, int n, int m = 1E6) {auto bucket_sort = [&](int offset) {memset(c, 0, sizeof (c));for (int i = 1; i <= n; i++) y[i] = sa[i];for (int i = 1; i <= n; i++) c[x[y[i] + offset]]++;for (int i = 1; i <= m; i++) c[i] += c[i - 1];for (int i = n; i >= 1; i--) sa[c[x[y[i] + offset]]--] = y[i];};for (int i = 1; i <= n; i++) x[sa[i] = i] = s[i - 1]; bucket_sort(0);for (int k = 1; k <= n && n != m; k *= 2) {bucket_sort(k), bucket_sort(0), m = 0;for (int i = 1; i <= n; i++) y[i] = x[i];for (int i = 0; i <= n; i++) {x[sa[i]] = m += !(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]);}}for (int i = 1; i <= n; i++) rk[sa[i]] = i;for (int i = 1, k = 0, j; i <= n; i++){if(rk[i] == 1) continue;k -= k != 0, j = sa[rk[i] - 1];while(i + k <= n && j + k <= n && s[i + k - 1] == s[j + k - 1]) k++;lcp[rk[i]] = k;}
}

	// 求s[l]..., s[r]...之间的lcp, 也就是他们的公共前缀std::vector st(22, std::vector<int>(n + 1));for (int i = 1; i <= n; i++) st[0][i] = lcp[i];for (int j = 1; j <= 21; j++) {for (int i = 1; i + (1 << j) - 1 <= n; i++) {st[j][i] = std::min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);}}auto query = [&](int a, int b) {if (a == b) return n - a + 1;int l = rk[a], r = rk[b];if (l > r) std::swap(l, r);l++;int k = log2(r - l + 1);return std::min(st[k][l], st[k][r - (1 << k) + 1]);};// example : 求字串排序std::sort(Q.begin(), Q.end(), [&](std::pair<int,int> a, std::pair<int,int> b) {int Lcp = query(a.first, b.first);int len1 = a.second - a.first + 1;int len2 = b.second - b.first + 1;if (Lcp >= len1 || Lcp >= len2) return len1 < len2 || (len1 == len2 && a < b);return s[a.first + Lcp - 1] < s[b.first + Lcp - 1] || (s[a.first + Lcp - 1] == s[b.first + Lcp - 1] && a < b);});// example : 求重复次数最多的连续重复子串 比如 abababab 那就是4 * ab 那就是4int ans = 1;	for (int i = 1; i <= n; i++) {for (int j = 1; j + i <= n; j += i) {int len_k = query(j, j + i);int k = j - (i - len_k % i);int num = len_k / i + 1;if (k >= 0 && query(k, k + i) >= i) num++;ans = std::max(num, ans);}}std::cout << ans << '\n';

KM算法

const int N = 30;
const LL inf = 1E9;
int vx[N], vy[N], love[N], evol[N];
LL lx[N], ly[N], w[N][N], d;bool dfs(int u, int n) {vx[u] = 1;for (int i = 1; i <= n; i++) {if (!vy[i]) {LL t = lx[u] + ly[i] - w[u][i];if (t == 0) {vy[i] = 1;if (!love[i] || dfs(love[i], n)) {love[i] = u;evol[u] = i;return true;}} else if (t > 0) d = std::min(d, t);}}return false;
}
void km(const int & n) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {lx[i] = std::max(lx[i], w[i][j]);}}for (int i = 1; i <= n; i++) {while (1) {d = inf;memset(vx, 0, sizeof (vx));memset(vy, 0, sizeof (vy));if (dfs(i, n)) break;for (int i = 1; i <= n; i++) if (vx[i]) lx[i] -= d;for (int i = 1; i <= n; i++) if (vy[i]) ly[i] += d;}}
}

模数类

constexpr long long P = 998244353;
template<class T>
T power (T a, long long b) {T res{1};for (; b > 0; a = a * a, b /= 2) {if (b % 2) res *= a;}return res;
}
struct Z {long long x;Z(int x) : x(norm(x)) {}Z(long long x = 0) : x(norm(x % P)) {}Z operator-() const {return Z(norm(P - x));}Z inv() const {assert(x != 0); return power(*this, P - 2); }Z &operator/=(const Z &rhs) {return *this *= rhs.inv();}Z &operator+=(const Z &rhs) {x = norm(x + rhs.x);return *this;}Z &operator-=(const Z &rhs) {x = norm(x - rhs.x);return *this;}Z &operator*=(const Z &rhs) {x = (long long)(x) * rhs.x % P;return *this;}Z operator*(const Z &rhs) {Z res = *this;res *= rhs;return res;}Z operator+(const Z &rhs) {Z res = *this;res += rhs;return res;}Z operator-(const Z &rhs) {Z res = *this;res -= rhs;return res;}Z operator/(const Z &rhs) {Z res = *this;res /= rhs;return res;}friend std::istream &operator>>(std::istream &is, Z &in) {long long v;is >> v;in = Z(v);return is;}friend std::ostream &operator<<(std::ostream &os, const Z &a) {return os << a.x;}long long norm(long long x) const {if(x < 0) x += P;if (x >= P) x -= P; return x;}
};

并查集

struct Dsu{int n, top;std::vector<int> fa, siz, stk;Dsu (int n = 4E5 + 10) : n(n), fa(n + 1), siz(n + 1, 1), stk(2E6), top(0){std::iota(fa.begin(), fa.end(), 0);};int find(int x) {while (x != fa[x]) x = fa[x];return x;}void merger(int x, int y) {x = find(x), y = find(y);if (x == y) return;if (siz[x] < siz[y]) std::swap(x, y);stk[++top] = y;fa[y] = x;siz[x] += siz[y];}void undo() {if (!top) return;int y = stk[top--];siz[fa[y]] -= siz[y];fa[y] = y;}
} dsu;

数位DP

    static long long f[10001][1025], g[10001][1025];auto dfs = [&](auto self, int pos, int lim, bool zero, int sta) -> std::pair<long long, long long>{if (pos == 0) return {(mask & sta) == mask, 0};if (!lim && !zero && f[pos][sta] != - 1) return {f[pos][sta], g[pos][sta]};int up = lim ? (s[N - pos] - '0') : 9;long long cnt = 0, sum = 0;for (int i = 0; i <= up; i++) {const auto& [x, y] = self(self, pos - 1, lim && i == up, zero && i == 0, (zero && i == 0) ? sta : sta | (1 << i));cnt = (cnt + x) % P;sum = (sum + y + ten[pos] * i % P * x) % P;}if (!lim && !zero) return {f[pos][sta] = cnt, g[pos][sta] = sum};return {cnt, sum};};memset(f, -1, sizeof(f));std::cout << dfs(dfs, N, 1, 1, 0).second << '\n';

笛卡尔树

    std::vector<int> ls(n + 1), rs(n + 1), stk(n + 1);auto CartesianTree = [&] () {for (int i = 1, top = 0, pos = 0; i <= n; i++) {pos = top;for (; pos && a[stk[pos]] > a[i]; pos--);if (pos) rs[stk[pos]] = i;if (pos < top) ls[i] = stk[pos + 1];stk[top = ++pos] = i;};return stk[1];};

对拍

#include <bits/stdc++.h>
int main() {system("g++ good.cpp -o good.exe");system("g++ bad.cpp -o bad.exe");system("g++ gen.cpp -o gen.exe");int test = 0;while (test++ <= 100) {system("gen.exe > in.txt");system("good.exe < in.txt > good.txt");system("bad.exe < in.txt > bad.txt");if (system("fc good.txt bad.txt")) break;if (system("diff good.txt bad.txt")) break;std::cout << "test " << test << " : success !" << "\n";}system("rm good.exe");system("rm bad.exe");system("rm gen.exe");if (test > 100) system("rm in.txt");system("pause");return 0;
}

#include <bits/stdc++.h>
int main() {for (int i = 1; i <= 51; i++) {std::string in = std::to_string(i) + ".in";std::string out = std::to_string(i) + ".out";std::system(("a.exe < " + in + " > bad.out ").c_str());if (std::system(("fc bad.out " + out).c_str())) {std::cout << i << '\n';std::system("pause");exit(0);}}return 0;
}

计算几何

// 直线 ax + by + c = 0
using point_t = long long;
template <typename T>
struct line {T a, b, c;line(T a, T b, T c) : a(a), b(b), c(c) {};Line (T x1, T y1, T x2, T y2) {a = y1 - y2;b = x2 - x1;c = x1 * y2 - y1 * x2;}void normalize() { // 前提是 int 或者是 long long 标准化T g = std::gcd(std::gcd(abs(a), abs(b)), abs(c));a /= g, b /= g, c /= g;if (a < 0) a = -a, b = -b, c = -c;}template<typename U>T getY(U x) {assert(b != 0);return (-c - a * x) / b;} // x -> y 整数: 需要特判是否 % b == 0 template<typename U>T getX(U y) {assert(a != 0);return (-c - b * y) / a;} // y -> x 整数: 需要特判是否 % a == 0 template<typename U> long double dis (U x, U y) {return sqrt((a * x + b * y + c) * (a * x + b * y + c) / (a * a + b * b));} // 点到直线的距离bool parallel(line<T> rhs) {return a * rhs.b - b * rhs.a == 0;}   // 平行bool orthogonal(line<T> rhs) {return a * rhs.a + b * rhs.b == 0;} // 垂直
};
using Line = line<point_t>;// 两直线求交点
Point getPoint (Line lhs, Line rhs) { // 可能会爆 i128LL D = lhs.a * rhs.b - rhs.a * lhs.b;assert(D != 0);if ((lhs.b * rhs.c - rhs.b * lhs.c) % D != 0) return {-1, -1};if (-(lhs.a * rhs.c - rhs.a * lhs.c) % D != 0) return {-1, 1};LL x = (lhs.b * rhs.c - rhs.b * lhs.c) / D;LL y = -(lhs.a * rhs.c - rhs.a * lhs.c) / D;return {x, y};
};

// Point 均只依赖结构体
using LL = long long;
using db = long double;
const db eps = 1E-12;struct Point {LL x, y;Point(LL x = 0, LL y = 0) : x(x), y(y) {}
};
LL norm(Point a) {return a.x * a,x + a.y * a.y;} // 范数
db abs(Point a) {return std::sqrt(a.x * a,x + a.y * a.y);} // 模长
LL dot(Point a, Point b) {return a.x * b.x + a.y * b.y;} // 点积
LL cross(Point a, Point b) {return a.x * b.y - a.y * b.x;} // 叉积
LL double_area(Point a, Point b, Point c) { // 面积LL x1 = b.x - a.x, y1 = b.y - a.y;LL x2 = c.x - a.x, y2 = c.y - a.y;return std::abs(x1 * y2 - x2 * y1);
}
db dis1(Point a, Point b) {return std::sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));} // 欧氏距离
LL dis2(Point a, Point b) {return std::abs(a.x - b.x) + std::abs(a.y - b.y);} //曼哈顿距离
LL dis3(Point a. Point b) {return std::max(std::abs(a.x - b.x), std::max(a.y - b,y))} //切比雪夫距离
bool argcmp(Point a, Point b) { // 极角排序auto quad = [](Point t) {if(t.x > 0 && t.y >= 0)  return 1;if(t.x <= 0 && t.y > 0)  return 2;if(t.x < 0 && t.y <= 0)  return 3;if(t.x >= 0 && t.y < 0)  return 4;}int qa = quad(a), qb = quad(b);if (qa != qb) return qa < qb;return a.x * b.y - a.y * b.x > eps;
}

//多边形
LL double_area(const std::vector<Point>& p) {const int n = p.size();assert(p.size () >= 3);LL res = 0;for (int i = 0; i < n; i++) {res += (p[i].x * p[(i + 1) % n].y) - (p[i].y * p[(i + 1) % n].x);}return res;
}

牛客

高精度

// 高精度
namespace Int {bool cmp(const std::string &a, const std::string& b) {return a.size() > b.size() || (a.size() == b.size() && a >= b);}std::string rev(std::string& res) {std::reverse(res.begin(), res.end()); return res;}std::string norm(const std::string& res) {for (int i = 0; i < res.size(); i++) if (res[i] != '0') return res.substr(i);return "0";}std::string add (std::string a, std::string b) {std::string res;if (a.size() < b.size()) std::swap(a, b);for (int i = a.size() - 1, j = b.size() - 1, t = 0; i >= 0; i--, j--) {if (j >= 0) t += b[j] - '0';t += a[i] - '0';res += char(t % 10 + '0');t /= 10;if (!i && t) res += char(t + '0');}return rev(res);};std::string sub(std::string a, std::string b) {int neg = 0;if(!cmp(a, b)) {std::swap(a, b);neg = 1;}std::string res;for (int i = a.size() - 1, j = b.size() - 1, t = 0; i >= 0; i--, j--) {if (j >= 0) t -= (b[j] - '0');t += a[i] - '0';if(t < 0) res += char(t + 10 + '0'), t = -1;else res += char(t % 10 + '0'), t /= 10;}if (neg) return '-' + norm(rev(res));return norm(rev(res));}std::string mul(const std::string &a, const std::string &b) {std::string res(a.size() + b.size(), 0);for(int i = a.size() - 1, n = a.size() - 1; i >= 0; i--){for(int j = b.size() - 1, m = b.size() - 1; j >= 0; j--){res[n - i + m - j] += (a[i] - '0') * (b[j] - '0');res[n - i + m - j + 1] += res[n - i + m - j] / 10;res[n - i + m - j] %= 10;}}for (char &ch : res) ch += '0';return norm(rev(res));}std::pair<std::string,long long> div(const std::string &a, int d) {std::string res;long long cur = 0;for(int i = 0; i < a.size(); i++){cur = cur * 10 + (a[i] - '0');res += char(cur / d + '0');cur %= d;}return {norm(res), cur};}std::pair<std::string,std::string> div(const std::string &a,const std::string &b) {std::string res, cur;for (int i = 0, cnt = 0; i < a.size(); i++, cnt = 0) {cur = norm(cur + a[i]);while (cmp(cur, b)) cnt++, cur = sub(cur, b);res += char(cnt + '0');}return {norm(res), norm(cur)};}
};
using namespace Int;

Rho

bool primetest(const uint64_t x) { assert(x > 1 && x < uint64_t(1) << 62);auto modPower = [](uint64_t x, uint64_t exp, uint64_t P) -> uint64_t{uint64_t ans = 1;for (x = (x % P + P) % P; exp > 0; x = __int128_t(x) * x % P, exp /= 2)if (exp % 2) ans = __int128_t(ans) * x % P; return ans;};if (x == 2 || x == 3 || x == 5 || x == 7) return true;if (x % 2 == 0 || x % 3 == 0 || x % 5 == 0 || x % 7 == 0) return false;if (x < 121) return x > 1;const uint64_t d = (x - 1) >> __builtin_ctzll(x - 1), mod = x, one = 1, minus_one = x - 1;auto ok = [&](uint64_t a) -> bool { uint64_t y = modPower(a, d, x), t = d;while (y != one && y != minus_one && t != x - 1) y = __int128_t(y) * y % mod, t <<= 1;if (y != minus_one && t % 2 == 0) return false; return true;};if (x < (uint64_t(1) << 32)) for (uint64_t a: {2, 7, 61}) {if (!ok(a)) return false;}else for (uint64_t a: {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) if (!ok(a)) return false;return true;
}
int64_t rho(int64_t n, int64_t c) { assert(n > 1 && c >= 0);const int64_t mod = n, cc = (c % mod + mod) % mod, m = 1LL << ((63 - __builtin_clzll(n)) / 5);auto f = [&](uint64_t x) {return (__int128_t(x) * x % mod + cc) % mod;};int64_t x = 1, y = 2, z = 1, q = 1, g = 1;for (int64_t r = 1; g == 1; r <<= 1, g = std::gcd(q, n)) {x = y; for(int i = 0; i < r; i++) y = f(y);for (int64_t k = 0; k < r && g == 1; k += m) { z = y;for (int i = 0; i < std::min(m, r - k); i++) y = f(y), q = (__int128_t(q) * ((x - y) % mod + mod) % mod) % mod;}}if (g == n)for (int64_t lhs = 1; std::gcd(lhs, n) == 1;lhs = ((x - z) % mod + mod) % mod) z = f(z);return g;
}
std::vector<std::pair<int64_t, int>> factor(int64_t n) {std::vector<std::pair<int64_t, int>> pf;while (n > 1) { int64_t p = n, e = 0;while (!primetest(p)) p = rho(p, rand() % p);while (n % p == 0) n /= p, e++; pf.emplace_back(p, e);}std::sort(pf.begin(), pf.end()); return pf;
}
std::vector<int64_t> divisors_by_pf(const std::vector<std::pair<int64_t, int>> &pf) {std::vector<int64_t> div = {1};for (const auto &[p, e]: pf) for (int64_t pp = p, n = div.size(), i = 1; i <= e; i++, pp *= p) for (int j = 0; j < n; j++)  div.emplace_back(div[j] * pp);return div;
}
std::vector<int64_t> divisors(int64_t N) {auto pf = factor(N); return divisors_by_pf(pf);}

悬绳法

    for (int i = 1; i <= n; i++) {L[i] = R[i] = i;        }for (int i = 1; i <= n; i++) {while (L[i] != 1 && a[L[i] - 1] >= a[i]) {L[i] = L[L[i] - 1];            }}for (int i = n; i >= 1; i--) {while (R[i] != n && a[R[i] + 1] >= a[i]) {R[i] = R[R[i] + 1];            }}

莫队

    struct node {int l, r, x, id;};std::vector<node> Q(q);for (int i = 0; i < q; i++) {auto &[l, r, x, id] = Q[i];std::cin >> l >> r >> x;id = i;}int B = std::min(500, (int)std::pow(n * 0.666));std::sort(Q.begin(), Q.end(), [&](auto t1, auto t2) {if (t1.l / B != t2.l / B) return t1.l < t2.l;if ((t1.l / B) % 2) return t1.r < t2.r;return t1.r > t2.r;});std::vector<int> ans(q);int l = 1, r = 0;// auto add = [&](int id) {// };// auto del = [&](int id) {// };for (int i = 0; i < Q; i++) {auto [ql, qr, qx, id] = Q[i];while (l > ql) add(--l);while (r < qr) add(++r);while (l < ql) del(l++);while (r > qr) del(r--);}for (int i = 0; i < q; i++) {std::cout << (ans[i] ? "YES" : "NO") << '\n';}//强制在线莫队算法
#include<bits/stdc++.h>
using namespace std;
#define N 233333
#define M 1111111
int sum, cnt[M], a[N], ans[N], sz;
struct ques {int l, r, t, id;
} qq[N], qr[N];
inline void add(int x) {sum+=!cnt[x]++;}
inline void del(int x) {sum-=!--cnt[x];}
inline void upd(int x, int t) {if (qq[x].l<=qr[t].l&&qr[t].l<=qq[x].r) {del(a[qr[t].l]);add(qr[t].r);}swap(a[qr[t].l], qr[t].r);
}
bool cmp (const ques &a, const ques &b) {return a.l/sz==b.l/sz? a.r/sz==b.r/sz ? a.t<b.t : a.r<b.r : a.l<b.l;
}
int main() {int n, m;cin >> n >> m;sz = std::max(500, pow(n,0.666));int cntq = 0, cntr = 0;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 1; i <= m; i++){char op;int l, r;cin>> op >> l >> r;if (op == 'Q') {++cntq;qq[cntq].id = cntq;qq[cntq].t = cntr;qq[cntq].l = l, qq[cntq].r = r;}else qr[++cntr].l = l, qr[cntr].r = r;}sort(qq + 1, qq + cntq + 1, cmp);int l = 1, r = 0, t = 0;for (int i = 1; i <= cntq; i++) {while (l > qq[i].l) add(a[--l]);while (l < qq[i].l) del(a[l++]);while (r > qq[i].r) del(a[r--]);while (r < qq[i].r) add(a[++r]);while (t < qq[i].t) upd(i, ++t);while (t > qq[i].t) upd(i, t--);ans[qq[i].id] = sum;}for (int i = 1; i <= cntq; i++) cout << ans[i] << '\n';return 0;
}

随机化

std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

结论

• 范德蒙德卷积

\[\sum_{i} ^ {k}\binom{n}{i} \binom{m}{k - i} = \binom{n + m}{k} \]

• 恒等式

\[k\binom{n}{k} = n\binom{n - 1}{k - 1} \]

• 插板法 : 每个元素都是相同的, 分成的组，每组的元素不为空 (假设每个篮子可以为空，可以想象为多了 m个相同的球)

\[\binom{m - 1}{n - 1} -> \binom{m - 1}{n + m - 1} \]

• 分数形式的二分 => 0/1 分数规划