算法模板初稿
2026/1/31大约 14 分钟
算法模板初稿
杂项
重载__int128的输入输出
std::ostream& operator<<(std::ostream& os, __int128 n) { if (n == 0) return os << 0; if (n < 0) return os << '-' << -n; std::string s; while (n > 0) { s += char('0' + n % 10); n /= 10; } std::reverse(s.begin(), s.end()); return os << s; } std::istream& operator>>(std::istream& is, __int128& x) { char c; while(c = is.get(), c != '-' && !isdigit(c)); if(c == '-') { x = '0' - is.get(); while(isdigit(c = is.get())) x = x * 10 + '0' - c; } else { x = c - '0'; while(isdigit(c = is.get())) x = x * 10 - '0' + c; } return is; }
数学
快速傅里叶变换
void FFT(complex<double> A[], int n, int op) { if (n == 1) return; complex<double> A1[n / 2], A2[n / 2]; for (int i = 0; i < n / 2; i++) A1[i] = A[2 * i], A2[i] = A[2 * i + 1]; FFT(A1, n / 2, op), FFT(A2, n / 2, op); complex<double> w1(cos(2 * PI / n), sin(2 * PI / n) * op); complex<double> wk(1, 0); for (int i = 0; i < n / 2; i++) { A[i] = A1[i] + A2[i] * wk; A[i + n / 2] = A1[i] - A2[i] * wk; wk = wk * w1; } } // 例子： // P3803 【模板】多项式乘法（FFT） const int N = 4e6 + 10; const double PI = acos(-1); complex<double> a[N], b[N]; signed main() { int n, m; cin >> n >> m; for (int i = 0; i <= n; i++) cin >> a[i]; for (int j = 0; j <= m; j++) cin >> b[j]; for (m = n + m, n = 1; n <= m; n <<= 1); FFT(a, n, 1), FFT(b, n, 1); for (int i = 0; i < n; i++) a[i] = a[i] * b[i]; FFT(a, n, -1); for (int i = 0; i <= m; i++) { cout << (int)(a[i].real() / n + 0.5) << ' '; } return 0; } // P1919 【模板】高精度乘法 | A*B Problem 升级版 const int N = 4e6 + 10; const double PI = acos(-1); complex<double> a[N], b[N]; int ans[N]; signed main() { string s1, s2; cin >> s1 >> s2; int n = s1.size() - 1, m = s2.size() - 1; for (int i = s1.size() - 1, k = 0; i >= 0; i--, k++) a[k] = s1[i] - '0'; for (int i = s2.size() - 1, k = 0; i >= 0; i--, k++) b[k] = s2[i] - '0'; for (m = n + m, n = 1; n <= m; n <<= 1); FFT(a, n, 1), FFT(b, n, 1); for (int i = 0; i < n; i++) a[i] = a[i] * b[i]; FFT(a, n, -1); int t = 0, k = 0; for (int i = 0; i < n || t; i++) { t += (int)(a[i].real() / n + 0.5); ans[k++] = t % 10; t /= 10; } while (k > 1 && ans[k - 1] == 0) k--; for (int i = k - 1; i >= 0; i--) cout << ans[i]; return 0; }矩阵快速幂
const int mod = 1e9 + 7; const int N = 3; struct Matrix { int a[N + 1][N + 1]; Matrix() { memset(a, 0, sizeof a); } void setE() { for (int i = 1; i <= N; i++) a[i][i] = 1; } Matrix operator*(const Matrix& m) { Matrix res; for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { for (int k = 1; k <= N; k++) { res.a[i][j] = (res.a[i][j] + a[i][k] * m.a[k][j]) % mod; } } } return res; } }; Matrix ksm(Matrix a, int k) { Matrix res; res.setE(); while (k) { if (k & 1) res = res * a; a = a * a; k >>= 1; } return res; }快速幂
int ksm(int a, int k, int mod) { int res = 1 % mod; a %= mod; while (k) { if (k & 1) res = 1LL * a * res % mod; a = 1LL * a * a % mod; k >>= 1; } return res; }欧拉筛
const int N = 2e6 + 10; int primes[N], vis[N], cnt; void euler() { vis[1] = 1; for (int i = 2; i < N; i++) { if (!vis[i]) primes[cnt++] = i; for (int j = 0; i * primes[j] < N; j++) { vis[i * primes[j]] = 1; if (i % primes[j] == 0) break; } } }欧拉函数
// 求解单个 phi(n) 时间复杂度O(sqrt(n)) int phi(int n) { int ans = n; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { ans = ans / i * (i - 1); while (n % i == 0) n /= i; } } if (n > 1) ans = ans / n * (n - 1); return ans; } // 利用欧拉筛求多个 const int N = 2e6 + 10; int primes[N], cnt, vis[N], phi[N]; void euler() { phi[1] = vis[1] = 1; for (int i = 2; i < N; i++) { if (!vis[i]) { primes[cnt++] = i; phi[i] = i - 1; } for (int j = 0; i * primes[j] < N; j++) { vis[i * primes[j]] = 1; if (i % primes[j] == 0) { phi[i * primes[j]] = primes[j] * phi[i]; break; } else { phi[i * primes[j]] = phi[i] * phi[primes[j]]; } } } }筛法求约数个数
const int N = 1e6 + 10; int primes[N], vis[N], cnt; int a[N]; // a[i]记录i的最小质因子的次数 int d[N]; // d[i]记录i的约数的个数 void euler() { vis[1] = d[1] = 1; for (int i = 2; i < N; i++) { if (!vis[i]) { primes[cnt++] = i; a[i] = 1, d[i] = 2; } for (int j = 0; i * primes[j] < N; j++) { int m = i * primes[j]; vis[m] = 1; if (i % primes[j] == 0) { a[m] = a[i] + 1; d[m] = d[i] / a[m] * (a[m] + 1); break; } a[m] = 1; d[m] = 2 * d[i]; } } }筛法求约数和
const int N = 1000010; int p[N], vis[N], cnt; // g[i]表示i的最小质因子的1+p^1+...+p^k int g[N], f[N];// f[i]表示i的约数和 void get_f(int n) { // 筛法求约数和 g[1] = f[1] = 1; for (int i = 2; i <= n; i++) { if (!vis[i]) { p[++cnt] = i; g[i] = f[i] = i + 1; } for (int j = 1; i * p[j] <= n; j++) { int m = i*p[j]; vis[m] = 1; if (i % p[j] == 0) { g[m] = g[i] * p[j] + 1; f[m] = f[i] / g[i] * g[m]; break; } g[m] = p[j] + 1; f[m] = f[i] * g[m]; } } }筛法求莫比乌斯函数
const int N = 1000010; int p[N], vis[N], cnt; int mu[N]; void get_mu(int n) { // 筛法求莫比乌斯函数 mu[1] = 1; for (int i = 2; i <= n; i++) { if (!vis[i]) { p[++cnt] = 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; } mu[m] = -mu[i]; } } }BSGS
typedef long long LL; // 求最小的满足 a^x % p = b 的 x，要求 a 与 p 互质 LL bsgs(LL a, LL b, LL p) { a %= p; b %= p; if (b == 1) return 0; // x=0 LL m = ceil(sqrt(p)); LL t = b; unordered_map<int, int> hash; hash[b] = 0; for (int j = 1; j < m; j++) { t = t*a % p; // 求b*a^j hash[t] = j; } LL mi = 1; for (int i = 1; i <= m; i++) mi = mi * a % p; // 求a^m t = 1; for (int i = 1; i <= m; i++) { t = t*mi % p; // 求(a^m)^i if (hash.count(t)) return i * m - hash[t]; } return -1; // 无解 }ex_bsgs
typedef long long LL; LL exbsgs(LL a, LL b, LL p) { a %= p; b %= p; if (b == 1 || p == 1)return 0; //x=0 LL d, k = 0, A = 1; while (true) { d = gcd(a, p); if (d == 1) break; if (b % d) return -1; //无解 k++; b /= d; p /= d; A = A*(a / d) % p; //求a^k/D if (A == b) return k; } LL m = ceil(sqrt(p)); LL t = b; unordered_map<int, int> hash; hash[b] = 0; for (int j = 1; j < m; j++) { t = t*a % p; //求b*a^j hash[t] = j; } LL mi = 1; for (int i = 1; i <= m; i++) mi = mi * a % p; //求a^m t = A; for (int i = 1; i <= m; i++) { t = t*mi % p; //求(a^m)^i if (hash.count(t)) return i * m - hash[t] + k; } return -1; //无解 }ex_gcd
int exgcd(int a, int b, int& x, int& y) { if (a == 0) { x = 0, y = 1; return b; } else { int d = exgcd(b % a, a, x, y); swap(x, y); x -= b / a * y; return d; } }线性基
struct XXJ { vector<int> ji; int n; XXJ(int n = 31) { this->n = n; ji.resize(n + 1, 0); } void insert(int x) { for (int i = n; i >= 0; i--) { if ((x >> i) & 1) { if (!ji[i]) { ji[i] = x; break; } else { x = x ^ ji[i]; } } } } int qmin(int t = 0) { int res = t; for (int i = this->n; i >= 0; i--) { res = min(res, res ^ ji[i]); } return res; } int qmax(int t = 0) { int res = t; for (int i = this->n; i >= 0; i--) { res = max(res, res ^ ji[i]); } return res; } };高精度
高斯消元
分解质因数
组合数
// 求组合数 1 (乘法逆元) const int N = 1e5 + 10; const int mod = 1e9 + 7; int fact[N], infact[N]; int ksm(int a, int k, int mod) { int res = 1; a %= mod; while (k) { if (k & 1) res = 1LL * res * a % mod; a = 1LL * a * a % mod; k >>= 1; } return res; } void init() { infact[0] = fact[0] = 1; for (int i = 1; i < N; i++) { fact[i] = 1LL * fact[i - 1] * i % mod; infact[i] = 1LL * infact[i - 1] * ksm(i, mod - 2, mod) % mod; } } // 从 n 个里面选 m 个 int C(int n, int m) { return (1LL * fact[n] * infact[n - m] % mod) * infact[m] % mod; } --------------------------------------------------------------------------------------------------------------- // 求组合数 2 (杨辉三角递推) const int N = 2010, P = 1e9+7; int C[N][N]; void init() { for (int i = 0; i < N; i++) C[i][0] = 1; for (int i = 1; i < N; i++) for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P; } --------------------------------------------------------------------------------------------------------------- // 求组合数 3 (卢卡斯定理) https://www.luogu.com.cn/problem/P3807 typedef long long LL; const int N = 100010; LL f[N], g[N]; // f[i] 表示 i 的阶乘, g[i] 表示 i 的阶乘的逆元 LL qpow(LL a, int b, int p) { LL res = 1; while (b) { if (b & 1) res = res * a % p; a = a * a % p; b >>= 1; } return res; } void init(int p) { f[0] = g[0] = 1; for (int i = 1; i <= p; i++) { f[i] = f[i - 1] * i % p; g[i] = g[i - 1] * qpow(i, p - 2, p) % p; } } LL getC(int n, int m, int p) { return f[n] * g[m] * g[n - m] % p; } int lucas(LL n, LL m, int p) { if (m == 0) return 1; return lucas(n / p, m / p, p) * getC(n % p, m % p, p) % p; }
字符串
马拉车
// P3805 【模板】manacher #include <bits/stdc++.h> using namespace std; signed main() { string a; cin >> a; string s = "$#"; for (int i = 0; i < a.size(); i++) { s += a[i]; s += '#'; } vector<int> d(s.size() + 1); d[1] = 1; for (int i = 2, l = 0, r = 1; i < s.size(); i++) { if (i <= r) d[i] = min(d[l + r - i], r - i + 1); while (s[i - d[i]] == s[i + d[i]]) d[i]++; if (i + d[i] - 1 > r) r = i + d[i] - 1, l = i - d[i] + 1; } int ans = 0; for (int i = 1; i < s.size(); i++) ans = max(ans, d[i]); cout << ans - 1 << endl; return 0; }kmp
最小表示
// P1368 工艺 #include <bits/stdc++.h> using namespace std; const int N = 6e5 + 10; int a[N]; signed main() { int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) a[i + n] = a[i]; int i = 1, j = 2, k = 0; while (i <= n && j <= n) { for (k = 0; a[i + k] == a[j + k]; k++); if (a[i + k] > a[j + k]) i = i + k + 1; else j = j + k + 1; if (i == j) j++; } int ans = min(i, j); for (i = ans; i <= ans + n - 1; i++) cout << a[i] << ' '; return 0; }字符串哈希
#include <bits/stdc++.h> using namespace std; using ULL = unsigned long long; const int N = 100010; ULL p[N], h[N]; int n, m, P = 131; string s; ULL get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; } int main() { cin >> n >> m; cin >> s; s = ' ' + s; p[0] = 1; for (int i = 1; i <= n; i++) { p[i] = p[i - 1] * P; h[i] = h[i - 1] * P + s[i]; } while (m--) { int l1, l2, r1, r2; cin >> l1 >> r1 >> l2 >> r2; if (get(l1, r1) == get(l2, r2)) cout << "Yes" << endl; else cout << "No" << endl; } return 0; }字典树
数据结构
线段树
// 支持区间加，区间乘，区间和的查询。来源：P3373 【模板】线段树 2 const int N = 1e5 + 10; int a[N], n, mod; struct Node { int l, r; int sum, add, mul; } tr[4 * N]; void pushup(Node& rt, Node& le, Node& ri) { rt.sum = (le.sum + ri.sum) % mod; } void pushdown(int u) { Node& rt = tr[u], & le = tr[u << 1], & ri = tr[u << 1 | 1]; if (rt.mul == 1 && rt.add == 0) return; le.sum = (le.sum * rt.mul % mod + rt.add * (le.r - le.l + 1) % mod) % mod; le.mul = le.mul * rt.mul % mod; le.add = (le.add * rt.mul + rt.add) % mod; ri.sum = (ri.sum * rt.mul % mod + rt.add * (ri.r - ri.l + 1) % mod) % mod; ri.mul = ri.mul * rt.mul % mod; ri.add = (ri.add * rt.mul + rt.add) % mod; rt.mul = 1; rt.add = 0; } void build(int u, int l, int r) { tr[u] = {l, r, 0, 0, 1}; if (l == r) tr[u].sum = a[l] % mod; else { int mid = (l + r) >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); pushup(tr[u], tr[u << 1], tr[u << 1 | 1]); } } void changeMul(int u, int l, int r, int k) { if (l <= tr[u].l && tr[u].r <= r) { tr[u].sum = tr[u].sum * k % mod; tr[u].add = tr[u].add * k % mod; tr[u].mul = tr[u].mul * k % mod; } else { pushdown(u); int mid = (tr[u].l + tr[u].r) >> 1; if (r <= mid) changeMul(u << 1, l, r, k); else if (l > mid) changeMul(u << 1 | 1, l, r, k); else { changeMul(u << 1, l, mid, k); changeMul(u << 1 | 1, mid + 1, r, k); } pushup(tr[u], tr[u << 1], tr[u << 1 | 1]); } } void changeAdd(int u, int l, int r, int k) { if (l <= tr[u].l && tr[u].r <= r) { tr[u].sum = (tr[u].sum + (tr[u].r - tr[u].l + 1) * k % mod) % mod; tr[u].add = (tr[u].add + k) % mod; } else { pushdown(u); int mid = (tr[u].l + tr[u].r) >> 1; if (r <= mid) changeAdd(u << 1, l, r, k); else if (l > mid) changeAdd(u << 1 | 1, l, r, k); else { changeAdd(u << 1, l, mid, k); changeAdd(u << 1 | 1, mid + 1, r, k); } pushup(tr[u], tr[u << 1], tr[u << 1 | 1]); } } int query(int u, int l, int r) { if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum; pushdown(u); int mid = (tr[u].l + tr[u].r) >> 1; if (r <= mid) return query(u << 1, l, r); else if (l > mid) return query(u << 1 | 1, l, r); else return (query(u << 1, l, mid) + query(u << 1 | 1, mid + 1, r)) % mod; }树状数组
// 来自 NotOnlySuccess const int mod = 1e9+7; template<typename T> T pred(T a, T b) { return (a + b) % mod; } template<typename T, T (*Pred)(T, T) = pred<T>, T Init = 0> struct BIT { public: size_t n; vector<T> data; BIT(size_t n): BIT(vector<T>(n + 1, Init)) {} BIT(const vector<T> &v): n(v.size() - 1), data(v) { for (size_t i = 1; i <= n; i ++) { size_t j = i + (i & -i); if (j <= n) data[j] = Pred(data[j], data[i]); } } void update(size_t i, T v = 1) { i ++; for (; i <= n; i += i & -i) { data[i] = Pred(data[i], v); } } T query(size_t i) { i ++; T res = Init; for (; i; i -= i & -i) { res = Pred(res, data[i]); } return res; } T query(size_t l, size_t r) { return query(r) - query(l - 1); } int lower_bound(T x) { T sum = Init; int index = 0; for (size_t i = 1 << __lg(n); i; i >>= 1) { if (index + i <= n && sum + data[index + i] < x) { index += i; sum += data[index]; } } return index + 1; } };并查集
struct DSU { vector<int> fa, p, e, f; DSU(int n) { fa.resize(n + 1); iota(fa.begin(), fa.end(), 0); p.resize(n + 1, 1); e.resize(n + 1); f.resize(n + 1); } int get(int x) { while (x != fa[x]) { x = fa[x] = fa[fa[x]]; } return x; } bool merge(int x, int y) { // 设x是y的祖先 if (x == y) f[get(x)] = 1; x = get(x), y = get(y); e[x]++; if (x == y) return false; if (x < y) swap(x, y); // 将编号小的合并到大的上 fa[y] = x; f[x] |= f[y], p[x] += p[y], e[x] += e[y]; return true; } bool same(int x, int y) { return get(x) == get(y); } bool F(int x) { // 判断连通块内是否存在自环 return f[get(x)]; } int size(int x) { // 输出连通块中点的数量 return p[get(x)]; } int E(int x) { // 输出连通块中边的数量 return e[get(x)]; } };可持久化线段树
ST表
struct SparseTable { vector<vector<int>> st; vector<int> log_table; void build(vector<int>& arr) { int n = arr.size(); log_table.resize(n + 1); log_table[1] = 0; for (int i = 2; i <= n; i++) { log_table[i] = log_table[i / 2] + 1; } int k = log_table[n] + 1; st.resize(n, vector<int>(k)); for (int i = 0; i < n; i++) { st[i][0] = arr[i]; } for (int j = 1; j < k; j++) { for (int i = 0; i + (1 << j) <= n; i++) { st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); } } } int query(int l, int r) { // 查询 [l, r] 闭区间最大值 int j = log_table[r - l + 1]; return max(st[l][j], st[r - (1 << j) + 1][j]); } };取模数（modint）
template<int mod> struct modint { int _v; // 初始化 modint() : _v(0) {} template<typename T> modint(T v) : _v((v % mod + mod) % mod) {} // 一元操作符 modint& operator++() { _v ++; if (_v == mod) _v = 0; return *this; } modint& operator--() { if (_v == 0) _v = mod; _v --; return *this; } modint operator++(int) { modint temp = *this; _v ++; return temp; } modint operator--(int) { modint temp = *this; _v --; return temp; } modint operator+() const { return *this; } modint operator-() const { return modint(0) - *this; } // 自运算 modint& operator+= (const modint& rhs) { _v += rhs._v; if (_v >= mod) _v -= mod; return *this; } modint& operator-= (const modint& rhs) { _v -= rhs._v; if (_v < 0) _v += mod; return *this; } modint& operator*= (const modint& rhs) { _v = (unsigned long long)_v * rhs._v % mod; return *this; } modint& operator/= (const modint& rhs) { return *this *= rhs.inv(); } // 二元运算 friend modint operator+ (const modint& lhs, const modint& rhs) { return modint(lhs._v) += rhs; } friend modint operator- (const modint& lhs, const modint& rhs) { return modint(lhs._v) -= rhs; } friend modint operator* (const modint& lhs, const modint& rhs) { return modint(lhs._v) *= rhs; } friend modint operator/ (const modint& lhs, const modint& rhs) { return modint(lhs._v) /= rhs; } friend bool operator== (const modint& lhs, const modint& rhs) { return lhs._v == rhs._v; } friend bool operator!= (const modint& lhs, const modint& rhs) { return lhs._v != rhs._v; } // 逆元，默认 mod 是质数 modint inv() const { modint res = 1, x = _v; for (int n = mod - 2; n; n /= 2, x *= x) { if (n & 1) res *= x; } return res; } // 输入输出 friend ostream& operator<< (ostream& os, const modint& rhs) { return os << rhs._v; } friend istream& operator>> (istream& is, modint& rhs) { return is >> rhs._v; } }; using mint = modint<998244353>; // using mint = modint<1000000007>;矩阵（matrix）
using i64 = int64_t; template<typename T, size_t N> struct matrix { array<array<T, N>, N> a = {{{0}}}; matrix() { for (size_t i = 0; i < N; i ++) a[i][i] = 1; } matrix(const array<array<T, N>, N> &a) : a(a) {} matrix operator*(const matrix<T, N> &b) const { matrix<T, N> res = {{{0}}}; for (size_t i = 0; i < N; i ++) { for (size_t k = 0; k < N; k ++) { for (size_t j = 0; j < N; j ++) { res[i][j] += a[i][k] * b[k][j]; } } } return res; } matrix& operator*= (const matrix &b) { return *this = *this * b; } matrix operator^(i64 p) const { matrix<T, N> res; auto a = *this; for (; p; p >>= 1, a *= a) if (p & 1) res *= a; return res; } matrix& operator^= (i64 p) { return *this = *this ^ p; } array<T, N>& operator[](size_t i) { return a[i]; } const array<T, N>& operator[](size_t i) const { return a[i]; } friend istream& operator>> (istream& is, matrix &a) { for (size_t i = 0; i < N; i ++) { for (size_t j = 0; j < N; j ++) { is >> a[i][j]; } } return is; } friend ostream& operator<< (ostream& os, const matrix &a) { for (size_t i = 0; i < N; i ++) { for (size_t j = 0; j < N; j ++) { os << a[i][j] << ' '; } os << '\n'; } return os; } };线段树（seg_tree）
class SegTree { public: struct node { int l, r, x, lz; }; explicit SegTree(const int n) : tr((n + 1) << 2), n(n) { build(1, 1, n); } // 数组信息需要储存在 1~n explicit SegTree(const std::vector<int>& a) : tr(a.size() << 2), n(a.size() - 1) { build(1, 1, n, a); } void build(const int u, const int l, const int r) { tr[u] = {l, r, 0, 0}; if (l == r) return; const int mid = (l + r) >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); } void build(const int u, const int l, const int r, const std::vector<int>& a) { tr[u] = {l, r, 0, 0}; if (l == r) { tr[u].x = a[l]; return; } const int mid = (l + r) >> 1; build(u << 1, l, mid, a); build(u << 1 | 1, mid + 1, r, a); pushup(u); } void pushup(const int u) { tr[u].x = tr[u << 1].x + tr[u << 1 | 1].x; } void pushdown(const int u) { if (tr[u].lz) { tr[u << 1].lz = tr[u << 1].lz + tr[u].lz; tr[u << 1 | 1].lz = tr[u << 1 | 1].lz + tr[u].lz; tr[u << 1].x = tr[u << 1].x + tr[u].lz * (tr[u << 1].r - tr[u << 1].l + 1); tr[u << 1 | 1].x = tr[u << 1 | 1].x + tr[u].lz * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1); tr[u].lz = 0; } } // 区间查询 int query(const int u, const int l, const int r) { if (l <= tr[u].l && tr[u].r <= r) return tr[u].x; pushdown(u); const int mid = (tr[u].l + tr[u].r) >> 1; if (r <= mid) return query(u << 1, l, r); if (l > mid) return query(u << 1 | 1, l, r); return (query(u << 1, l, mid) + query(u << 1 | 1, mid + 1, r)); } // 区间修改 void modify(const int u, const int l, const int r, const int x) { if (r < l) return; if (l <= tr[u].l && tr[u].r <= r) { tr[u].x = tr[u].x + (tr[u].r - tr[u].l + 1) * x; tr[u].lz = tr[u].lz + x; return; } pushdown(u); const int mid = (tr[u].l + tr[u].r) >> 1; if (r <= mid) modify(u << 1, l, r, x); else if (l > mid) modify(u << 1 | 1, l, r, x); else modify(u << 1, l, mid, x), modify(u << 1 | 1, mid + 1, r, x); pushup(u); } // 单点修改 void modify_add(const int u, const int p, const int x) { if (p > n) return; if (tr[u].l == tr[u].r) { tr[u].x = tr[u].x + x; return; } pushdown(u); const int mid = (tr[u].l + tr[u].r) >> 1; if (p <= mid) modify_add(u << 1, p, x); else modify_add(u << 1 | 1, p, x); pushup(u); } private: std::vector<node> tr; int n; };
图论
迪杰斯特拉
Floyd
SPFA
拓扑排序
树的直径
最近公共祖先