准备线下比赛用的模板, 会一直更新, 但更新频率不高。找个代码托管平台放一下或许更合适, 不过暂时没心思做这个。
小提示: 点击任意标题旁边的“显示目录导航”, 再点击右上角的图钉可以固定目录。
约定:
- 所有区间操作都是在闭区间上进行的。
- 编译器要支持 gnu++11 标准
基本框架
$0 是光标位置。
编译参数加个 -DLOCAL 就可以用 debug::operator<< 输出数据以及通过文件 sample.txt 读入样例了。
最好别输出到文件, 万一不小心写了个一直输出的死循环硬盘直接爆炸。
#include <bits/stdc++.h>
#ifdef LOCAL
#define debug_out(x) cerr << x;
#else
#define debug_out(x) ((void)x)
#endif
using namespace std;
using uint = unsigned;
using i64 = long long;
using u64 = unsigned long long;
struct Debug {
template<typename T>
Debug& operator<<(const T& x) {
debug_out(x);
return *this;
}
} debug;
template<typename T> bool chmax(T& a, const T& b) { return a < b ? (a = b, true) : false; }
template<typename T> bool chmin(T& a, const T& b) { return b < a ? (a = b, true) : false; }
const i64 inf = 0x3f3f3f3f3f3f3f3fLL;
int main() {
#ifdef LOCAL
freopen("sample.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin.tie(nullptr)->sync_with_stdio(false);$0
return 0;
}
数据结构
并查集
仅采用路径压缩优化, 单次操作平均复杂度 \(O(\alpha(N))\), 最差 \(O(logN)\)。
struct DSU {
vector<int> f;
DSU(int n = 0) : f(n) { iota(f.begin(), f.end(), 0); }
int find(int x) { return x == f[x] ? x : (f[x] = find(f[x])); }
bool same(int x, int y) { return find(x) == find(y); }
bool unite(int x, int y) {
x = find(x), y = find(y);
return x == y ? false : (f[x] = y, true);
}
};
树状数组
template<typename T>
struct Fenwick {
int n;
vector<int> t;
Fenwick(int n = 0) : n(n), t(n) {}
void add(int p, T x) {
while (p < n) {
t[p] += x;
p |= p + 1;
}
}
T sum(int l, int r) const {
T s[2]{};
int p[2]{l - 1, r};
for (int i : {0, 1}) {
while (~p[i]) {
s[i] += t[p[i]];
p[i] = (p[i] & (p[i] + 1)) - 1;
}
}
return s[1] - s[0];
}
};
ST 表
template<typename T, typename F = function<T(const T&, const T&)>>
struct ST {
vector<vector<T>> t;
F f;
ST(const vector<T>& a = {}, F f = {}) : t{a}, f(f) {
int n = a.size(), w = __lg(n);
t.resize(w + 1);
for (int i = 1; i <= w; ++i) {
t[i].resize(n - (1 << i) + 1);
for (int j = 0; j <= n - (1 << i); ++j)
t[i][j] = f(t[i - 1][j], t[i - 1][j + (1 << i >> 1)]);
}
}
T qry(int l, int r) const {
int w = __lg(r - l + 1);
return f(t[w][l], t[w][r - (1 << w) + 1]);
}
};
线段树
借鉴了 ac-library/atcoder/segtree.hpp。
\(2N\) 空间的非递归线段树, 常数较小, 码量也较小。
支持 \(O(logN)\) 单点改, \(O(1)\) 单点查, \(O(logN)\) 区间查, 特别地, 能 \(O(1)\) 查询整个区间。
template<typename S, S (*op)(S, S), S (*e)()>
struct SegTree {
int n, m;
vector<S> d;
SegTree(const vector<S>& v = {}) : n(v.size()), m(1 << __lg(n)), d(2 * n, e()) {
for (int i = 0; i < n; ++i) d[leaf(i)] = v[i];
for (int i = n - 1; i > 0; --i) pull(i);
}
SegTree(int n) : SegTree(vector<S>(n, e())) {}
void set(int p, const S& x) {
d[p = leaf(p)] = x;
while (p >>= 1) pull(p);
}
S get(int p) const { return d[leaf(p)]; }
S qry(int l, int r) const {
if (l > r) return e();
l = leaf(l), r = leaf(r);
S sl = e(), sr = e();
if (l > r) {
if (l & 1) sl = op(sl, d[l++]);
l >>= 1;
}
while (l <= r) {
if (l & 1) sl = op(sl, d[l++]);
if (~r & 1) sr = op(d[r--], sr);
l >>= 1, r >>= 1;
}
return op(sl, sr);
}
S all() const { return d[1]; }
int leaf(int p) const { return p + m - (p < 2 * n - m ? 0 : n); }
void pull(int p) { d[p] = op(d[2 * p], d[2 * p + 1]); }
};
struct S {
// 结点信息
};
S op(S a, S b) {
// 合并左右信息
}
S e() {
// 初始信息
}
数学
自动取模整数
可以用 iostream 输入输出, 输入会自动取模。
模数超过 \(\lfloor\sqrt{INT64\_MAX}\rfloor+1\) 时自动采用 long double 速乘以免溢出。
inv 用于实现除法, 返回 \(0\) 表示逆元不存在。
+ - * / 的重载写起来差不多, 可以考虑用宏减小码量。
i64 inv(i64 x, i64 m) {
i64 res = 0, v = 1, y = m;
while (x) {
i64 t = y / x;
swap(y -= t * x, x);
swap(res -= t * v, v);
}
if (y != 1) return 0;
return res < 0 ? res + m : res;
}
i64 mul(u64 x, u64 y, i64 P) {
u64 a = x * y, b = u64((long double)x / P * y + 0.5L) * P;
return a - b + (a < b ? P : 0);
}
const i64 P = {/* 给定的模数 */};
struct Z {
i64 v;
Z(i64 v) : v((v % P + P) % P) {}
Z& operator+=(Z o) {
if ((v += o.v) >= P) v -= P;
return *this;
}
Z& operator-=(Z o) {
if ((v -= o.v) < 0) v += P;
return *this;
}
Z& operator*=(Z o) {
v = P <= 3037000450LL ? v * o.v % P : mul(v, o.v, P);
return *this;
}
Z& operator/=(Z o) { return *this *= Z(inv(o.v, P)); }
friend Z operator+(Z x, Z y) { return Z(x) += y; }
friend Z operator-(Z x, Z y) { return Z(x) -= y; }
friend Z operator*(Z x, Z y) { return Z(x) *= y; }
friend Z operator/(Z x, Z y) { return Z(x) /= y; }
friend Z operator==(Z x, Z y) { return x.v == y.v; }
friend Z operator!=(Z x, Z y) { return x.v != y.v; }
friend istream& operator>>(istream& is, Z& x) {
x = Z((is >> x.v, x.v));
return is;
}
friend ostream& operator<<(ostream& os, Z x) { return os << x.v; }
};
扩展欧几里得算法
求关于 \(gcd(a,b)\) 及关于 \(x,y\) 的不定方程 \(ax+by=gcd(a,b)\) 的一组特解, 保证 \(x,y\) 的绝对值在所有特解中是最小的。
设函数返回 \([x_{0},y_{0},g]\),
则通解公式为:
\[\begin{cases} x=x_{0}+k\frac{b}{g}\\ y=y_{0}-k\frac{a}{g}\\ \end{cases} ,k\in\Z\]template<typename T>
array<T, 3> exgcd(T a, T b) {
if (b == 0) return {1, 0, a};
auto [x0, y0, g] = exgcd(b, a % b);
return {y0, x0 - a / b * y0, g};
}
籽馥串（
KMP
\(pi[i]=s[0...i]\) 的最长的相等的真前缀与真后缀的长度
template<typename T>
vector<int> KMP(const T& s) {
int n = s.size();
vector<int> pi(n);
for (int i = 1, j = 0; i < n; ++i) {
while (j && s[i] != s[j]) j = pi[j - 1];
if (s[i] == s[j]) ++j;
pi[i] = j;
}
return pi;
}
Manacher
\(d[l+r]\) 就是以下标 \(\dfrac{l+r}{2}\) 为中心的回文串长度
template<typename T>
vector<int> Manacher(const T& s) {
int n = s.size();
if (n == 0) return {};
vector<int> d(2 * n - 1);
for (int i = 0, l = -1, r = -1; i < 2 * n - 1; ++i) {
int i = (i + 1) >> 1;
int j = i >> 1;
int k = r < i ? 0 : min(r - j, d[2 * (l + r) - i] >> 1);
while (k < i && j + k + 1 < n && s[i - k - 1] == s[j + k + 1]) ++k;
d[i] = (k << 1) + (~i & 1);
if (r < j + k) {
l = i - k;
r = j + k;
}
}
return d;
}
Z 函数
\(z[i]\) 就是以 \(s[i]\) 开头的后缀和 \(s\) 的最长公共前缀
template<typename T>
vector<int> Z(const T& s) {
int n = s.size();
vector<int> z(n, n);
for (int i = 1, l = 0, r = 0; i < n; ++i) {
z[i] = i < r ? min(r - i, z[i - l]) : 0;
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
if (r < i + z[i]) {
l = i;
r = i + z[i];
}
}
return z;
}
后缀数组
求出 \(sa\) 后可以用 \(O(N)\) 求出 \(height\) 数组, \(height[i]=s[i]\) 和 \(s[i+1]\) 的最长公共前缀。
template<typename T>
vector<int> GetSA(const T& s) {
int n = s.size();
if (n == 0) return {};
vector<int> sa(n), rk(n), tmp{}, cnt(n);
iota(sa.begin(), sa.end(), 0);
sort(sa.begin(), sa.end(), [&](int x, int y) { return s[x] < s[y]; });
rk[sa[0]] = 0;
for (int i = 1; i < n; ++i)
rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i - 1]] < s[sa[i]]);
tmp.reserve(n);
for (int w = 1; rk[sa[n - 1]] < n - 1; w <<= 1) {
for (int i = 0; i < w; ++i)
tmp.push_back(n - w + i);
for (int i = 0; i < n; ++i)
if (sa[i] >= w) tmp.push_back(sa[i] - w);
for (int i = 0; i < n; ++i)
++cnt[rk[i]];
for (int i = 1; i < n; ++i)
cnt[i] += cnt[i - 1];
for (int i = n - 1; ~i; --i)
sa[--cnt[rk[tmp[i]]]] = tmp[i];
tmp[sa[0]] = 0;
for (int i = 1; i < n; ++i)
tmp[sa[i]] = tmp[sa[i - 1]] + (rk[sa[i - 1]] < rk[sa[i]] ||
sa[i - 1] + w == n ||
rk[sa[i - 1] + w] < rk[sa[i] + w]);
rk.swap(tmp);
tmp.clear();
fill(cnt.begin(), cnt.begin() + rk[sa[n - 1]] + 1, 0);
}
return sa;
}
template<typename T>
vector<int> GetHeight(const T& s, const vector<int>& sa) {
assert(s.size() == sa.size());
int n = s.size();
if (n <= 1) return {};
vector<int> rk(n), hgt(n - 1);
for (int i = 0; i < n; ++i) rk[sa[i]] = i;
for (int i = 0, h = 0; i < n; ++i) {
if (h != 0) --h;
if (rk[i] == n - 1) continue;
int j = sa[rk[i] + 1];
while (max(i, j) + h < n && s[i + h] == s[j + h]) ++h;
hgt[rk[i]] = h;
}
return hgt;
}