我的算法竞赛模板
[TOC]
__builtin
__builtin_clz(a)
std::hypotl
计算 平方和开平方根
std::hypotl(x, y)
list
std::list<int> list;
list.push_front(0);
std::vector<std::list<int>::iterator> it(N);
it[0] = list.begin();
for (int i = 1; i < N; i++) {
int k, p;
std::cin >> k >> p;
k--;
if (p == 0) {
it[i] = list.insert(it[k], i);
} else {
it[i] = list.insert(std::next(it[k]), i);
}
}
int M;
std::cin >> M;
std::vector<bool> erased(N);
while (M--) {
int x;
std::cin >> x;
x--;
if (!erased[x]) {
list.erase(it[x]);
erased[x] = true;
}
}
for (int x : list) {
std::cout << x + 1 << " ";
}
DSU
struct DSU {
std::vector<int> f, siz;
DSU() {}
DSU(int n) {
init(n);
}
void init(int n) {
f.resize(n);
std::iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
}
int find(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) {
return siz[find(x)];
}
};
DSU with weight
struct DSU {
std::vector<int> f, siz;
std::vector<int> val;
DSU() {}
DSU(int n) {
init(n);
}
void init(int n) {
f.resize(n);
std::iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
val.resize(n);
}
int find(int x) {
if (x == f[x]) {
return x;
}
int root = find(f[x]);
val[x] += val[f[x]];
return f[x] = root;
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y, int w) {
int nx = find(x), ny = find(y);
if (nx == ny) {
return false;
}
if (siz[nx] < siz[ny]) {
std::swap(nx, ny);
std::swap(x, y);
w *= -1;
}
siz[nx] += siz[ny];
val[ny] = val[x] + w - val[y];
f[ny] = nx;
return true;
}
int size(int x) {
return siz[find(x)];
}
};
DSU with rollback
struct DSU {
std::vector<int> siz;
std::vector<int> f;
std::vector<std::array<int, 2>> his;
DSU(int n) : siz(n + 1, 1), f(n + 1) {
std::iota(f.begin(), f.end(), 0);
}
int find(int x) {
while (f[x] != x) {
x = f[x];
}
return x;
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
if (siz[x] < siz[y]) {
std::swap(x, y);
}
his.push_back({x, y});
siz[x] += siz[y];
f[y] = x;
return true;
}
int time() {
return his.size();
}
void revert(int tm) {
while (his.size() > tm) {
auto [x, y] = his.back();
his.pop_back();
f[y] = y;
siz[x] -= siz[y];
}
}
};
ST
template<class T, class Cmp = std::less<T>>
struct RMQ {
const int n;
const Cmp cmp;
std::vector<std::vector<T>> a;
RMQ(const std::vector<T> &init) : n(init.size()), cmp(Cmp()) {
int lg = std::__lg(n);
a.assign(n, std::vector<T>(lg + 1));
for (int j = 0; j <= lg; j++) {
for (int i = 0; i + (1 << j) <= n; i++) {
a[i][j] = (j == 0 ? init[i] : std::min(a[i][j - 1], a[i + (1 << (j - 1))][j - 1], cmp));
}
}
}
T rangeMin(int l, int r) {
int k = std::__lg(r - l);
return std::min(a[l][k], a[r - (1 << k)][k], cmp);
}
};
auto cmpIdx = [](int x, int y) {
if (key[x] != key[y]) {
return key[x] > key[y];
}
return x > y;
};
二分查找：FFFFFTTTTTT
前驱（第一个T）$[lo, hi)$：
int lo = 1, hi = 1E9;
while (lo < hi) {
int m = (lo + hi) / 2;
if (check(m)) {
hi = m;
} else {
lo = m + 1;
}
}
std::cout << lo << "\n";
后继（最大可行值）： TTTTFFFFF（最后一个 T）$[lo, hi]$：
int lo = 1, hi = 1E9;
while (lo < hi) {
int m = (lo + hi + 1) / 2;
if (check(m)) {
lo = m;
} else {
hi = m - 1;
}
}
std::cout << lo << "\n";
partial_sum
前缀和：
std::partial_sum(A.begin(), A.end(), prefix.begin() + 1);
前缀异或和：
std::partial_sum(A.begin(), A.end(), prefix.begin() + 1, [](int a, int b) { return a ^ b; });
后缀和：
std::partial_sum(A.rbegin(), A.rend(), suffix.rbegin() + 1);
int128
std::ostream &operator<<(std::ostream &os, i128 n) {
if (n == 0) {
return os << 0;
}
std::string s;
while (n > 0) {
s += char('0' + n % 10);
n /= 10;
}
std::reverse(s.begin(), s.end());
return os << s;
}
随机数
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
Y conbinator + lambda
bfs + dfs（找环）：
int n, a, b;
std::cin >> n >> a >> b;
a--, b--;
std::vector<std::vector<int>> adj(n);
for (int i = 0; i < n; i++) {
int u, v;
std::cin >> u >> v;
u--, v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
auto bfs = [&](int s) {
std::vector<int> dis(n, -1);
dis[s] = 0;
std::queue<int> q;
q.push(s);
while (!q.empty()) {
auto x = q.front();
q.pop();
for (auto y : adj[x]) {
if (dis[y] == -1) {
dis[y] = dis[x] + 1;
q.push(y);
}
}
}
return dis;
};
auto dis = bfs(b);
int u = -1;
std::vector<int> vis(n);
std::vector<int> par(n), dep(n);
auto dfs = [&](auto self, int x) -> void {
vis[x] = true;
for (auto y : adj[x]) {
if (!vis[y]) {
par[y] = x;
dep[y] = dep[x] + 1;
self(self, y);
} else if (dep[y] < dep[x] - 1) {
for (int i = x; ; i = par[i]) {
if (u == -1 || dis[i] < dis[u]) {
u = i;
}
if (i == y) {
break;
}
}
}
}
};
dfs(dfs, 0);
if (bfs(u)[a] > dis[u]) {
std::cout << "YES\n";
} else {
std::cout << "NO\n";
}
data structure
fenwick:
0base，add(i, a), sum(i), rangeSum(l, r)
select(x)：前缀和不超过 x 的最大位置 。
template <typename T>
struct Fenwick {
int n;
std::vector<T> a;
Fenwick(int n_ = 0) {
init(n_);
}
void init(int n_) {
n = n_;
a.assign(n, T{});
}
void add(int x, const T &v) {
for (int i = x + 1; i <= n; i += i & -i) {
a[i - 1] = a[i - 1] + v;
}
}
T sum(int x) {
T ans{};
for (int i = x; i > 0; i -= i & -i) {
ans = ans + a[i - 1];
}
return ans;
}
T rangeSum(int l, int r) {
return sum(r) - sum(l);
}
int select(const T &k) {
int x = 0;
T cur{};
for (int i = 1 << std::__lg(n); i; i /= 2) {
if (x + i <= n && cur + a[x + i - 1] <= k) {
x += i;
cur = cur + a[x - 1];
}
}
return x;
}
};
二维 fenwick
template <typename T>
struct Fenwick {
int n, m;
std::vector<std::vector<T>> a;
Fenwick(int n_ = 0, int m_ = 0) {
init(n_, m_);
}
void init(int n_, int m_) {
n = n_, m = m_;
a.assign(n, std::vector<T>(m_, T{}));
}
void add(std::pair<int, int> x, const T &v) {
for (int i = x.first + 1; i <= n; i += i & -i) {
for (int j = x.second + 1; j <= m; j += j & -j) {
a[i - 1][j - 1] = a[i - 1][j - 1] + v;
}
}
}
T sum(std::pair<int, int> x) {
T ans{};
for (int i = x.first; i > 0; i -= i & -i) {
for (int j = x.second; j > 0; j -= j & -j) {
ans = ans + a[i - 1][j - 1];
}
}
return ans;
}
T rangeSum(std::pair<int, int> x, std::pair<int, int> y) {
return sum({y.first + 1, y.second + 1}) - sum({y.first + 1, x.second}) - sum({x.first, y.second + 1}) + sum({x.first, x.second});
}
};
SegmentTree:
template<class Info>
struct SegmentTree {
int n;
std::vector<Info> info;
SegmentTree() : n(0) {}
SegmentTree(int n_, Info v_ = Info()) {
init(n_, v_);
}
template<class T>
SegmentTree(std::vector<T> init_) {
init(init_);
}
void init(int n_, Info v_ = Info()) {
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {
n = init_.size();
info.assign(4 << std::__lg(n), Info());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {
info[p] = info[2 * p] + info[2 * p + 1];
}
void modify(int p, int l, int r, int x, const Info &v) {
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {
modify(1, 0, n, p, v);
}
// void rangeOr(int p, int l, int r, int x, int y, int v) {
// if (l >= y || r <= x) {
// return;
// }
// if ((info[p].sumAnd & v) == v) {
// return;
// }
// if (r - l == 1) {
// int nv = (info[p].sumAnd | v);
// info[p] = {nv, nv, std::max(0, nv), std::max(0, nv), std::max(0, nv)};
// return;
// }
// int m = (l + r) / 2;
// rangeOr(2 * p, l, m, x, y, v);
// rangeOr(2 * p + 1, m, r, x, y, v);
// pull(p);
// }
// void rangeOr(int l, int r, int v) {
// rangeOr(1, 0, n, l, r, v);
// }
Info rangeQuery(int p, int l, int r, int x, int y) {
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
}
Info rangeQuery(int l, int r) {
return rangeQuery(1, 0, n, l, r);
}
template<class F>
int findFirst(int p, int l, int r, int x, int y, F &&pred) {
if (l >= y || r <= x) {
return -1;
}
if (l >= x && r <= y && !pred(info[p])) {
return -1;
}
if (r - l == 1) {
return l;
}
int m = (l + r) / 2;
int res = findFirst(2 * p, l, m, x, y, pred);
if (res == -1) {
res = findFirst(2 * p + 1, m, r, x, y, pred);
}
return res;
}
template<class F>
int findFirst(int l, int r, F &&pred) {
return findFirst(1, 0, n, l, r, pred);
}
template<class F>
int findLast(int p, int l, int r, int x, int y, F &&pred) {
if (l >= y || r <= x) {
return -1;
}
if (l >= x && r <= y && !pred(info[p])) {
return -1;
}
if (r - l == 1) {
return l;
}
int m = (l + r) / 2;
int res = findLast(2 * p + 1, m, r, x, y, pred);
if (res == -1) {
res = findLast(2 * p, l, m, x, y, pred);
}
return res;
}
template<class F>
int findLast(int l, int r, F &&pred) {
return findLast(1, 0, n, l, r, pred);
}
};
constexpr i64 inf = 1E18 + 1;
struct Info {
i64 sum = 0;
int sumAnd = ~0;
i64 maxSub = -inf;
i64 pre = -inf;
i64 suf = -inf;
};
Info operator+ (const Info &a, const Info &b) {
Info c;
c.sum = a.sum + b.sum;
c.sumAnd = a.sumAnd & b.sumAnd;
c.maxSub = std::max({a.suf + b.pre, a.maxSub, b.maxSub});
c.pre = std::max(a.pre, a.sum + b.pre);
c.suf = std::max(b.suf, a.suf + b.sum);
return c;
}
LazySegmentTree：
template<class Info, class Tag>
struct LazySegmentTree {
int n;
std::vector<Info> info;
std::vector<Tag> tag;
LazySegmentTree() : n(0) {}
LazySegmentTree(int n_, Info v_ = Info()) {
init(n_, v_);
}
template<class T>
LazySegmentTree(std::vector<T> init_) {
init(init_);
}
void init(int n_, Info v_ = Info()) {
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {
n = init_.size();
info.assign(4 << std::__lg(n), Info());
tag.assign(4 << std::__lg(n), Tag());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {
info[p] = info[2 * p] + info[2 * p + 1];
}
void apply(int p, const Tag &v) {
info[p].apply(v);
tag[p].apply(v);
}
void push(int p) {
apply(2 * p, tag[p]);
apply(2 * p + 1, tag[p]);
tag[p] = Tag();
}
void modify(int p, int l, int r, int x, const Info &v) {
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
push(p);
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {
modify(1, 0, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
push(p);
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
}
Info rangeQuery(int l, int r) {
return rangeQuery(1, 0, n, l, r);
}
void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
if (l >= y || r <= x) {
return;
}
if (l >= x && r <= y) {
apply(p, v);
return;
}
int m = (l + r) / 2;
push(p);
rangeApply(2 * p, l, m, x, y, v);
rangeApply(2 * p + 1, m, r, x, y, v);
pull(p);
}
void rangeApply(int l, int r, const Tag &v) {
return rangeApply(1, 0, n, l, r, v);
}
template<class F>
int findFirst(int p, int l, int r, int x, int y, F &&pred) {
if (l >= y || r <= x) {
return -1;
}
if (l >= x && r <= y && !pred(info[p])) {
return -1;
}
if (r - l == 1) {
return l;
}
int m = (l + r) / 2;
push(p);
int res = findFirst(2 * p, l, m, x, y, pred);
if (res == -1) {
res = findFirst(2 * p + 1, m, r, x, y, pred);
}
return res;
}
template<class F>
int findFirst(int l, int r, F &&pred) {
return findFirst(1, 0, n, l, r, pred);
}
template<class F>
int findLast(int p, int l, int r, int x, int y, F &&pred) {
if (l >= y || r <= x) {
return -1;
}
if (l >= x && r <= y && !pred(info[p])) {
return -1;
}
if (r - l == 1) {
return l;
}
int m = (l + r) / 2;
push(p);
int res = findLast(2 * p + 1, m, r, x, y, pred);
if (res == -1) {
res = findLast(2 * p, l, m, x, y, pred);
}
return res;
}
template<class F>
int findLast(int l, int r, F &&pred) {
return findLast(1, 0, n, l, r, pred);
}
};
struct Tag {
int x = 0;
void apply(const Tag &t) & {
x = std::max(x, t.x);
}
};
struct Info {
int x = 0;
void apply(const Tag &t) & {
x = std::max(x, t.x);
}
};
Info operator+(const Info &a, const Info &b) {
return {std::max(a.x, b.x)};
}
欧拉筛：
std::vector<int> minp, primes;
void sieve(int n) {
minp.assign(n + 1, 0);
primes.clear();
for (int i = 2; i <= n; i++) {
if (minp[i] == 0) {
minp[i] = i;
primes.push_back(i);
}
for (auto p : primes) {
if (i * p > n) {
break;
}
minp[i * p] = p;
if (p == minp[i]) {
break;
}
}
}
}
bool isprime(int n) {
return minp[n] == n;
}
离散化：
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());
for (int i = 0; i < n; i++) {
a[i] = std::lower_bound(v.begin(), v.end(), a[i]) - v.begin();
}
双指针
for (int x = 0, y = -1; x <= n; x++) {
if (x < n && s[x] == 'A') {
ans++;
} else {
min = std::min(min, x - y - 1);
y = x;
}
}
单调栈
std::vector<int> stk;
for (int i = 0; i < N; i++) {
while (!stk.empty() && A[i] > A[stk.back()]) {
stk.pop_back();
}
if (!stk.empty()) {
ans[i] = -1;
} else {
ans[i] = stk.back();
}
stk.push_back(i);
}
单调队列
std::deque<int> q;
for (int i = 0; i < n; i++) {
while (!q.empty() && a[i] >= a[q.back()]) {
q.pop_back();
}
q.push_back(i);
if (i - q.front() > k - 1) {
q.pop_front();
}
if (i >= k - 1) {
max[i] = a[q.front()];
}
}
二维单调队列
std::vector<std::vector<int>> rowMin(a, std::vector<int>(b - n + 1)), rowMax(a, std::vector<int>(b - n + 1));
for (int x = 0; x < a; x++) {
std::deque<int> qMin, qMax;
for (int y = 0; y < b; y++) {
while (!qMin.empty() && g[x][y] <= g[x][qMin.back()]) {
qMin.pop_back();
}
qMin.push_back(y);
if (y - qMin.front() > n - 1) {
qMin.pop_front();
}
if (y >= n - 1) {
rowMin[x][y - n + 1] = g[x][qMin.front()];
}
}
for (int y = 0; y < b; y++) {
while (!qMax.empty() && g[x][y] >= g[x][qMax.back()]) {
qMax.pop_back();
}
qMax.push_back(y);
if (y - qMax.front() > n - 1) {
qMax.pop_front();
}
if (y >= n - 1) {
rowMax[x][y - n + 1] = g[x][qMax.front()];
}
}
}
std::vector<std::vector<int>> min(a - n + 1, std::vector<int>(b - n + 1)), max(a - n + 1, std::vector<int>(b - n + 1));
for (int y = 0; y < b - n + 1; y++) {
std::deque<int> qMin, qMax;
for (int x = 0; x < a; x++) {
while (!qMin.empty() && rowMin[x][y] <= rowMin[qMin.back()][y]) {
qMin.pop_back();
}
qMin.push_back(x);
if (x - qMin.front() > n - 1) {
qMin.pop_front();
}
if (x >= n - 1) {
min[x - n + 1][y] = rowMin[qMin.front()][y];
}
}
for (int x = 0; x < a; x++) {
while (!qMax.empty() && rowMax[x][y] >= rowMax[qMax.back()][y]) {
qMax.pop_back();
}
qMax.push_back(x);
if (x - qMax.front() > n - 1) {
qMax.pop_front();
}
if (x >= n - 1) {
max[x - n + 1][y] = rowMax[qMax.front()][y];
}
}
}
dijkstra
std::vector<std::vector<std::pair<int, i64>>> g(n);
for (int i = 0; i < m; i++) {
int u, v;
i64 w;
std::cin >> u >> v >> w;
u--;
v--;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
std::vector<i64> dis(n, INF);
std::priority_queue<std::pair<i64,int>, std::vector<std::pair<i64,int>>, std::greater<std::pair<i64,int>>> pq;
pq.emplace(0, T);
dis[T] = 0;
while (!pq.empty()) {
i64 d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d != dis[u]) {
continue;
}
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i].first;
i64 w = g[u][i].second;
if (dis[v] > d + w) {
dis[v] = d + w;
pq.emplace(dis[v], v);
}
}
}
dijkstra:
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, t;
std::cin >> n >> t;
std::vector<std::vector<std::pair<int, int>>> adj(n);
for (int i = 0; i < t; i++) {
int m;
std::cin >> m;
for (int j = 0; j < m; j++) {
int u, v;
std::cin >> u >> v;
u--;
v--;
adj[u].emplace_back(v, i);
adj[v].emplace_back(u, i);
}
}
int k;
std::cin >> k;
std::vector<std::vector<int>> pos(t);
for (int i = 0; i < k; i++) {
int a;
std::cin >> a;
a--;
pos[a].push_back(i);
}
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> q;
q.emplace(0, 0);
std::vector<int> dis(n, -1);
while (!q.empty()) {
auto [d, x] = q.top();
q.pop();
if (dis[x] != -1) {
continue;
}
dis[x] = d;
for (auto [y, i] : adj[x]) {
auto it = std::lower_bound(pos[i].begin(), pos[i].end(), d);
if (it != pos[i].end()) {
q.emplace(*it + 1, y);
}
}
}
std::cout << dis[n - 1] << "\n";
return 0;
}
trie 树
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 1E6 + 10;
int tot = 1;
int trie[N][26];
int cnt[N];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<std::string> s(n);
i64 ans = 0;
for (int i = 0; i < n; i++) {
std::cin >> s[i];
ans += s[i].size();
int p = 1;
for (auto c : s[i]) {
int &q = trie[p][c - 'a'];
if (!q) {
q = ++tot;
}
p = q;
cnt[p] += 1;
}
}
ans *= 2 * n;
for (int i = 0; i < n; i++) {
std::reverse(s[i].begin(), s[i].end());
int p = 1;
for (auto c : s[i]) {
int &q = trie[p][c - 'a'];
if (!q) {
break;
}
p = q;
ans -= 2 * cnt[p];
}
}
std::cout << ans << "\n";
return 0;
}
公式
平方和：
$$
1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{n(n + 1)(2n + 1)}{6}
$$
__builtin_popcount(x): x 二进制下，$1$ 的个数。
组合数：
/** 组合数（小范围预处理，逆元+杨辉三角）
* 2024-03-14: https://qoj.ac/submission/353877
* 2023-10-06: https://qoj.ac/submission/203196
**/
constexpr int P = 1000000007;
constexpr int L = 10000;
int fac[L + 1], invfac[L + 1];
int sumbinom[L + 1][7];
int binom(int n, int m) {
if (n < m || m < 0) {
return 0;
}
return 1LL * fac[n] * invfac[m] % P * invfac[n - m] % P;
}
int power(int a, int b) {
int res = 1;
for (; b; b /= 2, a = 1LL * a * a % P) {
if (b % 2) {
res = 1LL * res * a % P;
}
}
return res;
}
int main() {
fac[0] = 1;
for (int i = 1; i <= L; i++) {
fac[i] = 1LL * fac[i - 1] * i % P;
}
invfac[L] = power(fac[L], P - 2);
for (int i = L; i; i--) {
invfac[i - 1] = 1LL * invfac[i] * i % P;
}
sumbinom[0][0] = 1;
for (int i = 1; i <= L; i++) {
for (int j = 0; j < 7; j++) {
sumbinom[i][j] = (sumbinom[i - 1][j] + sumbinom[i - 1][(j + 6) % 7]) % P;
}
}
}