---
title: Template (C++)
tags: Programming Contest
---
# Graph
## Dijkstra
```cpp
template <typename T> struct Dijkstra {
vector<T> dis;
vector<int> par;
Dijkstra(int n, T inf) {
dis = vector<T>(n, inf);
par = vector<int>(n, -1);
}
void run(const vector<vector<pair<int, T>>> &adj,
const vector<int> &sources) {
using Item = pair<T, int>;
priority_queue<Item, vector<Item>, greater<Item>> que;
for (auto u : sources) {
dis[u] = 0;
par[u] = u;
que.push({dis[u], u});
}
while (!que.empty()) {
auto [d, u] = que.top();
que.pop();
if (d > dis[u]) {
continue;
}
for (auto [v, w] : adj[u]) {
auto new_d = dis[u] + w;
if (new_d < dis[v]) {
dis[v] = new_d;
par[v] = u;
que.push({dis[v], v});
}
}
}
}
};
```
https://cses.fi/problemset/result/6059594/
## SegTree
```cpp
#include <algorithm>
#include <iostream>
#include <vector>
#include <functional>
using namespace std;
template <typename S, typename F> struct LazySegTree {
// lazy[u] != default_lazy <-> data[lch] and data[rch] are not up-to-date,
// but data[u] is. lazy[u] == default_lazy <-> data[u], data[lch], data[rch]
// are up-to-date.
int NN;
vector<S> data;
vector<F> lazy;
virtual S default_data() = 0;
virtual F default_lazy() = 0;
virtual S op(S a, S b) = 0;
virtual S apply_lazy(F lazy, S val, int u, int l, int r) = 0;
virtual F merge_lazy(F parent, F child) = 0;
LazySegTree() = default;
// Calling virtual functions in constructor is not allowed.
// Therefore, we use this function instead.
void build_from_vector(const vector<S> &A) {
this->NN = 1;
while (this->NN < int(A.size())) {
this->NN <<= 1;
}
this->data = vector<S>(2 * this->NN, this->default_data());
this->lazy = vector<F>(2 * this->NN, this->default_lazy());
for (int i = 0; i < int(A.size()); i++) {
this->data[this->NN - 1 + i] = A[i];
}
for (int u = this->NN - 2; u >= 0; u--) {
this->data[u] =
this->op(this->data[u * 2 + 1], this->data[u * 2 + 2]);
}
}
// Apply lazy[u] to lch and rch, so data[lch] and data[rch] are updated.
// Merge lazy[u] into lazy[lch] and lazy[rch]
void push(int u, int l, int r) {
if (lazy[u] == this->default_lazy())
return;
int m = (l + r) / 2;
int lch = u * 2 + 1;
int rch = u * 2 + 2;
this->data[lch] =
this->apply_lazy(this->lazy[u], this->data[lch], lch, l, m);
this->data[rch] =
this->apply_lazy(this->lazy[u], this->data[rch], rch, m, r);
this->lazy[lch] = this->merge_lazy(this->lazy[u], this->lazy[lch]);
this->lazy[rch] = this->merge_lazy(this->lazy[u], this->lazy[rch]);
this->lazy[u] = this->default_lazy();
}
S prod(int a, int b, int u = -1, int l = -1, int r = -1) {
if (u == -1)
u = 0, l = 0, r = this->NN;
if (l >= b || r <= a)
return this->default_data();
if (l >= a && r <= b)
return this->data[u];
int m = (l + r) / 2;
this->push(u, l, r);
S res1 = this->prod(a, b, u * 2 + 1, l, m);
S res2 = this->prod(a, b, u * 2 + 2, m, r);
return this->op(res1, res2);
}
void apply(int a, int b, F x, int u = -1, int l = -1, int r = -1) {
if (u == -1)
u = 0, l = 0, r = this->NN;
if (l >= b || r <= a)
return;
if (l >= a && r <= b) {
this->data[u] = this->apply_lazy(x, this->data[u], u, l, r);
this->lazy[u] = this->merge_lazy(x, this->lazy[u]);
return;
}
int m = (l + r) / 2;
this->push(u, l, r);
this->apply(a, b, x, u * 2 + 1, l, m);
this->apply(a, b, x, u * 2 + 2, m, r);
this->data[u] = this->op(this->data[u * 2 + 1], this->data[u * 2 + 2]);
}
int find_first_of(const function<bool(S, int, int, int)> &f, int u = -1,
int l = -1, int r = -1) {
if (u == -1)
u = 0, l = 0, r = this->NN;
if (!f(this->data[u], u, l, r))
return -1;
if (r - l == 1)
return u - (this->NN - 1);
int m = (l + r) / 2;
int idx1 = this->find_first_of(f, u * 2 + 1, l, m);
if (idx1 != -1)
return idx1;
int idx2 = this->find_first_of(f, u * 2 + 2, m, r);
if (idx2 != -1)
return idx2;
return -1;
}
};
using S = int;
using F = int;
struct SegTree : LazySegTree<S, F> {
S default_data() { return 0x3f3f3f3f; }
F default_lazy() { return 0; }
S op(S lch, S rch) { return min(lch, rch); }
S apply_lazy(F lazy, S val, int u, int l, int r) {
return lazy + val;
}
F merge_lazy(F parent, F child) { return parent + child; }
};
```
驗題：
* https://atcoder.jp/contests/abc223/submissions/33287093
* https://judge.yosupo.jp/submission/104918
## Tree Diamter
https://hackmd.io/9KrxOEwRRA6LYrfn1NA9pQ?view#Tree-Diameter
```cpp
tuple<vector<int>, vector<int>, vector<int>> bfs(const vector<vector<int>> &G,
int root, int parent) {
int N = G.size();
auto vis = vector<int>();
auto par = vector(N, -1);
auto dep = vector(N, -1);
auto que = queue<tuple<int, int>>();
par[root] = parent;
dep[root] = 0;
que.push({root, parent});
while (que.size() > 0) {
auto [u, p] = que.front();
que.pop();
vis.push_back(u);
for (auto v : G[u]) {
if (v != p) {
par[v] = u;
dep[v] = dep[u] + 1;
que.push({v, u});
}
}
}
return {vis, par, dep};
}
int main() {
auto [vis, par, dep] = bfs(G, 0, -1);
int s = vis.back();
auto [s_vis, s_par, s_dep] = bfs(G, s, -1);
int t = s_vis.back();
return 0;
}
```
## Prefix
```cpp
template <typename T> struct Prefix2D {
vector<vector<T>> pref;
Prefix2D() = default;
Prefix2D(const vector<vector<T>> &A) {
int N = A.size();
int M = A[0].size();
pref = vector(N, vector<T>(M, 0));
pref[0][0] = A[0][0];
for (int r = 1; r < N; r++) {
pref[r][0] = pref[r - 1][0] + A[r][0];
}
for (int c = 1; c < M; c++) {
pref[0][c] = pref[0][c - 1] + A[0][c];
}
for (int r = 1; r < N; r++) {
for (int c = 1; c < M; c++) {
pref[r][c] = pref[r][c - 1] + pref[r - 1][c] -
pref[r - 1][c - 1] + A[r][c];
}
}
}
// [r1, r2] x [c1, c2]
T query(int r1, int r2, int c1, int c2) {
T ans = pref[r2][c2];
if (r1 >= 1)
ans -= pref[r1 - 1][c2];
if (c1 >= 1)
ans -= pref[r2][c1 - 1];
if (r1 >= 1 && c1 >= 1)
ans += pref[r1 - 1][c1 - 1];
return ans;
}
};
```
## BIT
```cpp
template <typename T> struct BIT {
vector<T> data;
BIT(int n) { data = vector<T>(n, 0); }
void add(int idx, T val) {
for (int i = idx + 1; i <= data.size() - 1; i += (i & (-i))) {
data[i] = data[i] + val;
}
}
T prefix(int idx) {
T res = 0;
for (int i = idx + 1; i > 0; i -= (i & -i)) {
res = res + data[i];
}
return res;
}
T sum(int l, int r) { // l..r
T val = prefix(r - 1);
if (l != 0) {
val -= prefix(l - 1);
}
return val;
}
};
```
https://atcoder.jp/contests/abc294/submissions/39908415
## Utility
### Argsort
```cpp
template <typename T> vector<int> argsort(const vector<T> &v) {
vector<pair<T, int>> data;
for (int i = 0; i < int(v.size()); i++) {
data.push_back({v[i], i});
}
sort(data.begin(), data.end());
vector<int> indices;
for (auto &&[_, i] : data) {
indices.push_back(i);
}
return indices;
}
```
### Print Vector
```cpp
template <typename T>
string join(const vector<T> &arr, const string &seperator = " ") {
ostringstream oss;
for (size_t i = 0; i < arr.size(); i++) {
if (i != 0) {
oss << seperator;
}
oss << arr[i];
}
return oss.str();
}
```
### Print Map
```cpp
template <typename K, typename V>
ostream &operator<<(ostream &out, const map<K, V>& m) {
out << "{ ";
for (auto &[k, v] : m) {
out << k << ": " << v << ", ";
}
out << "}";
return out;
}
```
### Print Tuple
```cpp
template <typename TupType, size_t... I>
ostream &tuple_print(ostream &out, const TupType &_tup, index_sequence<I...>) {
out << "(";
(..., (out << (I == 0 ? "" : ", ") << get<I>(_tup)));
out << ")";
return out;
}
template <typename... T> ostream &operator<<(ostream &out, const tuple<T...> &t) {
return tuple_print(out, t, make_index_sequence<sizeof...(T)>());
}
```
### Print Pair
```cpp
template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2>& p) {
out << "( " << p.first << ", " << p.second << " )";
return out;
}
```
## Numbers
### Euclidean Division
```cpp
pair<ll, ll> euclid_div(ll a, ll b) {
ll q = a / b;
ll r = a % b;
if (r < 0) {
r += b;
q -= 1;
}
return {q, r};
}
```
### GCD
```cpp
ll gcd(ll a, ll b) {
// gcd(x, 0) = x
// gcd(a, b) = gcd(b, r)
while (b != 0) {
ll r = a % b;
a = b;
b = r;
}
return a;
}
```
### ExtGCD
```cpp
tuple<ll, ll, ll> extgcd(ll a, ll b) {
if (b == 0) {
return {1, 0, a};
} else {
auto [x1, y1, g] = extgcd(b, (a % b + b) % b);
return {y1, x1 - a / b * y1, g};
}
}
```
### Sieve Of Eratosthenes
```cpp
using ll = long long;
using pll = pair<ll, ll>;
struct SieveOfEratosthenes {
vector<bool> is_prime;
vector<ll> primes;
SieveOfEratosthenes(ll V) {
is_prime = vector<bool>(V + 1, true);
primes = vector<ll>();
for (ll i = 2; i <= V; i ++) {
if (is_prime[i]) {
primes.push_back(i);
for (ll j = i * i; j <= V; j += i) {
is_prime[j] = false;
}
}
}
}
vector<pll> factorize(ll x) {
if (x <= 1) {
throw invalid_argument("x shoule be > 1");
}
auto result = vector<pll>();
for (auto p : primes) {
ll exp = 0;
while (x % p == 0) {
exp++;
x = x / p;
}
if (exp > 0) {
result.push_back(pll(p, exp));
}
if (p * p > x) {
break;
}
}
if (x > 1) {
result.push_back(pll(x, 1));
}
return result;
}
};
```
## Combination
```cpp
template <typename T> struct CombTool {
vector<T> fact;
vector<T> finv;
CombTool(int V) {
fact = vector<T>(V, 1);
finv = vector<T>(V, 1);
for (int i = 1; i < V; i++) {
fact[i] = fact[i - 1] * i;
}
finv[V - 1] = fact.back().inv();
for (int i = V - 2; i >= 0; i--) {
finv[i] = finv[i + 1] * (i + 1);
}
}
T comb(int a, int b) { return fact[a] * finv[b] * finv[a - b]; }
T perm(int a, int b) { return fact[a] * finv[a - b]; }
T hcomb(int a, int b) { return comb(a + b - 1, b); }
};
```
## Heavy Light Decomposition
```cpp
struct HLD {
vector<int> size;
vector<int> depth;
vector<int> heavy;
vector<int> parent;
vector<int> top;
vector<int> tour;
vector<int> t_enter;
vector<int> t_leave;
HLD(const vector<vector<int>> &adj, int root) {
int N = adj.size();
const int inf = 0x3f3f3f3f;
// Find size, depth, heavy, parent by DFS
{
size = vector<int>(N, 1);
depth = vector<int>(N, 0);
heavy = vector<int>(N, inf);
parent = vector<int>(N, inf);
auto stack = vector<pair<char, int>>{{'l', root}, {'e', root}};
depth[root] = 0;
parent[root] = root;
while (!stack.empty()) {
auto [cmd, u] = stack.back();
stack.pop_back();
if (cmd == 'l') {
size[u] = 1;
heavy[u] = inf;
for (auto v : adj[u]) {
if (v != parent[u]) {
size[u] += size[v];
if (heavy[u] == inf || size[v] > size[heavy[u]]) {
heavy[u] = v;
}
}
}
} else {
for (auto v : adj[u]) {
if (parent[v] == inf) {
parent[v] = u;
depth[v] = depth[u] + 1;
stack.push_back({'l', v});
stack.push_back({'e', v});
}
}
}
}
}
// Find top, tour, t_enter, t_leave by DFS
{
int time = 0;
top = vector<int>(N, inf);
tour = vector<int>(N, inf);
t_enter = vector<int>(N, inf);
t_leave = vector<int>(N, inf);
auto stack = vector<pair<char, int>>{{'l', root}, {'e', root}};
top[root] = root;
while (!stack.empty()) {
auto [cmd, u] = stack.back();
stack.pop_back();
if (cmd == 'l') {
t_leave[u] = time;
} else {
t_enter[u] = time;
tour[time] = u;
time++;
for (auto v : adj[u]) {
if (v != parent[u]) {
// heavy edge / light edge
top[v] = ((v == heavy[u]) ? top[u] : v);
stack.push_back({'l', v});
stack.push_back({'e', v});
}
}
}
}
}
}
int lca(int u, int v) {
while (top[u] != top[v]) {
if (depth[top[u]] > depth[top[v]]) {
u = parent[top[u]];
} else {
v = parent[top[v]];
}
}
return ((depth[u] < depth[v]) ? u : v);
}
};
```
https://atcoder.jp/contests/abc294/submissions/39908415
## Z algorithm
https://cp-algorithms.com/string/z-function.html
```cpp
vector<int> zfunc(const string& S) {
int N = S.length();
vector<int> z(N, 0);
int l = 0, r = 0;
for (int i = 1; i < N; i++) {
if (i <= r) {
z[i] = min(r - i, z[i - l]);
}
while (i + z[i] < N && S[i + z[i]] == S[z[i]]) {
z[i]++;
}
if (i + z[i] - 1 >= r) {
l = i;
r = i + z[i] - 1;
}
}
return z;
}
```
## Rolling Hash
https://cp-algorithms.com/string/string-hashing.html
```cpp
#include <cassert>
using ll = long long;
ll powmod(ll a, ll b, ll m) {
ll base = a;
ll res = 1;
while (b) {
if (b & 1) {
res = res * base % m;
}
base = base * base % m;
b >>= 1;
}
return res;
}
struct PolyHash {
ll mod;
ll base;
vector<ll> powr;
vector<ll> pinv;
// N is max length; mod should be prime
PolyHash(int N, ll base = 31, ll mod = 1e9 + 7) {
this->base = base;
this->mod = mod;
powr = vector<ll>(N, 1);
pinv = vector<ll>(N, 1);
for (int i = 1; i < N; i++) {
powr[i] = powr[i - 1] * base % mod;
}
pinv[N - 1] = powmod(powr[N - 1], mod - 2, mod);
for (int i = N - 2; i >= 0; i--) {
pinv[i] = pinv[i + 1] * base % mod;
}
}
vector<ll> transform(const vector<int> &v) {
for (auto && x : v) {
assert (x != 0);
}
vector<ll> h(v.size());
h[0] = v[0] % mod;
for (size_t i = 1; i < v.size(); i++) {
h[i] = (h[i - 1] + v[i] * powr[i] % mod) % mod;
}
return h;
}
ll substr(const vector<ll> &h, int l, int r) { // [l, r)
if (l == 0) {
return h[r - 1];
} else {
return ((h[r - 1] - h[l - 1] + mod) % mod) * pinv[l] % mod;
}
}
};
vector<int> string2vector(const string &s) {
vector<int> v(s.length());
for (size_t i = 0; i < s.length(); i++) {
if (s[i] >= 'a' && s[i] <= 'z') {
v[i] = s[i] - 'a' + 1;
} else {
v[i] = s[i] - 'A' + 1;
}
}
return v;
}
```
Sign in with Wallet
Connect another wallet