library

Bukayo Haka

Contents
1 template 2

2 Math 2
2.1 Combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 GCD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.3 Number theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.4 Mobius function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.5 phi function of n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.6 phi function from 1 to n . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.7 prime factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.8 prime check . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.9 Xor basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.10 Matrix exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.11 FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.12 NTT + generator + CRT . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 Data structures 6
3.1 Sparse table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 Fenwick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.3 Sqrt decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.4 MO’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.5 Binary Trie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.6 String Trie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.7 DSU with rollbacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.8 Lichao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.9 Lichao with rollbacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.10 Segment tree (point update, range query) . . . . . . . . . . . . . . . . . . 10
3.11 Segment tree (lazy propagation) . . . . . . . . . . . . . . . . . . . . . . . 10

4 Graphs and trees 11

4.1 Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2 Euler tour + DSU on trees . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.3 LCA and Binary lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

5 String algorithms 12
5.1 KMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.2 Manacher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.3 String hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.4 Z-algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1
 §1 template friend ostream& operator<<(ostream &os, mint a) {return os << a.v;}
};
#include <bits/stdc++.h> const int N = 2e5 + 5;
using namespace std; mint fact[N], inv[N];
#define ll long long mint binpow(mint a, int b) {
#define endl '\n' mint ans = 1;
void SOLVE(){} while (b) {
Bukayo Haka —

signed main(){ if (b & 1) ans *= a; a *= a; b >>= 1;

ios_base::sync_with_stdio(false); [Link](nullptr); [Link](nullptr); }
//freopen("[Link]", "r", stdin); return ans;
//freopen("[Link]", "w", stdout); }
int o_o = 1; cin >> o_o; mint choose(ll n, ll k){
while(o_o--) SOLVE(); if (k < 0 || n < k || n < 0) return 0;
return 0; return fact[n] * inv[n - k] * inv[k];
} }
mint stars_and_bars(ll n, ll k){ return choose(n + k - 1, n);}
void init(){
fact[1] = fact[0] = (mint) 1;
for(ll i = 2; i < N; i++) fact[i] = fact[i - 1] * i;
§2 Math inv[N - 1] = mint(1) / fact[N - 1];
for(int i = N - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1);
}
§2.1 Combinatorics

2
const int MOD = 998244353;
struct mint { §2.2 GCD
int v;
mint(long long x) { if (x >= MOD) x %= MOD; v = x;} ll gcd(ll a, ll b, ll& x, ll& y) {
mint() {v = 0;} if (b == 0) {
mint& operator+=(mint b) { x = 1; y = 0;
if ((v += b.v) >= MOD) v -= MOD; return a;
return *this; }
} ll x1, y1;
mint& operator-=(mint b) { ll G = gcd(b, a % b, x1, y1);
if ((v -= b.v) < 0) v += MOD; x = y1; y = x1 - y1 * (a / b);
return *this; return G;
} }
mint& operator*=(mint b) {
v = 1ll * v * b.v % MOD;
return *this;
}
mint& operator/=(mint b) { §2.3 Number theory
v = 1ll * v * binpow(b, MOD - 2).v % MOD;
return *this; const int N = 2e5 + 5;
} int lp[N];
friend mint operator+(mint a, mint b) {return a += b;} vector<int> primes;
friend mint operator-(mint a, mint b) {return a -= b;} void init(){
friend mint operator*(mint a, mint b) {return a *= b;} lp[1] = 1;
friend mint operator/(mint a, mint b) {return a /= b;} for (ll i = 2; i < N; i++) if (lp[i] == 0){
library

friend istream& operator>>(istream &is, mint &a) {return is >> a.v;} lp[i] = i;
 primes.push_back(i); return result;
for (ll j = i * i; j < N; j += i) if (lp[j] == 0){ }
lp[j] = i;
}
}
} §2.6 phi function from 1 to n
vector<int> getdiv(int n){
vector<int> div;
Bukayo Haka —

for (int i = 1; i <= n / i; i++)if (n % i == 0){ void phi_1_to_n(int n) {

div.push_back(i); vector<int> phi(n + 1);
if (i * i != n) div.push_back(n / i); for (int i = 0; i <= n; i++) phi[i] = i;
} for (int i = 2; i <= n; i++) {
return div; if (phi[i] == i) {
} for (int j = i; j <= n; j += i)
phi[j] -= phi[j] / i;
}
}
}
§2.4 Mobius function
int vis[N], p[N], ptot, mob[N];
void build() { §2.7 prime factorization
mob[1] = 1;
for (int i = 2; i < N; i++) { vector<ll> prime_factorization(ll n) {
if (!vis[i]) vector<ll> factorization;

3
p[++ptot] = i, mob[i] = -1; for (int d : {2, 3, 5}) {
for (int j = 1; j <= ptot && i * p[j] < N; j++) { while (n % d == 0) {
mob[i * p[j]] = -mob[i]; factorization.push_back(d);
vis[i * p[j]] = 1; n /= d;
if (i % p[j] == 0) { }
mob[i * p[j]] = 0; }
break; static array<int, 8> increments = {4, 2, 4, 2, 4, 6, 2, 6};
} int i = 0;
} for (ll d = 7; d * d <= n; d += increments[i++]) {
} while (n % d == 0) {
} factorization.push_back(d);
n /= d;
}
if (i == 8) i = 0;
§2.5 phi function of n }
if (n > 1) factorization.push_back(n);
return factorization;
int phi(int n) { }
int result = n;
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) {
while (n % i == 0) n /= i;
result -= result / i; §2.8 prime check
}
} bool isPrime(int n) {
library

if (n > 1) result -= result / n; if (n <= 1 || n % 2 == 0 || n % 3 == 0) return false;

 if (n == 2 || n == 3) return true; §2.10 Matrix exponentiation
for (int i = 5; i <= n / i; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0) return false;
return true; const int N = 2;
} using T = array<array<ll, N>, N>;
using S = array<array<ll, N>, 1>;
const ll MOD = 998244353;
ll mult(ll a, ll b) { return (a % MOD * b % MOD) % MOD; }
Bukayo Haka —

§2.9 Xor basis ll add(ll a, ll b) { return (a % MOD + b % MOD) % MOD; }

ll sub(ll a, ll b) { return (a % MOD - b % MOD + MOD) % MOD; }
template<class X>
const int LOG = 30; X matrix_mult(const X &a, const T &b){
struct xor_basis{ X res = {0};
vector<int> basis; for (int i = 0; i < (int) res[0].size(); i++)
int sz; for (int j = 0; j < N; j++)
xor_basis(){ for (int k = 0; k < N; k++)
sz = 0; res[i][j] = add(res[i][j], mult(a[i][k], b[k][j]));
basis = vector<int>(LOG); return res;
} }
void insert(int mask){ T matrix_expo(const T &a, ll p){
for(int i = LOG - 1; i >= 0; i--){ T iden = {0};
if((mask & (1 << i)) == 0) continue; for (int i = 0; i < N; i++) iden[i][i] = 1;
if(!basis[i]){ T res = a;
sz++; basis[i] = mask; while (p){
return; if (p & 1) iden = matrix_mult(iden, res);

4
} res = matrix_mult(res, res);
mask ^= basis[i]; p >>= 1;
} }
} return iden;
void anding(int val){ }
vector<int> a;
for(int i = 0; i < LOG; i++){
basis[i] &= val;
if(basis[i]) a.push_back(basis[i]);
basis[i] = 0;
}
for(auto v : a) insert(v); §2.11 FFT
}
bool can_represent(int x) {
for (auto y: basis) x = min(x, x ^ y); using cd = complex<double>;
return x == 0; const double PI = acos(-1);
} void fft(vector<cd> & a, bool invert){
int get_mx(){ int n = [Link]();
int answer = 0; if(n == 1) return;
for(int i = LOG - 1; i >= 0; i--){ vector<cd> even (n / 2), odd(n / 2);
if(answer & (1 << i)) continue; for(int i = 0; i < n / 2; i++){
if(basis[i]) answer ^= basis[i]; even[i] = a[2 * i];
} odd[i] = a[2 * i + 1];
return answer; }
} fft(even, invert); fft(odd, invert);
}; double ang = 2 * PI / n * (invert ? -1 : 1);
library

cd w(1), wn(cos(ang), sin(ang));

 for(int i = 0; i < n / 2; i++){ }
a[i] = even[i] + w * odd[i]; if (n > 1)
a[i + n / 2] = even[i] - w * odd[i]; fact.push_back (n);
if(invert){
a[i] /= 2; for (int res=2; res<=mod; ++res) {
a[i + n / 2] /= 2; bool ok = true;
} for (size_t i=0; i<[Link]() && ok; ++i)
w *= wn; ok &= modpow (res, phi / fact[i]) != 1;
Bukayo Haka —

} if (ok) return res;

} }
vector<int> multiply(vector<int>& a, vector<int>& b){ return -1;
int n = 1; }
while(n < ([Link]() + [Link]())) n *= 2; int modpow(int b, int e, int m) {
vector<cd> ffta(n), fftb(n); int ans = 1;
for(int i = 0; i < [Link](); i++) ffta[i] = a[i]; for (; e; b = (ll)b * b % m, e /= 2)
for(int i = 0; i < [Link](); i++) fftb[i] = b[i]; if (e & 1) ans = (ll)ans * b % m;
fft(ffta, 0); return ans;
fft(fftb, 0); }
for(int i = 0; i < n; i++) ffta[i] *= fftb[i];
fft(ffta, 1); void ntt(vector<int> &a) {
vector<int> answer(n); int n = (int)[Link](), L = 31 - __builtin_clz(n);
for(int i = 0; i < n; i++) answer[i] = round(ffta[i].real()); vector<int> rt(2, 1);
return answer; for (int k = 2, s = 2; k < n; k *= 2, s++) {
} [Link](n);
int z[] = {1, modpow(root, mod >> s, mod)};

5
for (int i = k; i < 2*k; ++i) rt[i] = (ll)rt[i / 2] * z[i & 1] % mod;
}
vector<int> rev(n);
§2.12 NTT + generator + CRT for (int i = 0; i < n; ++i) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
for (int i = 0; i < n; ++i) if (i < rev[i]) swap(a[i], a[rev[i]]);
const ll mod = (119 << 23) + 1, root = 62; // = 998244353 for (int k = 1; k < n; k *= 2) {
// For p < 2^30 there is also e.g. 5 << 25, 7 << 26, 479 << 21 for (int i = 0; i < n; i += 2 * k) {
// and 483 << 21 (same root). The last two are > 10^9. for (int j = 0; j < k; ++j) {
int z = (ll)rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];
a[i + j + k] = ai - z + (z > ai ? mod : 0);
ll modpow(ll b, ll e) { ai += (ai + z >= mod ? z - mod : z);
ll ans = 1; }
for (; e; b = b * b % mod, e /= 2) }
if (e & 1) ans = ans * b % mod; }
return ans; }
} vector<int> conv(const vector<int> &a, const vector<int> &b) {
if ([Link]() || [Link]()) return {};
// Primitive Root of the mod of form 2^a * b + 1 int s = (int)[Link]() + (int)[Link]() - 1, B = 32 - __builtin_clz(s), n =
,→ 1 << B;
int generator () {
vector<int> fact; int inv = modpow(n, mod - 2, mod);
int phi = mod-1, n = phi; vector<int> L(a), R(b), out(n);
for (int i=2; i*i<=n; ++i) [Link](n), [Link](n);
if (n % i == 0) { ntt(L), ntt(R);
fact.push_back (i); for (int i = 0; i < n; ++i) out[-i & (n - 1)] = (ll)L[i] * R[i] % mod *
,→ inv % mod;
while (n % i == 0)
ntt(out);
library

n /= i;
 return {[Link](), [Link]() + s}; }
} };

ll CRT(ll a, ll m1, ll b, ll m2) {

__int128 m = m1*m2;
ll ans = a*m2%m*modpow(m2, m1-2, m1)%m + m1*b%m*modpow(m1, m2-2, m2)%m; §3.2 Fenwick
return ans % m;
}
Bukayo Haka —

vector<int> poly_pow(vector<int> poly, int p, int limit = 2e6) { template <class T>
vector<int> ans{1}; struct Fenwick{ //1-indexed
while (p) { int n; int LOG;
if(p&1) ans = conv(ans, poly); vector<T> tree;
poly = conv(poly, poly); Fenwick(int _n) : n(_n + 5) { [Link](n); LOG = log2(n) + 1; }
[Link](limit + 1); void add(int i, T val) {
[Link](limit + 1); if (i <= 0) return;
p >>= 1; for (; i <= n; i += (i & -i)) tree[i] += val;
} }
return ans; T query(int i) {
} if(i <= 0) return 0;
T res = 0;
for (; i >= 1; i -= (i & -i)) res += tree[i];
return res;
}
int lower_bound(ll val){
T sum = 0; int pos = 0;

6
§3 Data structures for(int i = LOG; i >= 0; i--){
if(pos + (1 << i) <= n && sum + tree[pos + (1 << i)] < val){
pos += (1 << i); sum += tree[pos];
§3.1 Sparse table }
}
return pos + 1;
struct SparseTable { }
int n; };
vector<ll> arr;
vector<vector<ll>> table;
function<ll(ll, ll)> f;
SparseTable(int n_, vector<ll> &v, function<ll(ll, ll)> func) : n(n_),
,→ arr(v), §3.3 Sqrt decomposition
f(func) {
table = vector<vector<ll>>(n + 2, vector<ll>(log2(n) + 2)); struct Sq_dec{
for (int i = 0; i < n; ++i) int bs;
table[i][0] = arr[i]; vector<ll> a, B;
for (int j = 1; (1 << j) <= n; j++) { Sq_dec(vector<ll> &arr){
for (int i = 0; i + (1 << j) - 1 < n; i++) int n = [Link]();
table[i][j] = f(table[i][j - 1], table[i + (1 << (j - 1))][j - [Link](n, 0);
,→ 1]); a = arr;
} bs = ceil(sqrt([Link]()));
} for (int i = 0; i < [Link](); i++){
ll query(int l, int r) { B[i / bs] += a[i];
if (l > r) swap(l, r); }
int j = log2(r - l + 1); }
library

return f(table[l][j], table[r - (1 << j) + 1][j]); void update(int x, int v){

 B[x / bs] -= a[x]; §3.5 Binary Trie
a[x] = v;
B[x / bs] += a[x]; struct Trie{
} struct Node{
ll query(int r){ Node *child[2];
ll res = 0; int freq;
for (int i = 0; i < r / bs; i++){ Node(){
res += B[i]; child[0] = child[1] = NULL;
Bukayo Haka —

} freq = 0;
for (int i = (r / bs) * bs; i < r; i++){ }
res += a[i]; };
} Node *root;
return res; int bits;
} Trie(int x){
ll query(int l, int r) { return query(r) - query(l - 1); } root = new Node();
}; bits = x;
}
void insert(ll val){
Node *current = root;
for (int i = bits; i >= 0; i--){
bool bit = (val >> i) & 1;
if (current->child[bit] == NULL){
§3.4 MO’s algorithm current->child[bit] = new Node();
}
current = current->child[bit];

7
const int N = 1e5 + 5, sq = 317; current->freq++;
struct query{ }
int l, r, indx; }
bool operator<(query &other){ void del(ll val) {
if (l / sq != other.l / sq) return l / sq < other.l / sq; Node *current = root;
return (l / sq & 1 ? r < other.r : other.r < r); Node *parent = nullptr;
} int lst = -1;
}; for (int i = bits; i >= 0; i--) {
void MO(){ bool bit = (val >> i) & 1;
int q; if (!current->child[bit]) return;
vector<query> qu(q); parent = current;
sort([Link](), [Link]()); lst = bit;
vector<int> answer(q); current = current->child[bit];
int l = 0, r = -1; current->freq--;
int counter = 0; if (current->freq == 0) {
auto add = [&](int indx) {}; if (parent) {
auto del = [&](int indx) {}; delete parent->child[lst];
for (auto &[l_, r_, indx] : qu){ parent->child[lst] = nullptr;
while (l > l_) add(--l); }
while (r < r_) add(++r); return;
while (l < l_) del(l++); }
while (r > r_) del(r--); }
answer[indx] = counter; }
} ll query(ll val, ll k){ // num ^ val < k
} Node *current = root;
library

ll answer = 0;
 for (ll i = bits; i >= 0; i--){ §3.6 String Trie
if (current == NULL) break;
int b1 = (val >> i) & 1; struct Trie{
int b2 = (k >> i) & 1; struct Node{
if (b2){ Node *ch[26];
if (current->child[b1]) int prefix;
answer += current->child[b1]->freq; int end;
current = current->child[b1 ^ 1]; Node(){
Bukayo Haka —

}else{ prefix = end = 0;

current = current->child[b1]; memset(ch, 0, sizeof(ch));
} }
} };
return answer; Node *root = new Node();
} void insert(string s){
ll mxXor(ll val){ Node *current = root;
Node *current = root; for (char c : s){
ll ret = 0; int idx = c - 'a';
for (ll i = bits; i >= 0; i--){ if (current->ch[idx] == 0)
bool bit = (val >> i) & 1; current->ch[idx] = new Node();
if (current->child[bit ^ 1]){ current = current->ch[idx];
current = current->child[bit ^ 1]; current->prefix++;
ret |= (1 << i); }
} current->end++;
else{ }
current = current->child[bit]; int count(string s){

8
} Node *current = root;
} for (char c : s){
return ret; int idx = c - 'a';
} if (current->ch[idx] == 0)
ll mnXor(ll val){ return 0;
Node *current = root; current = current->ch[idx];
ll ret = 0; }
for (ll i = bits; i >= 0; i--){ return current->end;
int bit = (val >> i) & 1; }
if (current->child[bit]){ };
current = current->child[bit];
}else{
current = current->child[bit ^ 1];
ret |= (1LL << i);
} §3.7 DSU with rollbacks
}
return ret; struct DSU{
} int n;
}; vector<int> parent, size;
vector<pair<int &, int>> history;
int components;
DSU(int n){
parent = size = vector<int>(n + 1);
components = n;
for (int i = 1; i <= n; i++){
library

parent[i] = i;
 size[i] = 1; else if(left != m) add_line(p, 2 * node + 1, l, mid);
} else add_line(p, 2 * node + 2, mid, r);
} }
int find(int v){ ll get(ll x, int node = 0, int l = -N, int r = N + 1){
return parent[v] = (parent[v] == v ? v : find(parent[v])); int mid = (l + r) >> 1;
} if(r - l == 1) return eval(line[node], x);
void union_sets(int a, int b){ else if(x < mid) return min(eval(line[node], x), get(x, 2 * node + 1,
a = find(a); ,→ l, mid));
Bukayo Haka —

b = find(b); else return min(eval(line[node], x), get(x, 2 * node + 2, mid, r));

if (a != b){ }
if (size[a] < size[b]) swap(a, b); };
history.push_back({size[a], size[a]});
history.push_back({parent[b], parent[b]});
parent[b] = a;
size[a] += size[b];
components--; §3.9 Lichao with rollbacks
}
} using point = pair<ll, ll>;
void rollback(int until) { ll eval(point p, ll x){ // p dot (x, 1);
while ([Link]() > until) { return [Link] * x + [Link];
[Link]().first = [Link]().second; }
history.pop_back(); const int N = 1e6 + 5;
} int timer = 0;
} struct lichao{
}; int n;

9
vector<point> line;
stack<tuple<int, point, int>> history;
lichao(){
n = 1;
§3.8 Lichao while(n < N) n *= 2;
line = vector<point>(n << 3);
using point = pair<ll, ll>; }
ll eval(point p, ll x){ // p dot (x, 1); void add_line(point p, int node = 0, int l = -N, int r = N + 1){
return [Link] * x + [Link]; int mid = (l + r) >> 1;
} bool left = eval(p, l) < eval(line[node], l);
const int N = 1e6 + 5; bool m = eval(p, mid) < eval(line[node], mid);
int timer = 0; if(m){
struct lichao{ [Link]({node, line[node], timer});
vector<point> line; swap(p, line[node]);
int n; }
lichao(){ if(r - l == 1) return;
n = 1; else if(left != m) add_line(p, 2 * node + 1, l, mid);
while(n < N) n *= 2; else add_line(p, 2 * node + 2, mid, r);
line = vector<point>(n << 2, {0, LLONG_MAX}); }
}
void add_line(point p, int node = 0, int l = -N, int r = N + 1){ void remove_line(int time){ //remove all lines with t = time
int mid = (l + r) >> 1; if([Link]()) return;
bool left = eval(p, l) < eval(line[node], l); while(![Link]()){
bool m = eval(p, mid) < eval(line[node], mid); auto [node, prev_line, t] = [Link]();
if(m) swap(p, line[node]); if(t != time) return;
library

if(r - l == 1) return; [Link]();

 line[node] = prev_line; return f(query(l, r, 2 * node + 1, l_node, m),
} query(l, r, 2 * node + 2, m, r_node));
} }
item query(int l, int r){ // [l, r] inclusive
ll get(ll x, int node = 0, int l = -N, int r = N + 1){ return query(l, r + 1, 0, 0, n);
int mid = (l + r) >> 1; }
if(r - l == 1) return eval(line[node], x); };
else if(x < mid) return min(eval(line[node], x), get(x, 2 * node + 1,
Bukayo Haka —

,→ l, mid));
else return min(eval(line[node], x), get(x, 2 * node + 2, mid, r));
}
}; §3.11 Segment tree (lazy propagation)
struct item{
ll val;
§3.10 Segment tree (point update, range query) item(){}
item(ll v){
val = v;
struct item{ }
ll val; };
item(){} struct segment_tree{
item(ll v){val = v;} int n; int NEUTRAL = 0;
}; vector<item> tree; vector<ll> lazy;
item NEUTRAL(-1); segment_tree(int n_){
struct segment_tree{ n = 1;

10
int n; while (n < n_) n *= 2;
vector<item> tree; tree = vector<item>(n << 1);
ll iden = 0; lazy = vector<ll>(n << 1);
segment_tree(int n_){ }
n = 1; ll modify(ll a, ll b){}
while (n < n_) n <<= 1; item f_query(item a, item b){}
tree = vector<item>(2 * n, NEUTRAL); void propagate(int node, int l, int r){
} if(lazy[node] == NEUTRAL) return;
item f(item a, item b){} if (r - l == 1) return;
void set(int i, ll val, int node, int l, int r){ tree[2 * node + 1];
if (r - l == 1){ tree[2 * node + 2];
tree[node] = item(val); lazy[2 * node + 1] = modify(lazy[2 * node + 1], lazy[node]);
return; lazy[2 * node + 2] = modify(lazy[2 * node + 2], lazy[node]);
} lazy[node] = NEUTRAL ;
int mid = (l + r) >> 1; }
if (i < mid) set(i, val, 2 * node + 1, l, mid); void set(int l, int r, ll val, int node, int l_node, int r_node){
else set(i, val, 2 * node + 2, mid, r); propagate(node, l_node, r_node);
tree[node] = f(tree[2 * node + 1], tree[2 * node + 2]); if (l_node >= r || r_node <= l) return;
} if (l_node >= l && r_node <= r){
void set(int i, ll val){ // here
set(i, val, 0, 0, n); return;
} }
item query(int l, int r, int node, int l_node, int r_node){ int mid = (r_node + l_node) >> 1;
if (l_node >= r || l >= r_node) return NEUTRAL; set(l, r, val, 2 * node + 1, l_node, mid);
if (l_node >= l && r_node <= r) return tree[node]; set(l, r, val, 2 * node + 2, mid, r_node);
library

int m = (l_node + r_node) >> 1; tree[node] = f_query(tree[2 * node + 1], tree[2 * node + 2]);
 } §4.2 Euler tour + DSU on trees
void set(int l, int r, ll val){
set(l, r + 1, val, 0, 0, n);
} vector<int> tin(n + 1), tout(n + 1), vertex(n + 1),sz(n + 1, 1), d(n + 1, 1);
item query(int l, int r, int node, int l_node, int r_node){ int timer = 0;
propagate(node, l_node, r_node); int euler (int node, int parent){
if (l_node >= r || r_node <= l) return item(0); tin[node] = timer++;
if (l_node >= l && r_node <= r) return tree[node]; vertex[tin[node]] = node;
Bukayo Haka —

int mid = (r_node + l_node) >> 1; for(auto child : graph[node]){

return f_query(query(l, r, 2 * node + 1, l_node, mid), if(child == parent) continue;
query(l, r, 2 * node + 2, mid, r_node)); d[child] = d[node] + 1;
} sz[node] += euler(child, node);
item query(int l, int r){ }
return query(l, r + 1, 0, 0, n); tout[node] = timer;
} return sz[node];
}; }
auto add =[&](int node){};
auto remove =[&](int node){};
void dfs (int node, int parent, bool keep){
int big = -1;
for(auto child : graph[node]){
§4 Graphs and trees if(child == parent) continue;
if(big == -1 || sz[child] > sz[big]) big = child;
}
for(auto child : graph[node])
§4.1 Dijkstra if(child != parent && child != big) dfs(child, node, 0);

11
if(big != -1) dfs(big, node, 1);
int n; for(auto child : graph[node]){
vector<vector<pair<int, ll>>> graph; if(child == parent || child == big) continue;
vector<ll> dijkstra(int node){ for(int i = tin[child]; i < tout[child]; i++){
vector<ll> ret(n + 1, 1e15); // do whatever you want
ret[node] = 0; add(vertex[i]);
using pi = pair<ll, int>; // dist,node }
priority_queue<pi, vector<pi>, greater<pi>> pq; }
[Link]({0, node}); add(node);
while (![Link]()){ if(!keep){
ll cost = [Link]().first; for(int i = tin[node]; i < tout[node]; i++) remove(vertex[i]);
node = [Link]().second; }
[Link](); };
if (ret[node] != cost)
continue;
for (auto adj : graph[node]){
ll w = cost + [Link];
if (ret[[Link]] > w){
ret[[Link]] = w; §4.3 LCA and Binary lifting
[Link]({w, [Link]});
}
} const int N = 3e5 + 9, LOG = 18;
} vector<int> graph[N];
return ret; int parent[N][LOG + 1], depth[N];
} void dfs(int u, int p = 0) {
library

parent[u][0] = p;
 depth[u] = depth[p] + 1; §5 String algorithms
for (int i = 1; i <= LOG; i++)
parent[u][i] = parent[parent[u][i - 1]][i - 1];
for (auto v: graph[u]) §5.1 KMP
if (v != p) dfs(v, u);
}
int lca(int u, int v) { vector<int> KMP(string s){
if (depth[u] < depth[v]) swap(u, v); int n = [Link]();
vector<int> pi(n);
Bukayo Haka —

for (int k = LOG; k >= 0; k--) {

if (depth[parent[u][k]] >= depth[v]) for(int i = 1; i < n; i++){
u = parent[u][k]; int j = pi[i - 1];
} while(j > 0 && s[i] != s[j]) j = pi[j - 1];
if (u == v) return u; if(s[i] == s[j]) j++;
for (int k = LOG; k >= 0; k--){ pi[i] = j;
if (parent[u][k] != parent[v][k]) { }
u = parent[u][k]; return pi;
v = parent[v][k]; };
} vector<vector<int>> automaton(string s){ // aut[[Link]() + 1][26]
} s += '#';
return parent[u][0]; int n = [Link]();
} vector<int> pi = KMP(s);
int kth(int u, int k) { vector<vector<int>> aut(n, vector<int>(26));
assert(k >= 0); for(int i = 0; i < n; i++){
while(k){ for(int j = 0; j < 26; j++){
u = parent[u][__lg(k & - k)]; if (i > 0 && 'a' + j != s[i]) aut[i][j] = aut[pi[i - 1]][j];
else aut[i][j] = i + ('a' + j == s[i]);

12
k ^= k & -k;
} }
return u; }
} return aut;
int dist(int u, int v) { }
int l = lca(u, v);
return depth[u] + depth[v] - (depth[l] * 2);
}
//kth node from u to v, 0th node is u §5.2 Manacher
int go(int u, int v, int k) {
int l = lca(u, v); struct manacher{
int d = dist(u, v); string s;
assert(k <= d); vector<int> p;
if (depth[l] + k <= depth[u]){ manacher(){}
return kth(u, k); void run_manacher(string s){
} int n = [Link]();
k -= depth[u] - depth[l]; [Link](n, 1);
return kth(v, depth[v] - depth[l] - k); int l = 1, r = 1;
} for(int i = 1; i < n; i++){
p[i] = max(0, min(r - i, p[l + r - i]));
while(i - p[i] >= 0 && i + p[i] < n && s[i + p[i]] == s[i - p[i]]){
p[i]++;
}
if(r < i + p[i]){
r = i + p[i];
library

l = i - p[i];
 } Hashing(string _s) {
} n = _s.size();
}; s = _s;
void build(string s){ hs = vector<pair<int, int>>(n);
string t; hs[0].first = (s[0] - 'a' + 1);
for(char c : s) t += string("#") + c; hs[0].second = (s[0] - 'a' + 1);
run_manacher(t + "#"); for (int i = 1; i < n; i++) {
} hs[i].first = add(hs[i - 1].first, mult(pw[i].first, (s[i] - 'a' +
Bukayo Haka —

int get_longest(int cen, bool odd){ ,→ 1)));

return p[2 * cen + 1 + (!odd)] - 1; hs[i].second = add(hs[i - 1].second, mult(pw[i].second, (s[i] - 'a' +
} ,→ 1)));
bool is_palindrome(int l, int r){ }
return (r - l + 1) <= get_longest((l + r) >> 1, l % 2 == r % 2); }
} pair<int, int> get_hash(int l, int r) {
}; if(l == 0) return {hs[r].first, hs[r].second};
pair<int,int> ret;
[Link] = mult(sub(hs[r].first, hs[l - 1].first), ipw[l].first);
[Link] = mult(sub(hs[r].second, hs[l - 1].second), ipw[l].second);
return ret;
§5.3 String hashing }
};
const int N = 1e6 + 9; struct Rabin{
const int MOD = 998244353; pair<int,int> hash;
int mult(ll a, ll b) { return (a * b) % MOD; } int n;
int add(ll a, ll b) { return (a + b) % MOD; } Rabin(){ hash = {0,0}; n = 0;}

13
int sub(ll a, ll b) { return (a - b + MOD)%MOD; } int getval(char c){ return c - 'a' + 1; }
int binpow (ll a, ll b){ Rabin(const string & s){
a %= MOD; n = [Link]();
ll res = 1; for(int i = 0 ; i < n; i++){
while(b > 0){if(b & 1) res = mult(res, a); a = mult(a, a); b >>= 1; } [Link] = add([Link], mult(getval(s[i]), pw[i].first));
return res; [Link] = add([Link], mult(getval(s[i]), pw[i].second));
} }
int divide(ll a, ll b) { return mult(a, binpow(b, MOD - 2)); } }
const int p1 = 31, p2 = 47; void push_back(char c){
const int ip1 = divide(1, p1) , ip2 = divide(1, p2); [Link] = add([Link], mult(pw[n].first, getval(c)));
pair<int, int> pw[N], ipw[N]; [Link] = add([Link], mult(pw[n++].second, getval(c)));
void pre() { }
pw[0] = {1, 1}; void push_front(char c){
ipw[0] = {1, 1}; [Link] = add(getval(c), mult([Link], p1));
for(int i = 1; i < N; i++) { [Link] = add(getval(c), mult([Link], p2));
pw[i].first = mult(pw[i -1].first, p1); n++;
pw[i].second = mult(pw[i -1].second, p2); }
ipw[i].first = mult(ipw[i - 1].first, ip1); void pop_back(char c){
ipw[i].second = mult(ipw[i - 1].second, ip2); if(n == 0) return;
} [Link] = sub([Link], mult(pw[--n].first, getval(c)));
} [Link] = sub([Link], mult(pw[n].second, getval(c)));
struct Hashing { n--;
int n; }
string s; void pop_front(char c){
vector<pair<int, int>> hs; if(n == 0) return;
[Link] = mult(ip1, sub([Link], getval(c)));
library

Hashing() {}
 [Link] = mult(ip2, sub([Link], getval(c))); §5.4 Z-algorithm
n--;
} vector<int> zfunction(string s){
void clear(){ int n = [Link]();
n = 0; hash = {0, 0}; vector<int> z(n);
} for(int i = 1, l = 0, r = 0; i < n; i++){
bool operator==(const Rabin & other){ if(i < r) z[i] = min(r - i, z[i - l]);
return other.n == n && [Link] == hash; while(i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
Bukayo Haka —

} if(i + z[i] > r){

bool operator!=(const Rabin & other){ r = i + z[i];
return other.n != n || [Link] != hash; l = i;
} }
}; }
return z;
}

14
library