- Template
- Flags
- Pragmas
- Debug
- Algoritmos
- Geometria
- Ângulo entre segmentos
- Distância entre pontos
- Envoltório convexo
- Orientação de ponto
- Verificar Quadrado
- Slope
- Mediatriz
- Rotação de ponto
- Árvores
- Binary Lifting
- Centróide
- Decomposição de Centróide
- Euler Tour
- Menor ancestral comum (LCA)
- Grafos
- Bellman-Ford
- BFS 0/1
- Caminho euleriano
- Detecção de ciclo
- Dijkstra
- Floyd Warshall
- Johnson
- Kosaraju
- MST
- Ordenação topológica
- Fluxo
- Pontes e articulações
- Outros
- Algoritmo de Mo
- Busca ternária
- Kadane
- Listar combinações
- Maior subsequência comum (LCS)
- Maior subsequência crescente (LIS)
- Pares com gcd x
- Próximo maior/menor elemento
- Matemática
- Coeficiente binomial
- Conversão de base
- Crivo de Eratóstenes
- Divisores
- Divisores rápido
- Divisores de vários números
- Equações diofantinas
- Exponenciação rápida
- Fatoração
- Fatoração com crivo
- Fatoração rápida
- Gauss
- Teorema chinês do resto
- Teste de primalidade
- Totiente de Euler
- Totiente de Euler rápido
- Transformada de Fourier
- Strings
- Autômato KMP
- Bordas
- Comparador de substring
- Distância de edição
- KMP
- Maior prefixo comum (LCP)
- Substrings palíndromas
- Menor rotação
- Ocorrências de substring com coringas
- Suffix array
- Geometria
- Estruturas
- Árvores
- BIT 2D
- DSU
- Heavy-light decomposition
- Ordered Set
- Segment tree
- Primeiro maior
- SegTree Lazy (Affine)
- Treap
- Wavelet Tree
- Geometria
- Círculo
- Polígono
- Reta
- Segmento
- Triângulo
- Matemática
- Matriz
- Strings
- Aho-Corasick
- Hash
- Hash Inverso
- Suffix Automaton
- Trie
- Bit Trie
- Outros
- Compressão
- Fila agregada
- Mex
- Venice set
- Árvores
- Utils
- Aritmética modular
- Bits
- Ceil division
- Combinatória modular
- Igualdade para floats
- Fatos
- Bitwise
- Geometria
- Matemática
- Strings
- Outros
#include <bits/stdc++.h>
using namespace std;
#ifdef croquete // BEGIN TEMPLATE ----------------------|
#include "dbg/dbg.h"
#define fio freopen("in.txt", "r", stdin)
#else
#define dbg(...)
#define fio cin.tie(0)->sync_with_stdio(0)
#endif
#define ll long long
#define vll vector<ll>
#define vvll vector<vll>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define all(xs) xs.begin(), xs.end()
#define rep(i, a, b) for (ll i = (a); i < (ll)(b); ++i)
#define per(i, a, b) for (ll i = (a); i >= (ll)(b); --i)
#define eb emplace_back
#define cinj cin.iword(0) = 1, cin
#define coutj cout.iword(0) = 1, cout
template <typename T> // read vector
istream& operator>>(istream& is, vector<T>& xs) {
assert(!xs.empty());
rep(i, is.iword(0), xs.size()) is >> xs[i];
return is.iword(0) = 0, is;
} template <typename T> // print vector
ostream& operator<<(ostream& os, vector<T>& xs) {
rep(i, os.iword(0), xs.size()) os << xs[i] << ' ';
return os.iword(0) = 0, os;
} void solve();
signed main() {
fio;
ll t = 1;
cin >> t;
while (t--) solve();
} // END TEMPLATE --------------------------------------|
void solve() {
}// BEGIN EXTRAS -----------------------------------------|
#define ull unsigned ll
#define vvvll vector<vvll>
#define vvpll vector<vpll>
#define tll tuple<ll, ll, ll>
#define vtll vector<tll>
#define pd pair<double, double>
#define x first
#define y second
map<char, pll> ds1 { {'R', {0, 1}}, {'D', {1, 0}}, {'L', {0, -1}}, {'U', {-1, 0}} };
vpll ds2 { {0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1} };
vpll ds3 { {1, 2}, {2, 1}, {-1, 2}, {-2, 1}, {1, -2}, {2, -1}, {-1, -2}, {-2, -1} };
// END EXTRAS -------------------------------------------|g++ -g -std=c++20 -fsanitize=undefined -fno-sanitize-recover -Wall -Wextra -Wshadow -Wconversion -Wduplicated-cond -Winvalid-pch -Wno-sign-compare -Wno-sign-conversion -Dcroquete -D_GLIBCXX_ASSERTIONS -fmax-errors=1
#pragma GCC target("popcnt") // if solution involves bitset
#include <bits/stdc++.h>
using namespace std;
template <typename T> void p(T x) {
int f = 0;
#define _(a, b) if constexpr (requires {(a);}) { (b); } else
#define D(d) cerr << "\e[94m" << (f++ ? d : "")
_(cout << x, cerr << x)
_(x.pop(), {struct y : T {using T::c;}; p(static_cast<y>(x).c);}) {
cerr << '{';
_(get<0>(x), apply([&](auto... a) {((D(","), p(a)), ...);}, x))
for (auto i : x) (requires {begin(*begin(x));} ? cerr << "\n\t" : D(",")), p(i);
cerr << '}';
}
} template <typename... T>
void pr(T... a) {int f = 0; ((D(" | "), p(a)), ...); cerr << "\e[m\n";}
#define dbg(...) { cerr << __LINE__ << ": [" << #__VA_ARGS__ << "] = "; pr(__VA_ARGS__); }// Menor ângulo orientado entre segmentos PQ e RS em radianos. O(1)
double angle(pd P, pd Q, pd R, pd S) {
assert(P != Q && R != S);
double ux = P.x - Q.x, uy = P.y - Q.y;
double vx = R.x - S.x, vy = R.y - S.y;
double cross = ux * vy - uy * vx;
double dot = ux * vx + uy * vy;
return atan2(cross, dot);
}// Distância euclidiana entre pontos P e Q. O(1)
double dist(pd P, pd Q) { return hypot(P.x - Q.x, P.y - Q.y); }template <typename T>
vector<pair<T, T>> make_hull(const vector<pair<T, T>>& PS) {
vector<pair<T, T>> hull;
for (auto& P : PS) {
ll sz = hull.size(); // colinear < 0
while (sz >= 2 && D(hull[sz - 2], hull[sz - 1], P) <= 0) {
hull.pop_back();
sz = hull.size();
}
hull.eb(P);
}
return hull;
}
// Convex hull dos pontos PS. Retorna ordenado anti-horário.
// Primeiro ponto e último são iguais. Cuidado com polígono que
// é só uma reta. O(Nlog(N))
template <typename T>
vector<pair<T, T>> monotone_chain(vector<pair<T, T>> PS) {
vector<pair<T, T>> lower, upper;
sort(all(PS));
lower = make_hull(PS);
reverse(all(PS));
upper = make_hull(PS);
lower.pop_back();
lower.emplace(lower.end(), all(upper));
return lower;
}// Positivo: P à esquerda de AB.
// Negativo: P à direita de AB.
// Zero: P colinear com AB.
// O(1)
template <typename T>
T D(pair<T, T> A, pair<T, T> B, pair<T, T> P) {
return (B.x - A.x) * (P.y - A.y) - (B.y - A.y) * (P.x - A.x);
}// Checa se 4 pontos formam um quadrado. O(1)
bool is_square(const vpll& ps) {
if (ps.size() != 4) return false;
vll ds;
rep(i, 0, 4) rep(j, i + 1, 4) {
ll dx = ps[i].x - ps[j].x, dy = ps[i].y - ps[j].y;
ds.eb(dx * dx + dy * dy);
}
sort(all(ds));
ds.erase(unique(all(ds)), ds.end());
return ds.size() == 2 && 2 * ds[0] == ds[1];
} // Retorna a fração irredutível dy/dx, dy sempre positivo. O(1)
pll slope(pll P, pll Q) {
ll dy = P.y - Q.y, dx = P.x - Q.x;
if (dy < 0 || (dy == 0 && dx < 0)) dy *= -1, dx *= -1;
ll g = gcd(dy, dx);
return {dy / g, dx / g};
}// Mediatriz do segmento PQ. O(1)
template <typename T>
Line<T> perpendicular_bisector(pair<T, T> P, pair<T, T> Q) {
T a = 2 * (Q.x - P.x), b = 2 * (Q.y - P.y);
T c = (P.x * P.x + P.y * P.y) - (Q.x * Q.x + Q.y * Q.y);
return {a, b, c};
}// Retorna o ponto P rotacionado. O(1)
pd rotate(pd P, double rad) {
double x = cos(rad) * P.x - sin(rad) * P.y;
double y = sin(rad) * P.x + cos(rad) * P.y;
return {x, y};
}constexpr ll LOG = 22;
vvll parent;
// ps é um vetor de pais que representa uma árvore ou grafo sucessor. O(Nlog(N))
void populate(const vll& ps) {
ll n = ps.size();
parent = vvll(n, vll(LOG));
rep(i, 0, n) parent[i][0] = ps[i];
rep(i, 1, LOG) rep(j, 0, n)
parent[j][i] = parent[ parent[j][i - 1] ][i - 1];
}
// Retorna o k-ésimo parente. 0-ésimo é u. Requer populate(). O(log(N))
ll kth(ll u, ll k) {
assert(!parent.empty() && 0 <= u && u < parent.size() && k >= 0);
rep(i, 0, LOG) if (k & (1LL << i))
u = parent[u][i];
return u;
}vll subtree;
ll subtree_dfs(const vvll& g, ll u, ll p) {
for (ll v : g[u]) if (v != p)
subtree[u] += subtree_dfs(g, v, u);
return subtree[u];
}
// Retorna uma nova raiz para a árvore g.
// Garantindo que o tamanho de todas as subárvores será n/2 ou menos. O(N)
ll centroid(const vvll& g, ll u, ll p = -1) {
ll sz = g.size();
if (p == -1) subtree = vll(sz, 1), subtree_dfs(g, u, p);
for (ll v : g[u]) if (v != p && subtree[v] * 2 > sz)
return centroid(g, v, u);
return u;
}vll parent, subtree;
ll subtree_dfs(const vvll& g, ll u, ll p) {
subtree[u] = 1;
for (ll v : g[u]) if (v != p && parent[v] == -1)
subtree[u] += subtree_dfs(g, v, u);
return subtree[u];
}
// Monta árvore de centróides com altura O(log(N)), o tamanho das subárvores de cada
// centróide será O(log(N)). O(N)
void centroid_decomp(const vvll& g, ll u = 0, ll p = -1, ll sz = 0) {
if (p == -1) p = -2, parent= vll(g.size(), -1), subtree = vll(g.size());
if (sz == 0) sz = subtree_dfs(g, u, -1);
for (ll v : g[u]) if (parent[v] == -1 && subtree[v] * 2 > sz)
return subtree[u] = 0, centroid_decomp(g, v, p, sz);
parent[u] = p;
for (ll v : g[u]) if (parent[v] == -1) centroid_decomp(g, v, u);
}ll timer = 0;
vll st, et;
// st vai ser o início do intervalo e et o final. O(N)
void euler_tour(const vvll& g, ll u, ll p = -1) {
if (p == -1) timer = 0, st = et = vll(g.size());
st[u] = ++timer;
for (ll v : g[u]) if (v != p)
euler_tour(g, v, u);
et[u] = timer;
}// Requer binary lifting. O(log(N))
ll lca(ll u, ll v) {
assert(1 <= u && u < parent.size() && 1 <= v && v < parent.size());
if (depth[u] < depth[v]) swap(u, v);
ll k = depth[u] - depth[v];
u = kth(u, k);
if (u == v) return u;
per(i, LOG - 1, 0) if (parent[u][i] != parent[v][i])
u = parent[u][i], v = parent[v][i];
return parent[u][0]; // poderia ser parent[v][0]
}// Retorna vetor com menores distâncias e anterior para reconstruir o caminho.
// Pesos podem ser negativos. Detecta ciclos negativos. O(EV)
constexpr ll NC = LLONG_MIN; // Ciclo negativo
pair<vll, vll> spfa(const vvpll& g, ll s) {
ll n = g.size();
vll ds(n, LLONG_MAX), cnt(n), pre(n);
vector<bool> inq(n);
deque<ll> q;
ds[s] = 0, q.push_back(s);
while (!q.empty()) {
ll u = q.front(); q.pop_front(), inq[u] = false;
for (auto [w, v] : g[u]) {
if (ds[u] == NC) { // Espalha ciclo negativo
if (ds[v] != NC)
q.push_back(v), inq[v] = true;
ds[v] = NC;
} else if (ds[u] + w < ds[v]) {
ds[v] = ds[u] + w, pre[v] = u;
if (!inq[v]) {
if (!q.empty() && ds[v] < ds[q.front()])
q.push_front(v);
else q.push_back(v);
inq[v] = true;
if (++cnt[v] > n) ds[v] = NC;
}
}
}
}
return {ds, pre};
}// Retorna vetor com menores distâncias. Pesos ou 0 ou 1. O(N)
vll bfs01(const vvpll& g, ll s) {
vll ds(g.size(), LLONG_MAX);
deque<ll> dq;
dq.eb(s); ds[s] = 0;
while (!dq.empty()) {
ll u = dq.front(); dq.pop_front();
for (auto [w, v] : g[u])
if (ds[u] + w < ds[v]) {
ds[v] = ds[u] + w;
if (w == 1) dq.eb(v);
else dq.emplace_front(v);
}
}
return ds;
}// Caminho Euleriano passa por toda aresta uma única vez. Ciclo começa e termina
// no mesmo nó.
vll eulerian(const vvll& g) {
}// Retorna um vetor com vértices ou arestas do ciclo.
// edges é se quer as arestas e d é se o grafo é direcionado.
// O grafo é (id da aresta, v). O(V + E)
vll cycle(const vvpll& g, bool edges, bool d) {
ll n = g.size();
vll color(n + 1), parent(n + 1), edge(n + 1), res;
auto dfs = [&](auto&& self, ll u, ll p) -> ll {
color[u] = 1;
bool parent_skipped = false;
for (auto [i, v] : g[u]) {
if (!d && v == p && !parent_skipped)
parent_skipped = true;
else if (color[v] == 0) {
parent[v] = u, edge[v] = i;
if (ll end = self(self, v, u); end != -1) return end;
} else if (color[v] == 1) {
parent[v] = u, edge[v] = i;
return v;
}
}
color[u] = 2;
return -1;
};
rep(u, 0, n) if (color[u] == 0)
if (ll end = dfs(dfs, u, -1), start = end; end != -1) {
do {
res.eb(edges ? edge[end] : end);
end = parent[end];
} while (end != start);
reverse(all(res));
return res;
}
return {};
}// Retorna vetor com menores distâncias e anterior para reconstruir o caminho.
// A distância só é final na primeira vez que o vértice sai da fila.
// Não funciona com pesos negativos, mas dá para encontrar uma função potencial
// que transforma os pesos em positivos. É uma função tal que o novo peso é
// w' = w + p(u) - p(v) >= 0, e a distância será dist(u, v) = dist'(u, v) - p(u) + p(v).
// O(Elog(V))
pair<vll, vll> dijkstra(const vvpll& g, ll s) {
vll ds(g.size(), LLONG_MAX), pre = ds;
priority_queue<pll, vpll, greater<>> pq;
ds[s] = 0, pq.emplace(ds[s], s);
while (!pq.empty()) {
auto [t, u] = pq.top(); pq.pop();
if (t > ds[u]) continue;
for (auto [w, v] : g[u])
if (t + w < ds[v]) {
ds[v] = t + w, pre[v] = u;
pq.emplace(ds[v], v);
}
}
return {ds, pre};
}
vll get_path(const vll& pre, ll u) {
vll p;
while (u != LLONG_MAX) p.eb(u), u = pre[u];
reverse(all(p));
return p;
}// Retorna vetor com menores distâncias para todos pares de vértices.
// Pesos podem ser negativos. Detecta ciclos negativos. O(V³)
constexpr ll oo = 4e18;
vvll floyd_warshall(const vvpll& g) {
ll n = g.size();
vvll ds(n, vll(n, oo));
rep(u, 0, n) {
ds[u][u] = 0;
for (auto [w, v] : g[u]) ds[u][v] = min(ds[u][v], w);
}
rep(k, 0, n) rep(u, 0, n) rep(v, 0, n)
ds[u][v] = min(ds[u][v], ds[u][k] + ds[k][v]);
rep(k, 0, n) if (ds[k][k] < 0)
rep(u, 0, n) rep(v, 0, n)
if (ds[u][k] != oo && ds[k][v] != oo)
ds[u][v] = -oo;
return ds;
}// Retorna vetor com menores distâncias para todos pares de vértices.
// Pesos podem ser negativos. Detecta ciclos negativos.
// Requer Bellman-Ford e Dijkstra. O(EVlog(N))
vvll johnson(vvpll& g) {
ll n = g.size();
rep(v, 1, n) g[0].eb(0, v);
auto [dsb, _] = spfa(g, 0);
vvll dsj(n, vll(n, NC));
rep(u, 1, n) {
if (dsb[u] == NC) return dsj; // Ciclo negativo
for (auto& [w, v] : g[u])
w += dsb[u] - dsb[v];
}
rep(u, 1, n) {
auto [dsd, __] = dijkstra(g, u);
rep(v, 1, n)
if (dsd[v] == LLONG_MAX)
dsj[u][v] = LLONG_MAX;
else
dsj[u][v] = dsd[v] - dsb[u] + dsb[v];
}
return dsj;
}// Retorna o grafo condensado, componentes fortemente conectados e vetor
// para saber o líder dos vértices. Os componentes são acessados pelo líder. O(Elog(V))
tuple<vvll, map<ll, vll>, vll> kosaraju(const vvll& g) {
ll n = g.size();
vvll inv(n), cond(n);
map<ll, vll> scc;
vll vs(n), leader(n), order;
auto dfs = [&vs](auto&& self, const vvll& h, vll& out, ll u) -> void {
vs[u] = true;
for (ll v : h[u]) if (!vs[v])
self(self, h, out, v);
out.eb(u);
};
rep(u, 0, n) {
for (ll v : g[u]) inv[v].eb(u);
if (!vs[u]) dfs(dfs, g, order, u);
}
vs = vll(n, false);
reverse(all(order));
for (ll u : order) if (!vs[u]) {
vll cc;
dfs(dfs, inv, cc, u);
scc[u] = cc;
for (ll v : cc) leader[v] = u;
}
rep(u, 0, n) for (ll v : g[u]) if (leader[u] != leader[v])
cond[leader[u]].eb(leader[v]);
return {cond, scc, leader};
}// Retorna arestas da MST. Requer DSU. O(Nlog(N))
vtll kruskal(vtll& edges, ll n) {
DSU dsu(n + 1);
vtll mst;
sort(all(edges)); // Muda ordem se quiser máximo
for (auto [w, u, v] : edges)
if (dsu.merge(u, v))
mst.eb(w, u, v);
return mst;
}// Primeiro os vértices que ninguém aponta. O(V + E)
vll toposort(const vvll& g) {
ll n = g.size();
vll degree(n), res;
rep(u, 1, n) for (ll v : g[u])
++degree[v];
queue<ll> q;
rep(u, 1, degree.size())
if (degree[u] == 0)
q.emplace(u);
while (!q.empty()) {
ll u = q.top();
q.pop();
res.eb(u);
for (ll v : g[u])
if (--degree[v] == 0)
q.emplace(v);
}
if (res.size() != n - 1) return {}; // Ciclo
return res;
}// Resgatar caminho: faz dfs, só vai se a aresta for real e c = 0.
// Bloquear caminho: Seta w += 1.
struct Flow {
struct Edge { bool real; ll c, v, rev, w; };
ll n, s, t, l = 1;
vector<vector<Edge>> g;
vll ds, ptr;
Flow(ll n, ll source, ll sink)
: n(n), s(source), t(sink), g(n + 1), ds(n + 1), ptr(n + 1) {}
void add_edge(ll c, ll u, ll v, ll w = 0) { // w se mcmf
if (c > 1) l = 1 << 31;
g[u].eb(true, c, v, g[v].size(), w);
g[v].eb(false, 0, u, g[u].size() - 1, -w);
}
// O(E²logC), com capacidades unitárias é melhor.
ll max_flow() {
ll f = 0;
while (l >>= 1) while (bfs())
while (ll nf = dfs(s, LLONG_MAX)) f += nf;
return f;
}
// Se bipartido, checa para (u, v) se c = 0.
vpll min_cut() {
max_flow();
vpll res;
rep(u, 0, n + 1) if (ds[u] != 0)
for (auto e : g[u])
if (e.real && e.c == 0 && ds[e.v] == 0)
res.eb(u, e.v);
return res;
}
// Reusa ptr como parent_edge_idx
pll min_cost_max_flow(ll k) {
ll c = 0, f = 0;
vll pre(n + 1);
while (f < k && spfa(pre)) {
ll p = k - f;
for (ll v = t; v != s; v = pre[v])
p = min(p, g[pre[v]][ptr[v]].c);
f += p, c += p * ds[t];
for (ll v = t; v != s; v = pre[v]) {
auto& e = g[pre[v]][ptr[v]];
e.c -= p;
g[v][e.rev].c += p;
}
}
return {c, f};
}
private:
ll dfs(ll u, ll f) {
if (u == t || !f) return f;
for (ll& i = ptr[u]; i < (ll)g[u].size(); ++i) {
auto& e = g[u][i];
if (ds[e.v] == ds[u] + 1)
if (ll p = dfs(e.v, min(f, e.c))) {
e.c -= p, g[e.v][e.rev].c += p;
return p;
}
}
return 0;
}
ll bfs() {
fill(all(ds), 0), fill(all(ptr), 0);
queue<ll> q;
ds[s] = 1, q.emplace(s);
while (!q.empty() && !ds[t]) {
ll u = q.front(); q.pop();
for (auto e : g[u]) if (!ds[e.v] && e.c >= l)
ds[e.v] = ds[u] + 1, q.emplace(e.v);
}
return ds[t];
}
ll spfa(vll& pre) {
fill(all(ds), LLONG_MAX), fill(all(ptr), -1);
deque<ll> q;
vector<bool> inq(n + 1);
ds[s] = 0, q.push_back(s);
while (!q.empty()) {
ll u = q.front(); q.pop_front(), inq[u] = false;
rep(i, 0, g[u].size()) {
auto& e = g[u][i];
if (e.c > 0 && ds[u] + e.w < ds[e.v]) {
ds[e.v] = ds[u] + e.w;
ptr[e.v] = i, pre[e.v] = u;
if (!inq[e.v]) {
if (!q.empty() && ds[e.v] < ds[q.front()])
q.push_front(e.v);
else q.push_back(e.v);
inq[e.v] = true;
}
}
}
}
return ds[t] != LLONG_MAX;
}
};// Pontes são arestas que se removidas criam componentes.
// Articulações são vértices que se removidos criam componentes.
// O grafo tem que ser (id da aresta, v). O(E + V)
vll bridges_or_articulations(const vvpll& g, bool get_bridges) {
ll n = g.size(), timer = 0;
vector<bool> vs(n);
vll st(n), low(n), res;
auto dfs = [&](auto&& self, ll u, ll p) -> void {
vs[u] = true;
st[u] = low[u] = timer++;
ll children = 0;
bool parent_skipped = false;
for (auto [i, v] : g[u]) {
if (v == p && !parent_skipped) {
parent_skipped = true;
continue;
}
if (vs[v]) low[u] = min(low[u], st[v]);
else {
self(self, v, u);
low[u] = min(low[u], low[v]);
if (get_bridges && low[v] > st[u]) res.eb(i);
else if (!get_bridges && p != 0 && low[v] >= st[u]) res.eb(u);
++children;
}
}
if (!get_bridges && p == 0 && children > 1) res.eb(u);
};
rep(i, 0, g.size()) if (!vs[i]) dfs(dfs, i, 0);
if (!get_bridges) {
sort(all(res));
res.erase(unique(all(res)), res.end());
}
return res;
}struct Query {
ll l, r, idx, block;
bool operator<(const Query& q) const {
if (block != q.block) return block < q.block;
return (block & 1 ? (r < q.r) : (r > q.r));
}
};
template <typename T, typename Tans>
struct Mo {
vector<T> vs;
vector<Query> qs;
const ll block_size;
Mo(const vector<T>& xs) : vs(xs), block_size((int)ceil(sqrt(xs.size()))) {}
void add_query(ll l, ll r) {
qs.emplace_back(l, r, qs.size(), l / block_size);
}
// O(Nsqrt(N))
auto solve() {
vector<Tans> answers(qs.size());
sort(all(qs));
ll cur_l = 0, cur_r = -1;
for (auto q : qs) {
while (cur_l > q.l) add(--cur_l);
while (cur_r < q.r) add(++cur_r);
while (cur_l < q.l) remove(cur_l++);
while (cur_r > q.r) remove(cur_r--);
answers[q.idx] = get_answer();
}
return answers;
}
private:
inline void add(ll idx) {}
inline void remove(ll idx) {}
inline Tans get_answer() {}
};// f: Função unimodal. Retorna o maior valor da função no intervalo.
// Se é uma função inteira use busca binária. O(log(N)).
double ternary_search(double lo, double hi, function<double(double)> f) {
rep(i, 0, 100) {
double mi1 = lo + (hi - lo) / 3.0, mi2 = hi - (hi - lo) / 3.0;
if (f(mi1) < f(mi2)) lo = mi1;
else hi = mi2;
}
return f(lo);
}// Retorna a maior ou menor soma contígua e menor intervalo. O(N)
template <typename T>
tuple<T, ll, ll> kadane(const vector<T>& xs, bool mx = true) {
T res = 0, csum = 0;
ll l = -1, r = -1, j = 0;
rep(i, 0, xs.size()) {
csum += xs[i] * (mx ? 1 : -1);
if (csum < 0) csum = 0, j = i + 1; // > para maior intervalo
else if (csum > res || (csum == res && i - j + 1 < r - l + 1))
res = csum, l = j, r = i;
}
return {res * (mx ? 1 : -1), l, r};
}// Lista todas as combinações com k elementos.
// Pode ser melhor pedir por n - k e pegar o complementar ou fazer
// uma lógica inversa. O(K(binom(N, K)))
void binom(ll k, const vll& xs) {
vll ks;
auto f = [&](auto&& self, ll i, ll rem) {
if (rem == 0) { // Processa aqui
cout << ks << '\n';
return;
}
if (i == xs.size()) return;
ks.eb(xs[i]);
self(self, i + 1, rem - 1);
ks.pop_back();
self(self, i + 1, rem);
}; f(f, 0, k);
}// Retorna uma das maiores sequências comuns. O(NM)
template <typename T>
T lcs(const T& xs, const T& ys) {
ll n = xs.size(), m = ys.size();
vvll dp(n + 1, vll(m + 1));
vvpll pre(n + 1, vpll(m + 1, {-1, -1}));
rep(i, 1, n + 1) rep(j, 1, m + 1)
if (xs[i - 1] == ys[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1], pre[i][j] = {i - 1, j - 1};
else {
if (dp[i][j - 1] >= dp[i][j])
dp[i][j] = dp[i][j - 1], pre[i][j] = pre[i][j - 1];
if (dp[i - 1][j] >= dp[i][j])
dp[i][j] = dp[i - 1][j], pre[i][j] = pre[i - 1][j];
}
T res;
while (pre[n][m].first != -1) {
tie(n, m) = pre[n][m];
res.eb(xs[n]); // += se T é uma string.
}
reverse(all(res));
return res; // dp[n][m] é o tamanho da lcs.
}// Retorna os índices da maior subsequência crescente. O(Nlog(N))
vll lis(const vll& xs) {
assert(!xs.empty());
vll ss, idx, pre(xs.size()), ys;
rep(i, 0, xs.size()) {
// upper_bound se quiser não decrescente
ll j = lower_bound(all(ss), xs[i]) - ss.begin();
if (j == ss.size()) ss.eb(), idx.eb();
if (j == 0) pre[i] = -1;
else pre[i] = idx[j - 1];
ss[j] = xs[i], idx[j] = i;
}
ll i = idx.back();
while (i != -1) ys.eb(i), i = pre[i];
reverse(all(ys));
return ys;
}// Retorna vetor com quantidade de pares com gcd igual a i. O(Nlog(N))
vll gcd_pairs(const vll& xs) {
ll MAXN = (ll)1e6 + 1;
vll dp(MAXN, -1), ms(MAXN), hist(MAXN);
for (ll x : xs) ++hist[x];
rep(i, 1, MAXN)
for (ll j = i; j < MAXN; j += i)
ms[i] += hist[j];
per(i, MAXN - 1, 1) {
dp[i] = ms[i] * (ms[i] - 1) / 2;
for (ll j = 2 * i; j < MAXN; j += i)
dp[i] -= dp[j];
}
return dp;
}// Retorna vetor com índices do primeiro elemento menor à esquerda. O(N)
template <typename T>
vector<T> closests(const vector<T>& xs) {
ll n = xs.size();
vll dp(n, -1); // n: para direita
// n - 1 -> 0: para direita
rep(i, 0, n) {
ll j = i - 1; // i + 1: para direita
// < n <= se quiser estritamente maior
while (j >= 0 && xs[j] >= xs[i]) j = dp[j];
dp[i] = j;
}
return dp;
}// Primeira vez O(N²), depois O(1)
ll binom(ll n, ll k) {
constexpr ll MAXN = 64;
static vvll dp(MAXN + 1, vll(MAXN + 1));
if (dp[0][0] != 1) {
dp[0][0] = 1;
rep(i, 1, MAXN + 1) rep(j, 0, i + 1)
dp[i][j] = dp[i - 1][j] + (j ? (dp[i - 1][j - 1]) : 0);
}
if (n < k || n * k < 0) return 0;
return dp[n][k];
}// Exemplo: (x = 6, b = 2): { 1, 1, 0 }. O(log(N))
vll to_base(ll x, ll b) {
assert(b > 1);
vll res;
while (x) res.eb(x % b), x /= b;
reverse(all(res));
return res;
}// Retorna primos e vetor menor fator primo. O(Nlog(log(N)))
pair<vll, vll> sieve(ll n) {
vll ps, spf(n + 1);
rep(i, 2, n + 1) if (!spf[i]) {
spf[i] = i;
ps.eb(i);
for (ll j = i * i; j <= n; j += i)
if (!spf[j]) spf[j] = i;
}
return {ps, spf};
}// Vetor não ordenado com os divisores. O(sqrt(N))
vll divisors(ll x) {
vll ds;
for (ll i = 1; i * i <= x; ++i)
if (x % i == 0) {
ds.eb(i);
if (i * i != x) ds.eb(x / i);
}
return ds;
}// Vetor não ordenado com os divisores. Requer uma fatoração rápida.
vll divisors(ll x) {
vll fs = factors(x), ds{1}; // Garanta fatores ordenados
ll prev = 1, sz_prev = 1;
rep(i, 0, fs.size()) {
ll f = fs[i];
if (i > 0 && fs[i] == fs[i - 1])
prev = f *= prev;
else prev = fs[i], sz_prev = ds.size();
rep(j, 0, sz_prev) ds.eb(ds[j] * f);
}
return ds;
}// Vetor com divisores para cada número em xs. O(Nlog(N))
vvll divisors(const vll& xs) {
ll MAXN = (ll)1e6, mx = 0;
vector<bool> hist(MAXN);
for (ll y : xs) {
mx = max(mx, y);
hist[y] = true;
}
vvll ds(mx + 1);
rep(i, 1, mx + 1)
for (ll j = i; j <= mx; j += i)
if (hist[j]) ds[j].eb(i);
return ds;
}// Retorna (x, y, d), solução para aX + bY = c, d é o gcd. O(log(N))
tuple<ll, ll, ll> diophantine(ll a, ll b, ll c = 1) {
if (b == 0) {
if (c % a != 0) return {LLONG_MAX, LLONG_MAX, a};
return {c / a, 0, a};
}
auto [x, y, d] = diophantine(b, a % b, c);
if (x == LLONG_MAX) return {x, y, a};
return {y, x - a / b * y, d};
}template <typename T>
T pot(T a, ll b) { // O(log(N))
T res(1); // Identidade de T
while (b) {
if (b & 1) res = res * a;
a = a * a, b /= 2;
}
return res;
}// Vetor ordenado com os fatores. O(sqrt(N))
vll factors(ll x) {
vll fs;
for (ll i = 2; i * i <= x; ++i)
while (x % i == 0)
fs.eb(i), x /= i;
if (x > 1) fs.eb(x);
return fs;
}// Vetor ordenado com os fatores. Requer crivo. O(log(N))
vll factors(ll x, const vll& spf) {
vll fs;
while (x != 1) fs.eb(spf[x]), x /= spf[x];
return fs;
}ll rho(ll n) {
auto f = [n](ll x) { return mul(x, x, n) + 1; };
ll init = 0, x = 0, y = 0, prod = 2, i = 0;
while (i & 63 || gcd(prod, n) == 1) {
if (x == y) x = ++init, y = f(x);
if (ll t = mul(prod, (x - y), n); t) prod = t;
x = f(x), y = f(f(y)), ++i;
}
return gcd(prod, n);
}
// Vetor não ordenado com os fatores. Requer teste de primalidade. O(N^(1/4)log(N))
vll factors(ll x) {
if (x == 1) return {};
if (is_prime(x)) return {x};
ll d = rho(x);
vll l = factors(d), r = factors(x / d);
l.insert(l.end(), all(r));
return l;
}// const double EPS = 1e-9; // double
const ll EPS = 0; // mod
#define abs(x) (x).v // mod
// Recebe uma matriz representando o sistema linear e retorna os
// valores de cada variável. O(N³)
template <typename T>
vector<T> gauss(vector<vector<T>>& ls) {
ll n = ls.size(), m = ls[0].size() - 1;
vll where(m, -1);
for (ll col = 0, row = 0; col < m && row < n; ++col) {
ll sel = row;
rep(i, row, n) if (abs(ls[i][col]) > abs(ls[sel][col])) sel = i;
if (abs(ls[sel][col]) <= EPS) continue;
rep(i, col, m + 1) swap(ls[sel][i], ls[row][i]);
where[col] = row;
rep(i, 0, n) if (i != row) {
T c = ls[i][col] / ls[row][col];
rep(j, col, m + 1) ls[i][j] -= ls[row][j] * c;
}
++row;
}
vector<T> ans(m);
rep(i, 0, m) if (where[i] != -1) ans[i] = ls[where[i]][m] / ls[where[i]][i];
rep(i, 0, n) {
T sum = 0;
rep(j, 0, m) sum += ans[j] * ls[i][j];
if (abs(sum - ls[i][m]) > EPS) return {};
}
return ans;
}// Resolve sistema da forma:
// x = a1 mod m1
// x = a2 mod m2
// ...
// Retorna (x, m) solução é x mod m.
// Requer equações diofantinas. O(Nlog(N))
pll crt(const vpll& congruences) {
auto [s, l] = congruences[0];
for (auto [a, m] : congruences) {
auto [x, y, d] = diophantine(l, -m, a - s);
if (x == LLONG_MAX) return {x, y};
s = (a + y % (l / d) * m + l * m / d) % (l * m / d);
l = l * m / d;
}
return {s, l};
}ll mul(ll a, ll b, ll p) { return (__int128)a * b % p; }
ll pot(ll a, ll b, ll p) {
ll res(1);
a %= p;
while (b) {
if (b & 1) res = mul(res, a, p);
a = mul(a, a, p), b /= 2;
}
return res;
}
// O(log²(N))
bool is_prime(ll x) { // Miller Rabin
if (x < 2) return false;
if (x <= 3) return true;
if (x % 2 == 0) return false;
ll r = __builtin_ctzll(x - 1), d = x >> r;
for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23}) {
if (a == x) return true;
a = pot(a, d, x);
if (a == 1 || a == x - 1) continue;
rep(i, 1, r) {
a = mul(a, a, x);
if (a == x - 1) break;
}
if (a != x - 1) return false;
}
return true;
}// Retorna vetor com totiente para cada número em [1, n].
// Totiente é a quantidade de coprimos a x em [1, x]. O(Nlog(log(N)))
vll totient(ll n) {
vll phi(n + 1);
iota(all(phi), 0);
rep(i, 2, n + 1) if (phi[i] == i)
for (ll j = i; j <= n; j += i)
phi[j] -= phi[j] / i;
return phi;
}// Retorna totiente. Requer uma fatoração rápida.
// Totiente é a quantidade de coprimos a x em [1, x].
ll totient(ll x) {
vll fs = factors(x);
sort(all(fs));
fs.erase(unique(all(fs)), fs.end());
ll res = x;
for (ll f : fs) res = (res / f) * (f - 1);
return res;
}#define T complex<double> // fft
// #define T Mi<M> // ntt
// constexpr ll M = 998244353; // ntt
// constexpr T G = 3; // ntt
vector<T> roots;
void init(ll n) {
if (roots.size() >= n) return;
ll k = roots.empty() ? 2 : roots.size();
while (k < n) k <<= 1;
roots.resize(k);
const double PI = acos(-1); // ftt
for (int i = 0; i < k; i++) { // ftt
double ang = 2 * PI * i / k; // ftt
roots[i] = T(cos(ang), sin(ang)); // ftt
} // ftt
// T r = pot(G, (M - 1) / k); // ntt
// roots[0] = 1; // ntt
// for (int i = 1; i < k; i++) roots[i] = roots[i - 1] * r; // ntt
}
void bit_reversal(vector<T>& a, ll n) {
ll j = 0;
rep(i, 1, n) {
ll bit = n >> 1;
for (; j & bit; bit >>= 1) j ^= bit;
j ^= bit;
if (i < j) swap(a[i], a[j]);
}
}
void fft(vector<T>& a, bool invert) {
ll n = a.size();
init(n);
ll root_max = roots.size();
bit_reversal(a, n);
for (ll len = 2; len <= n; len <<= 1) {
ll step = root_max / len;
for (ll i = 0; i < n; i += len) {
for (ll j = 0; j < len / 2; j++) {
ll idx = j * step;
if (invert && idx) idx = root_max - idx;
T u = a[i + j], v = a[i + j + len / 2] * roots[idx];
a[i + j] = u + v, a[i + j + len / 2] = u - v;
}
}
}
if (invert) {
T inv_n = T(1) / T(n);
for (T& x : a) x *= inv_n;
}
}
// a, b são vetores com os coeficientes dos polinômios.
// Requer aritmética modular se for NTT.
// se for FFT pode precisar arredondar: round(.real()). O(Nlog(N))
vector<T> convolution(const vector<T>& a, const vector<T>& b) {
vector<T> fa(all(a)), fb(all(b));
ll n = 1;
while (n < a.size() + b.size()) n <<= 1;
fa.resize(n), fb.resize(n);
fft(fa, false), fft(fb, false);
rep(i, 0, n) fa[i] *= fb[i];
fft(fa, true);
return fa;
}// O(26N)
vvll kmp_automaton(const string& s) {
ll n = s.size();
vll pi(n);
vvll aut(n + 1, vll(26));
rep(i, 0, n + 1) {
rep(c, 0, 26)
if (i < n && c == s[i] - 'a') aut[i][c] = i + 1;
else if (i > 0) aut[i][c] = aut[pi[i - 1]][c];
if (i > 0 && i < n) pi[i] = aut[pi[i - 1]][s[i] - 'a'];
}
return aut;
}// O(N)
vll borders(const T& s) {
vll pi = kmp(s), res;
ll b = pi[s.size() - 1];
while (b >= 1) res.eb(b), b = pi[b - 1];
reverse(all(res));
return res;
}// Compara substrings. i, j são os inícios de cada substring.
// m é o tamanho das duas substrings (igual). cs é a classe de equivalência
// do suffix array. Retorna 0 se igual, -1 se menor, 1 se maior.
// Requer suffix array. O(1)
ll compare(ll i, ll j, ll m, const vvll& cs) {
ll k = 0; // Move pra fora
while ((1 << (k + 1)) <= m) ++k; // Move pra fora
pll a = {cs[k][i], cs[k][i + m - (1 << k)]};
pll b = {cs[k][j], cs[k][j + m - (1 << k)]};
return a == b ? 0 : (a < b ? -1 : 1);
}// Retorna distância de edição e operações. -, c, =
// remoção, inserção e mantém. c->d substitui c por d.
// Transformar s em t. O(MN)
pair<ll, string> edit(const string& s, string& t) {
ll ci = 1, cr = 1, cs = 1, m = s.size(), n = t.size();
vvll dp(m + 1, vll(n + 1)), pre = dp;
rep(i, 0, m + 1) dp[i][0] = i*cr, pre[i][0] = 'r';
rep(j, 0, n + 1) dp[0][j] = j*ci, pre[0][j] = 'i';
rep(i, 1, m + 1)
rep(j, 1, n + 1) {
ll ins = dp[i][j - 1] + ci, del = dp[i - 1][j] + cr;
ll subs = dp[i - 1][j - 1] + cs * (s[i - 1] != t[j - 1]);
dp[i][j] = min({ ins, del, subs });
pre[i][j] = (dp[i][j] == ins ? 'i' : (dp[i][j] == del ? 'r' : 's'));
}
ll i = m, j = n;
string ops;
while (i || j) {
if (pre[i][j] == 'i') ops += t[--j];
else if (pre[i][j] == 'r')
ops += '-', --i;
else {
--i, --j;
if (s[i] == t[j]) ops += '=';
else
ops += "]", ops += t[j], ops += ">-", ops += s[i], ops += "[";
}
}
reverse(all(ops));
return {dp[m][n], ops};
}// Retorna um vetor com os tamanhos das bordas para cada prefixo. O(N)
template <typename T>
vll kmp(const T& s) {
ll n = s.size();
vll pi(n);
rep(i, 1, n) {
ll j = pi[i - 1];
while (j > 0 && s[i] != s[j])
j = pi[j - 1];
pi[i] = j + (s[i] == s[j]);
}
return pi;
}// Requer suffix array. lcp[i] é o maior prefixo comum entre os sufixos
// sa[i] e sa[i + 1]. Para pegar entre sa[i] e sa[j] faz
// lcp(i, j) = min({lcp[i], ..., lcp[j - 1]}). O(N)
vll lcp(const string& s, const vll& sa) {
ll n = s.size(), k = 0;
vll rank(n), lcp(n - 1);
rep(i, 0, n) rank[sa[i]] = i;
rep(i, 0, n) {
if (rank[i] == n - 1) {
k = 0;
continue;
}
ll j = sa[rank[i] + 1];
while (i + k < n && j + k < n && s[i + k] == s[j + k])
++k;
lcp[rank[i]] = k;
if (k) --k;
}
return lcp;
}// Retorna vetor de pares (deven, dodd). Representam o maior palíndromo
// centrado em i, de tamanho par e ímpar. Os de tamanho par estão
// centrados em i - 1 e i. O(N)
vpll manacher(const string& s) {
string t = "#";
for(char c : s) t += c, t += '#';
ll n = t.size(), l = 0, r = 1;
t = "$" + t + "^";
vll p(n + 2);
rep(i, 1, n + 1) {
p[i] = max(0LL, min(r - i, p[l + (r - i)]));
while(t[i - p[i]] == t[i + p[i]]) p[i]++;
if(i + p[i] > r) l = i - p[i], r = i + p[i];
}
ll m = s.size(), i = 0;
vpll res(m);
for (auto& [deven, dodd] : res)
deven = p[2 * i + 1] - 1, dodd = p[2 * i + 2] - 1, ++i;
return res;
}// Retorna o índice da menor rotação. O(N)
ll min_rotation(const string& s) {
ll n = s.size(), k = 0;
vll f(2 * n, -1);
rep(j, 1, 2 * n) {
ll i = f[j - k - 1];
while (i != -1 && s[j % n] != s[(k + i + 1) % n]) {
if (s[j % n] < s[(k + i + 1) % n])
k = j - i - 1;
i = f[i];
}
if (i == -1 && s[j % n] != s[(k + i + 1) % n]) {
if (s[j % n] < s[(k + i + 1) % n])
k = j;
f[j - k] = -1;
}
else
f[j - k] = i + 1;
}
return k;
}// A substring pode ter coringas '?'. Requer FFT.
// Retorna o vetor com os índices das ocorrências. O(Nlog(N))
vll occur(const string& s, const string& t) {
ll n = s.size(), m = t.size(), q = 0;
if (n < m) return {};
vector<T> a(n), b(m);
rep(i, 0, n) {
double ang = acos(-1) * (s[i] - 'a') / 13;
a[i] = {cos(ang), sin(ang)};
}
rep(i, 0, m) {
if (t[m - i - 1] == '?') ++q;
else {
double ang = acos(-1) * (t[m - 1 - i] - 'a') / 13;
b[i] = {cos(ang), -sin(ang)};
}
}
auto c = convolution(a, b);
vll res;
rep(i, 0, n)
if (abs(c[m - 1 + i].real() - (double)(m - q)) < 1e-3)
res.eb(i);
return res;
}template <typename T>
void csort(const T& xs, vll& ps, ll alpha) {
vll hist(alpha + 1);
for (auto x : xs) ++hist[x];
rep(i, 1, alpha + 1) hist[i] += hist[i - 1];
per(i, ps.size() - 1, 0) ps[--hist[xs[i]]] = i;
}
template <typename T>
void upd_eq_class(vll& cs, const vll& ps, const T& xs) {
cs[0] = 0;
rep(i, 1, ps.size())
cs[ps[i]] = cs[ps[i - 1]] + (xs[ps[i - 1]] != xs[ps[i]]);
}
// k é o mesmo k do comparador de substrings se for usar. O(N(log(N)))
// Suffix array é um vetor com os índices dos sufixos ordenados lexigraficamente.
vll suffix_array(string s, ll k = LLONG_MAX) {
s += ';';
ll n = s.size();
vll ps(n), rs(n), xs(n), cs(n);
csort(s, ps, 256);
vpll ys(n);
upd_eq_class(cs, ps, s);
for (ll mask = 1; mask < n && k > 0; mask *= 2, --k) {
rep(i, 0, n) {
rs[i] = ps[i] - mask + (ps[i] < mask) * n;
xs[i] = cs[rs[i]];
ys[i] = {cs[i], cs[i + mask - (i + mask >= n) * n]};
}
csort(xs, ps, cs[ps.back()] + 1);
rep(i, 0, n) ps[i] = rs[ps[i]];
upd_eq_class(cs, ps, ys);
}
ps.erase(ps.begin());
return (k == 0 ? cs : ps);
}template <typename T>
struct BIT2D {
ll n, m;
vector<vector<T>> bit;
BIT2D(ll h, ll w) : n(h), m(w), bit(n + 1, vector<T>(m + 1)) {}
// Adiciona v na posição (y, x), 1-indexado. O(log(N))
void add(ll y, ll x, T v) {
assert(0 < y && y <= n && 0 < x && x <= m)
for (; y <= n; y += y & -y)
for (ll i = x; i <= m; i += i & -i)
bit[y][i] += v;
}
T sum(ll y, ll x) {
T sum = 0;
for (; y > 0; y -= y & -y)
for (ll i = x; i > 0; i -= i & -i)
sum += bit[y][i];
return sum;
}
// Retorna soma no retângulo ly, hy, lx, hx. 1-indexado. O(log(N))
T sum(ll ly, ll lx, ll hy, ll hx) {
assert(0 < ly && ly <= hy && hy <= n && 0 < lx && lx <= hx && hx <= m);
return sum(hy, hx) - sum(hy, lx - 1) - sum(ly - 1, hx) + sum(ly - 1, lx - 1);
}
};struct DSU { // ~O(1)
vll parent, size;
DSU(ll n) : parent(n), size(n, 1) { iota(all(parent), 0); }
ll find(ll x) {
assert(0 <= x && x < parent.size());
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
bool merge(ll x, ll y) {
x = find(x), y = find(y);
if (x == y) return false;
if (size[x] > size[y]) swap(x, y);
parent[x] = y;
size[y] += size[x], size[x] = 0;
return true;
}
bool same(ll x, ll y) { return find(x) == find(y); }
};template <typename T, typename Op = function<T(T, T)>>
struct HLD {
Segtree<T> seg;
Op op;
bool values_on_edges;
vll idx, subtree, parent, head;
ll timer = 0;
// g é uma árvore. def é o valor padrão, f é a função de merge da segtree.
// Inicializa com upd_qry_path(u, u) ou se os valores forem nas arestas com
// upd_qry_path(u, v). O(N)
HLD(vvll& g, bool values_on_edges, T def, Op f)
: seg(g.size(), def, f), op(f), values_on_edges(values_on_edges) {
idx = subtree = parent = head = vll(g.size());
auto build = [&](auto&& self, ll u = 1, ll p = -1) -> void {
idx[u] = timer++, subtree[u] = 1, parent[u] = p;
for (ll& v : g[u]) if (v != p) {
head[v] = (v == g[u][0] ? head[u] : v);
self(self, v, u);
subtree[u] += subtree[v];
if (subtree[v] > subtree[g[u][0]] || g[u][0] == p)
swap(v, g[u][0]);
}
if (p == 0) {
timer = 0;
self(self, head[u] = u, -1);
}
};
build(build);
}
// Retorna f() do caminho entre u e v ou adiciona x se especificado. O(log²(N))
ll upd_qry_path(ll u, ll v, ll x = INT_MIN) {
assert(1 <= u && u < idx.size() && 1 <= v && v < idx.size());
if (idx[u] < idx[v]) swap(u, v);
if (head[u] == head[v]) return seg.upd_qry(idx[v] + values_on_edges, idx[u], x);
return op(seg.upd_qry(idx[head[u]], idx[u], x),
upd_qry_path(parent[head[u]], v, x));
}
// Retorna f() da subárvore de u ou adiciona x se especificado. O(log(N))
ll upd_qry_subtree(ll u, ll x = INT_MIN) {
assert(1 <= u && u < idx.size());
return seg.upd_qry(idx[u] + values_on_edges, idx[u] + subtree[u] - 1, x);
}
ll lca(ll u, ll v) { // O(log(N))
for (; head[u] != head[v]; u = parent[head[u]])
if (idx[u] < idx[v]) swap(u, v);
return idx[u] < idx[v] ? u : v;
}
};#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
// oset<int> = set, oset<int, int> = map.
// Muda less<> para less_equal<> para multiset/multimap. mas .lower_bound() troca
// com .upper_bound(), .erase() só funciona com iterador, .find() quebra.
// Os métodos são os mesmos do set/map, com dois novos:
// .find_by_order(i) que retorna o iterador pro elemento no índice i.
// .order_of_key(T), que retorna o índice onde o elemento T seria inserido.
// Se já tem, retorna o índice do primeiro. O(log(N))
template <typename T, typename S = null_type>
using oset = tree<T, S, less<>, rb_tree_tag, tree_order_statistics_node_update>;template <typename T, typename Op = function<T(T, T)>>
struct Segtree {
ll n;
T DEF;
vector<T> seg, lzy;
Op op;
// def é o valor padrão. f é a função de merge.
Segtree(ll sz, T def, Op f) : n(sz), DEF(def), seg(4 * n, DEF), lzy(4 * n), op(f) {}
// O(N)
void build(const vector<T>& xs, ll l = 0, ll r = -1, ll no = 1) {
if (r == -1) r = n - 1;
if (l == r) seg[no] = xs[l];
else {
ll m = (l + r) / 2;
build(xs, l, m, 2 * no);
build(xs, m + 1, r, 2 * no + 1);
seg[no] = op(seg[2 * no], seg[2 * no + 1]);
}
}
// Retorna f() do intervalo ou adiciona x se especificado.
// Intervalo [i, j]. O(log(N))
T upd_qry(ll i, ll j, T x = LLONG_MIN, ll l = 0, ll r = -1, ll no = 1) {
assert(0 <= i && i <= j && j < n);
if (r == -1) r = n - 1;
if (lzy[no]) unlazy(l, r, no);
if (j < l || i > r) return DEF;
if (i <= l && r <= j) {
if (x != LLONG_MIN) {
lzy[no] += x;
unlazy(l, r, no);
}
return seg[no];
}
ll m = (l + r) / 2;
T q = op(upd_qry(i, j, x, l, m, 2 * no),
upd_qry(i, j, x, m + 1, r, 2 * no + 1));
seg[no] = op(seg[2 * no], seg[2 * no + 1]);
return q;
}
private:
void unlazy(ll l, ll r, ll no) {
if (seg[no] == DEF) seg[no] = 0;
seg[no] += (r - l + 1) * lzy[no]; // Soma
// seg[no] += lzy[no]; // Min/max
if (l < r) {
lzy[2 * no] += lzy[no];
lzy[2 * no + 1] += lzy[no];
}
lzy[no] = 0;
}
};// Retorna o primeiro índice à direita que é maior que x no intervalo.
// Isso é um método da segtree e a função de merge deve ser max().
// Retorna -1 se não tem elemento maior nesse intervalo.
// Intervalo [i, j]. O(log(N))
ll first_greater(ll i, ll j, T x, ll l = 0, ll r = -1, ll no = 1) {
assert(0 <= i && i <= j && j < n);
if (r == -1) r = n - 1;
if (j < l || i > r || seg[no] <= x) return -1;
if (l == r) return l;
ll m = (l + r) / 2;
ll left = first_greater(i, j, x, l, m, 2 * no);
if (left != -1) return left;
return first_greater(i, j, x, m + 1, r, 2 * no + 1);
}template <typename T>
struct Affine {
T mul = 1, add = 0;
Affine operator+=(const Affine& other) {
return *this = {mul * other.mul, add * other.mul + other.add};
}
operator bool() { return mul != 1 || add != 0; }
};
// dentro da seg
vector<Affine<T>> lzy;
// dentro do upd_qry
Affine<T> x = Affine<T>()
// dentro do unlazy
seg[no] = seg[no] * lzy[no].mul + (r - l + 1) * lzy[no].add;
lzy[no] = Affine<T>(); // em vez de = 0mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef char NT;
struct Node {
NT v, s;
ll w, sz = 1;
bool lazy_rev = false;
Node *l = nullptr, *r = nullptr;
Node(NT x) : v(x), s(x), w(rng()) {}
};
typedef Node* NP;
ll size(NP t) { return t ? t->sz : 0; }
ll sum(NP t) { return t ? t->s : 0; }
void unlazy(NP t) {
if (!t || !t->lazy_rev) return;
t->lazy_rev = false;
swap(t->l, t->r);
if (t->l) t->l->lazy_rev ^= true;
if (t->r) t->r->lazy_rev ^= true;
}
void lazy(NP t) {
if (!t) return;
unlazy(t->l), unlazy(t->r);
t->sz = size(t->l) + size(t->r) + 1;
t->s = sum(t->l) + sum(t->r) + t->v;
}
NP merge(NP l, NP r) {
NP t;
unlazy(l), unlazy(r);
if (!l || !r) t = l ? l : r;
else if (l->w > r->w) l->r = merge(l->r, r), t = l;
else r->l = merge(l, r->l), t = r;
lazy(t);
return t;
}
// Divide t em l: [0, i) e r: [val, )
void split(NP t, NP& l, NP& r, ll i) {
unlazy(t);
if (!t) l = r = nullptr;
else if (i > size(t->l)) split(t->r, t->r, r, i - size(t->l) - 1), l = t;
else split(t->l, l, t->l, i), r = t;
lazy(t);
}
// Printa a lista. O(N)
void print(NP t) {
unlazy(t);
if (!t) return;
print(t->l);
cout << t->v;
print(t->r);
}
struct Treap {
NP root = nullptr;
// Insere x no índice i. O(log(N))
void insert(ll i, NT x) {
NP l, r, no = new Node(x);
split(root, l, r, i);
root = merge(merge(l, no), r);
}
// Apaga elemento no índice i. O(log(N))
void erase(ll i) {
NP l, r;
split(root, l, r, i);
split(r, root, r, 1);
root = merge(l, r);
}
// Atualiza o intervalo [i, j) com a função f. O(log(N))
void upd(ll i, ll j, function<void(NP)> f) {
NP m, r;
split(root, root, m, i);
split(m, m, r, j - i + 1);
if (m) f(m);
root = merge(merge(root, m), r);
}
// Consulta o intervalo [i, j) com a função f. O(log(N))
template <typename R>
R query(ll i, ll j, function<R(NP)> f) {
NP m, r;
split(root, root, m, i);
split(m, m, r, j - i + 1);
assert(m);
R x = f(m);
root = merge(merge(root, m), r);
return x;
}
};struct WaveletTree {
ll n;
vvll wav;
// xs é o vetor comprimido. sz é a quantidade de elementos distintos em xs.
// Ordena xs no processo. O(Nlog(N))
WaveletTree(vll& xs, ll sz) : n(sz), wav(2 * n) {
auto build = [&](auto&& self, auto b, auto e, ll l, ll r, ll no) {
if (l == r) return;
ll m = (l + r) / 2, i = 0;
wav[no].resize(e - b + 1);
for (auto it = b; it != e; ++it, ++i)
wav[no][i + 1] = wav[no][i] + (*it <= m);
auto p = stable_partition(b, e, [m](ll x) { return x <= m; });
self(self, b, p, l, m, 2 * no);
self(self, p, e, m + 1, r, 2 * no + 1);
};
build(build, all(xs), 0, n - 1, 1);
}
// Retorna o k-ésimo menor elemento em [i, j]. 1-indexado. O(log(N))
ll kth(ll i, ll j, ll k) {
assert(0 <= i && i <= j && j < (ll)wav[1].size() && k > 0);
++j;
ll l = 0, r = n - 1, no = 1;
while (l != r) {
ll m = (l + r) / 2;
ll leqm_l = wav[no][i], leqm_r = wav[no][j];
no *= 2;
if (k <= leqm_r - leqm_l) i = leqm_l, j = leqm_r, r = m;
else k -= leqm_r - leqm_l, i -= leqm_l, j -= leqm_r, l = m + 1, ++no;
}
return l;
}
// Retorna a quantidade de elementos menores ou igual que x em [i, j].
// x é o valor comprimido. O(log(N))
ll leq(ll i, ll j, ll x) {
assert(0 <= i && i <= j && j < (ll)wav[1].size() && 0 <= x && x < n);
++j;
ll l = 0, r = n - 1, lx = 0, no = 1;
while (l != r) {
ll m = (l + r) / 2;
ll leqm_l = wav[no][i], leqm_r = wav[no][j];
no *= 2;
if (x <= m) i = leqm_l, j = leqm_r, r = m;
else i -= leqm_l, j -= leqm_r, l = m + 1, lx += leqm_r - leqm_l, ++no;
}
return j - i + lx;
}
};enum Position { IN, ON, OUT };
template <typename T>
struct Circle {
pair<T, T> C;
T r;
// Origem e raio.
Circle(const pair<T, T>& P, T r) : C(P), r(r) {}
double area() { return acos(-1.0) * r * r; }
double perimeter() { return 2.0 * acos(-1.0) * r; }
double arc(double rad) { return rad * r; }
double chord(double rad) { return 2.0 * r * sin(rad / 2.0); }
double sector(double rad) { return (rad * r * r) / 2.0; }
double segment(double rad) {
double c = chord(rad);
double s = (r + r + c) / 2.0;
double t = sqrt(s) * sqrt(s - r) * sqrt(s - r) * sqrt(s - c);
return sector(rad) - t;
}
Position position(const pair<T, T>& P) {
double d = dist(P, C);
return equals(d, r) ? ON : (d < r ? IN : OUT);
}
vector<pair<T, T>> intersection(const Circle& c) {
double d = dist(c.C, C);
// Sem interseção ou círculos iguais.
if (d > c.r + r || d < abs(c.r - r) || (equals(d, 0) && equals(c.r, r)))
return {};
double a = (c.r * c.r - r * r + d * d) / (2.0 * d);
double h = sqrt(c.r * c.r - a * a);
double x = c.C.x + (a / d) * (C.x - c.C.x);
double y = c.C.y + (a / d) * (C.y - c.C.y);
pd p1, p2;
p1.x = x + (h / d) * (C.y - c.C.y);
p1.y = y - (h / d) * (C.x - c.C.x);
p2.x = x - (h / d) * (C.y - c.C.y);
p2.y = y + (h / d) * (C.x - c.C.x);
return p1 == p2 ? vector<pair<T, T>> { p1 } : vector<pair<T, T>> { p1, p2 };
}
vector<pd> intersection(pair<T, T> P, pair<T, T> Q) {
P.x -= C.x, P.y -= C.y, Q.x -= C.x, Q.y -= C.y;
double a(P.y - Q.y), b(Q.x - P.x), c(P.x * Q.y - Q.x * P.y);
double x0 = -a * c / (a * a + b * b), y0 = -b * c / (a * a + b * b);
if (c*c > r*r * (a*a + b*b) + 1e-9) return {};
if (equals(c*c, r*r * (a*a + b*b))) return { {x0, y0} };
double d = r * r - c * c / (a * a + b * b);
double mult = sqrt(d / (a * a + b * b));
double ax = x0 + b * mult + C.x;
double bx = x0 - b * mult + C.x;
double ay = y0 - a * mult + C.y;
double by = y0 + a * mult + C.y;
return { {ax, ay}, {bx, by} };
}
// Pontos de tangência olhando da origem.
pair<pd, pd> tan_points() {
double b = hypot(C.x, C.y), th = acos(r / b);
double d = atan2(-C.y, -C.x), d1 = d + th, d2 = d - th;
return { {C.x + r * cos(d1), C.y + r * sin(d1)},
{C.x + r * cos(d2), C.y + r * sin(d2)} };
}
static Circle<double> from3(const pair<T, T>& P, const pair<T, T>& Q,
const pair<T, T>& R) {
T a = 2 * (Q.x - P.x), b = 2 * (Q.y - P.y);
T c = 2 * (R.x - P.x), d = 2 * (R.y - P.y);
double det = a * d - b * c;
// Pontos colineares
if (equals(det, 0)) return { {0, 0}, 0 };
T k1 = (Q.x * Q.x + Q.y * Q.y) - (P.x * P.x + P.y * P.y);
T k2 = (R.x * R.x + R.y * R.y) - (P.x * P.x + P.y * P.y);
double cx = (k1 * d - k2 * b) / det;
double cy = (a * k2 - c * k1) / det;
return { {cx, cy}, dist(P, {cx, cy}) };
}
// Menor círculo em volta desses pontos. O(N)
static Circle<double> mec(vector<pair<T, T>>& PS) {
random_shuffle(all(PS));
Circle<double> c(PS[0], 0);
rep(i, 0, PS.size()) {
if (c.position(PS[i]) != OUT) continue;
c = {PS[i], 0};
rep(j, 0, i) {
if (c.position(PS[j]) != OUT) continue;
c = {
{(PS[i].x + PS[j].x) / 2.0, (PS[i].y + PS[j].y) / 2.0},
dist(PS[i], PS[j]) / 2.0
};
rep(k, 0, j)
if (c.position(PS[k]) == OUT)
c = from3(PS[i], PS[j], PS[k]);
}
}
return c;
}
};template <typename T>
struct Polygon {
vector<pair<T, T>> vs;
ll n;
// Pontos ordenados no sentido anti-horário.
Polygon(const vector<pair<T, T>>& PS) : vs(PS), n(vs.size()) { vs.eb(vs.front()); }
bool convex() { // O(N)
if (n < 3) return false;
ll P = 0, N = 0, Z = 0;
rep(i, 0, n) {
auto d = D(vs[i], vs[(i + 1) % n], vs[(i + 2) % n]);
d ? (d > 0 ? ++P : ++N) : ++Z;
}
return P == 0 || N == 0;
}
// Se pontos inteiros retorna 2*area. O(N)
T area() {
T a = 0;
rep(i, 0, n) a += vs[i].x * vs[i + 1].y - vs[i + 1].x * vs[i].y;
if (is_floating_point_v<T>) return 0.5 * abs(a);
return abs(a);
}
double perimeter() { // O(N)
double P = 0;
rep(i, 0, n) P += dist(vs[i], vs[i + 1]);
return P;
}
// Não considera na borda do polígono. O(N)
bool contains(const pair<T, T>& P) {
if (n < 3) return false;
bool in = false;
rep(i, 0, n) {
if (((vs[i].y > P.y) != (vs[i + 1].y > P.y)) &&
(P.x < (vs[i + 1].x - vs[i].x) * (P.y - vs[i].y) / (double)(vs[i + 1].y - vs[i].y) + vs[i].x))
in = !in;
}
return in;
}
// Retorna um dos polígonos gerado pelo corte na linha PQ. O(N)
Polygon cut(const pair<T, T>& P, const pair<T, T>& Q) {
vector<pair<T, T>> points;
double EPS = 1e-9;
rep(i, 0, n) {
auto d1 = D(P, Q, vs[i]), d2 = D(P, Q, vs[i + 1]);
if (d1 > -EPS) points.eb(vs[i]);
if (d1 * d2 < -EPS)
points.eb(intersection(vs[i], vs[i + 1], P, Q));
}
return { points };
}
// Apenas para polígono regular. O(1)
double circumradius() {
double s = dist(vs[0], vs[1]);
return (s / 2.0) * (1.0 / sin(acos(-1.0) / n));
}
// Apenas para polígono regular. O(1)
double apothem() {
double s = dist(vs[0], vs[1]);
return (s / 2.0) * (1.0 / tan(acos(-1.0) / n));
}
private:
// Interseção entre retas. O(1)
pair<T, T> intersection(const pair<T, T>& P, const pair<T, T>& Q,
const pair<T, T>& R, const pair<T, T>& S) {
T a = S.y - R.y, b = R.x - S.x, c = S.x * R.y - R.x * S.y;
T u = abs(a * P.x + b * P.y + c), v = abs(a * Q.x + b * Q.y + c);
return {(P.x * v + Q.x * u) / (u + v), (P.y * v + Q.y * u) / (u + v)};
}
};// Reta com coeficientes normalizados.
template <typename T>
struct Line {
T a, b, c;
Line(const pair<T, T>& P, const pair<T, T>& Q)
: a(P.y - Q.y), b(Q.x - P.x), c(P.x * Q.y - Q.x * P.y) {
if constexpr (is_floating_point_v<T>) {
if (abs(a) > abs(b)) b /= a, c /= a, a = 1;
else a /= b, c /= b, b = 1;
}
else {
if (a < 0 || (a == 0 && b < 0)) a *= -1, b *= -1, c *= -1;
T gcd_abc = gcd(a, gcd(b, c));
a /= gcd_abc, b /= gcd_abc, c /= gcd_abc;
}
}
bool contains(const pair<T, T>& P) { return equals(a * P.x + b * P.y + c, 0); }
bool parallel(const Line& r) {
T det = a * r.b - b * r.a;
return equals(det, 0);
}
bool orthogonal(const Line& r) { return equals(a * r.a + b * r.b, 0); }
pd intersection(const Line& r) {
double det = r.a * b - r.b * a;
// Retas iguais ou paralelas.
if (equals(det, 0)) return {};
double x = (-r.c * b + c * r.b) / det;
double y = (-c * r.a + r.c * a) / det;
return {x, y};
}
double dist(const pair<T, T>& P) {
return abs(a * P.x + b * P.y + c) / hypot(a, b);
}
// Ponto mais próximo de P na reta. O(1)
pd closest(const pair<T, T>& P) {
double den = a * a + b * b;
double x = (b * (b * P.x - a * P.y) - a * c) / den;
double y = (a * (-b * P.x + a * P.y) - b * c) / den;
return {x, y};
}
bool operator==(const Line& r) {
return equals(a, r.a) && equals(b, r.b) && equals(c, r.c);
}
};template <typename T>
struct Segment {
pair<T, T> A, B;
Segment(const pair<T, T>& P, const pair<T, T>& Q) : A(P), B(Q) {}
bool contains(const pair<T, T>& P) const {
T xmin = min(A.x, B.x), xmax = max(A.x, B.x);
T ymin = min(A.y, B.y), ymax = max(A.y, B.y);
if (P.x < xmin || P.x > xmax || P.y < ymin || P.y > ymax) return false;
return equals((P.y - A.y) * (B.x - A.x), (P.x - A.x) * (B.y - A.y));
}
bool intersect(const Segment& r) {
T d1 = D(A, B, r.A), d2 = D(A, B, r.B);
T d3 = D(r.A, r.B, A), d4 = D(r.A, r.B, B);
d1 /= d1 ? abs(d1) : 1, d2 /= d2 ? abs(d2) : 1;
d3 /= d3 ? abs(d3) : 1, d4 /= d4 ? abs(d4) : 1;
if ((equals(d1, 0) && contains(r.A)) || (equals(d2, 0) && contains(r.B)))
return true;
if ((equals(d3, 0) && r.contains(A)) || (equals(d4, 0) && r.contains(B)))
return true;
return (d1 * d2 < 0) && (d3 * d4 < 0);
}
// Ponto mais próximo de P no segmento. O(1)
pair<T, T> closest(const pair<T, T>& P) {
Line<T> r(A, B);
pd Q = r.closest(P);
double distA = dist(A, P), distB = dist(B, P);
if (this->contains(Q)) return Q;
if (distA <= distB) return A;
return B;
}
};enum Class { EQUILATERAL, ISOSCELES, SCALENE };
enum Angles { RIGHT, ACUTE, OBTUSE };
template <typename T>
struct Triangle {
pair<T, T> A, B, C;
T a, b, c;
Triangle(pair<T, T> P, pair<T, T> Q, pair<T, T> R)
: A(P), B(Q), C(R), a(dist(A, B)), b(dist(B, C)), c(dist(C, A)) {}
double perimeter() { return a + b + c; }
double inradius() { return (2 * area()) / perimeter(); }
double circumradius() { return (a * b * c) / (4.0 * area()); }
// Se pontos inteiros retorna 2*area. O(1)
T area() {
T det = (A.x * B.y + A.y * C.x + B.x * C.y) -
(C.x * B.y + C.y * A.x + B.x * A.y);
if (is_floating_point_v<T>) return 0.5 * abs(det);
return abs(det);
}
Class class_by_sides() {
if (equals(a, b) && equals(b, c)) return EQUILATERAL;
if (equals(a, b) || equals(a, c) || equals(b, c)) return ISOSCELES;
return SCALENE;
}
Angles class_by_angles() {
double alpha = acos((a * a - b * b - c * c) / (-2.0 * b * c));
double beta = acos((b * b - a * a - c * c) / (-2.0 * a * c));
double gamma = acos((c * c - a * a - b * b) / (-2.0 * a * b));
double right = acos(-1.0) / 2.0;
if (equals(alpha, right) || equals(beta, right) || equals(gamma, right))
return RIGHT;
if (alpha > right || beta > right || gamma > right) return OBTUSE;
return ACUTE;
}
// Ponto de interseção entre as medianas. O(1)
pd barycenter() {
double x = (A.x + B.x + C.x) / 3.0;
double y = (A.y + B.y + C.y) / 3.0;
return {x, y};
}
pd circumcenter() {
double D = 2 * (A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y));
T A2 = A.x * A.x + A.y * A.y, B2 = B.x * B.x + B.y * B.y,
C2 = C.x * C.x + C.y * C.y;
double x = (A2 * (B.y - C.y) + B2 * (C.y - A.y) + C2 * (A.y - B.y)) / D;
double y = (A2 * (C.x - B.x) + B2 * (A.x - C.x) + C2 * (B.x - A.x)) / D;
return {x, y};
}
pd incenter() {
double P = perimeter();
double x = (a * A.x + b * B.x + c * C.x) / P;
double y = (a * A.y + b * B.y + c * C.y) / P;
return {x, y};
}
// Ponto de interseção entre as alturas. O(1)
pd orthocenter() {
Line<T> r(A, B), s(A, C);
Line<T> u{r.b, -r.a, -(C.x * r.b - C.y * r.a)};
Line<T> v{s.b, -s.a, -(B.x * s.b - B.y * s.a)};
double det = u.a * v.b - u.b * v.a;
double x = (-u.c * v.b + v.c * u.b) / det;
double y = (-v.c * u.a + u.c * v.a) / det;
return {x, y};
}
};// Acelera dp de espaço constante.
// A matriz terá os coeficientes da dp.
// ndp[i] += dp[j] * m[i][j].
template <typename T>
struct Matrix {
vector<vector<T>> mat;
Matrix(const vector<vector<T>>& matrix) : mat(matrix) {}
Matrix(ll n, ll m, ll x = 0) : mat(n, vector<T>(m)) {
if (n == m) rep(i, 0, n) mat[i][i] = x;
}
vector<T>& operator[](ll i) { return mat[i]; }
ll size() const { return mat.size(); }
Matrix operator*(const Matrix& other) const { // O(N³)
ll N = mat.size(), K = mat[0].size(), M = other[0].size();
assert(other.size() == K);
Matrix res(N, M);
rep(i, 0, N) rep(k, 0, K) rep(j, 0, M)
res[i][j] += mat[i][k] * other[k][j];
return res;
}
};struct AhoCorasick {
static constexpr ll MAXN = 5e5 + 1;
ll n, m;
vvll to, go, idx;
vll mark, qnt, p, pc, link, exit;
AhoCorasick() : n(0), m(0), to(MAXN, vll(26)), go(MAXN, vll(26, -1)), idx(MAXN), mark(MAXN),
qnt(MAXN), p(MAXN), pc(MAXN), link(MAXN, -1), exit(MAXN, -1) {}
void insert(const string& s) { // O(N)
ll u = 0;
for (char ch : s) {
ll c = ch - 'a';
ll& v = to[u][c];
if (!v) v = ++n, p[v] = u, pc[v] = c;
u = v, ++qnt[u];
}
++mark[u], ++qnt[0], idx[u].eb(m++);
}
vpll occur(const string& s) { // O(N + Matches)
vll occ(n + 1);
vpll res;
ll u = 0;
for (char ch : s) {
u = go_to(u, ch - 'a');
for (ll v = u; v != 0; v = get_exit(v)) ++occ[v];
}
rep(v, 0, n + 1) for (auto i : idx[v])
if (occ[v])
res.eb(i, occ[v]);
return res;
}
ll get_link(ll u) {
if (link[u] != -1) return link[u];
if (u == 0 || p[u] == 0) return link[u] = 0;
return link[u] = go_to(get_link(p[u]), pc[u]);
}
ll go_to(ll u, ll c) {
if (go[u][c] != -1) return go[u][c];
if (to[u][c]) return go[u][c] = to[u][c];
return go[u][c] = u == 0 ? 0 : go_to(get_link(u), c);
}
ll get_exit(ll u) {
ll v = get_link(u);
if (exit[u] != -1) return exit[u];
return exit[u] = (v == 0 || mark[v]) ? v : get_exit(v);
}
};constexpr ll M1 = (ll)1e9 + 7, M2 = (ll)1e9 + 9;
#define H pll
#define x first
#define y second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
H P(
uniform_int_distribution<ll>(256, 1e9)(rng),
uniform_int_distribution<ll>(256, 1e9)(rng)
);
ll sum(ll a, ll b, ll m) { return (a += b) >= m ? a - m : a; };
ll sub(ll a, ll b, ll m) { return (a -= b) < 0 ? a + m : a; };
H operator*(H a, H b) { return {a.x * b.x % M1, a.y * b.y % M2}; }
H operator+(H a, H b) { return {sum(a.x, b.x, M1), sum(a.y, b.y, M2)}; }
H operator-(H a, H b) { return {sub(a.x, b.x, M1), sub(a.y, b.y, M2)}; }
template <typename T>
struct Hash {
ll n;
// Segtree<H> ps;
vector<H> ps, pw;
// Dá para fazer updates usando segtree, partes comentadas.
// p^n + p^n-1 + ... + p^0. O(N)
Hash(const T& s) : n(s.size()), ps(n + 1), pw(n + 1) {
pw[0] = {1, 1};
rep(i, 0, n) {
ps[i + 1] = ps[i] * P + H(s[i], s[i]);
pw[i + 1] = pw[i] * P;
}
// vector<H> ps_(n);
// rep(i, 0, n) {
// ll v = s[i] - 'a' + 1;
// ps_[i] = pw[n - i - 1] * H(v, v);
// }
// ps.build(ps_);
}
// O(log(N))
// void set(ll i, char c) {
// ps.upd_qry(i, i, pw[n - i - 1] * H(c, c));
// }
H operator()(ll i, ll j) {
assert(0 <= i && i <= j && j < n);
return ps[j + 1] - ps[i] * pw[j + 1 - i];
// return ps.upd_qry(i, j) * pw[i];
}
};template <typename T>
struct HashInv {
Hash<T> h;
HashInv(T s) : h("") { reverse(all(s)), h = Hash<T>(s); }
H operator()(ll i, ll j) { return h(h.n - j - 1, h.n - i - 1); }
};struct SuffixAutomaton {
vvll to; // Se MLE use vector<map<ll, ll>>
vll len, fpos, lnk, cnt, rcnt, dcnt;
ll sz = 0, last = 0, n = 0, alpha = 26;
SuffixAutomaton() { make_node(); }
void insert(const string& s) { // O(N)
last = 0;
for (auto c : s) add(c - 'a');
}
void finalize() {
vll order(sz - 1);
iota(all(order), 1);
sort(all(order), [&](ll a, ll b) { return len[a] > len[b]; });
for (ll i : order) cnt[lnk[i]] += cnt[i];
// Pré-processamento para kth_sub e kth_dsub
dfs(0);
}
pll count_and_first(const string &t) { // O(M)
ll u = 0;
for (auto c : t) {
ll v = to[u][c - 'a'];
if (!v) return {0, -1};
u = v;
}
return {cnt[u], fpos[u] - t.size() + 1};
}
// Quantidade de substrings distintas por tamanho. O(N)
vll dsubs_by_size() {
vll delta(n);
rep(i, 1, sz) {
ll mnlen = len[lnk[i]];
++delta[mnlen];
if (len[i] < n) --delta[len[i]];
}
rep(i, 1, n) delta[i] += delta[i - 1];
return delta;
}
// k-ésima substring lexograficamente. Começa do 0. O(N)
string kth_sub(ll k) {
k += cnt[0];
string res;
ll u = 0;
while (k >= cnt[u]) {
k -= cnt[u];
rep(i, 0, alpha) {
ll v = to[u][i];
if (!v) continue;
if (rcnt[v] > k) {
res += i + 'a', u = v;
break;
}
k -= rcnt[v];
}
}
return res;
}
// k-ésima substring distinta lexograficamente. Começa do 0. O(N)
string kth_dsub(ll k) {
string res;
ll u = 0;
while (k >= 0) {
rep(i, 0, alpha) {
ll v = to[u][i];
if (!v) continue;
if (dcnt[v] > k) {
res += i + 'a', --k, u = v;
break;
}
k -= dcnt[v];
}
}
return res;
}
private:
ll make_node(ll LEN = 0, ll FPOS = -1, ll LNK = -1, ll CNT = 0) {
to.eb(vll(alpha)), rcnt.eb(0), dcnt.eb(0);
len.eb(LEN), fpos.eb(FPOS), lnk.eb(LNK), cnt.eb(CNT);
return sz++;
}
void add(ll c) {
++n;
ll p = last; // Se as strings tem peso, cnt = 0, marca depois.
ll u = make_node(len[p] + 1, len[p], 0, 1);
last = u;
for (; p != -1 && !to[p][c]; p = lnk[p]) to[p][c] = u;
if (p == -1) lnk[u] = 0;
else {
ll v = to[p][c];
if (len[p] + 1 == len[v]) lnk[u] = v;
else {
ll clone = make_node(len[p] + 1, fpos[v], lnk[v]);
to[clone] = to[v];
lnk[u] = lnk[v] = clone;
for (; p != -1 && to[p][c] == v; p = lnk[p])
to[p][c] = clone;
}
}
}
void dfs(ll u) { // Para kth_sub and kth_dsub
dcnt[u] = 1, rcnt[u] = cnt[u];
rep(i, 0, alpha) {
ll v = to[u][i];
if (!v) continue;
if (!dcnt[v]) dfs(v);
dcnt[u] += dcnt[v];
rcnt[u] += rcnt[v];
}
}
};struct Trie {
static constexpr ll MAXN = 5e5;
ll n;
vvll to;
// term: Quantidade de strings que terminam nesse vértice.
// qnt: Quantidade de strings que passam nesse vértice.
vll term, qnt;
Trie() : n(0), to(MAXN + 1, vll(26)), term(MAXN + 1), qnt(MAXN + 1) {}
void insert(const string& s) { // O(N)
ll u = 0;
for (auto c : s) {
ll& v = to[u][c - 'a'];
if (!v) v = ++n;
u = v, ++qnt[u];
}
++term[u], ++qnt[0];
}
void erase(const string& s) { // O(N)
ll u = 0;
for (char c : s) {
ll& v = to[u][c - 'a'];
u = v, --qnt[u];
if (!qnt[u]) v = 0;
}
--term[u], --qnt[0];
}
void dfs(ll u) {
rep(i, 0, 26) {
ll v = to[u][i];
if (v) {
if (term[v]) cout << "\e[31m";
cout << (char)(i + 'a') << " \e[m";
dfs(to[u][i]);
}
}
}
};struct BitTrie {
static constexpr ll MAXN = 5e6;
ll n;
vvll to;
vll qnt;
BitTrie() : n(0), to(MAXN + 1, vll(2)), qnt(MAXN + 1) {}
void insert(ll x) {
ll u = 0;
rep(i, 0, 32) {
ll& v = to[u][(x >> i) & 1];
if (!v) v = ++n;
u = v, ++qnt[u];
}
++qnt[0];
}
void erase(ll x) {
ll u = 0;
rep(i, 0, 32) {
ll& v = to[u][(x >> i) & 1];
u = v, --qnt[u];
if (!qnt[u]) v = 0;
}
--qnt[0];
}
ll mx_or(ll x) {
ll u = 0;
ll res = 0;
rep(i, 0, 32) {
ll desired = !((x >> i) & 1);
ll v = to[u][desired];
if (v) {
u = v;
res |= desired << i;
}
else {
u = to[u][!desired];
res |= (!desired) << i;
}
}
return res;
}
};template <typename T>
struct Compressed {
Compressed(const vector<T>& xs) : cs(xs) {
sort(all(cs));
cs.erase(unique(all(cs)), cs.end());
}
ll operator[](T x) { return lower_bound(all(cs), x) - cs.begin(); }
T ret(ll c) { return cs[c]; }
ll size() { return cs.size(); }
vector<T> cs;
};template <typename T, typename Op = function<T(T, T)>>
struct AggQueue {
stack<pair<T, T>> in, out;
Op op;
// f é uma função (não precisa ter inverso).
AggQueue(Op f) : op(f) {}
// Retorna f() dos elementos na fila. O(1)
T query() {
if (in.empty()) return out.top().y;
if (out.empty()) return in.top().y;
return op(in.top().y, out.top().y);
}
void insert(T x, bool is_user_insertion = true) {
auto& st = is_user_insertion ? in : out;
T cur = st.empty() ? x : op(st.top().y, x);
st.emplace(x, cur);
}
void pop() {
if (out.empty()) while (!in.empty())
insert(in.top().x, false), in.pop();
out.pop();
}
};struct Mex { // O(log(N))
vll hist;
set<ll> missing;
Mex(ll n) : hist(n) { rep(i, 0, n + 1) missing.emplace(i); }
ll mex() { return *missing.begin(); }
void insert(ll x) { if (x < hist.size() && ++hist[x] == 1) missing.erase(x); }
void erase(ll x) { if (x < hist.size() && --hist[x] == 0) missing.emplace(x); }
};template<typename T>
struct VeniceSet { // O(log(N))
map<T, ll> xs;
T delta = 0;
void emplace(T x) { xs[x + delta]++; }
void add_all(T x) { delta -= x; }
ll count(T x) {
if (xs.find(x + delta) != xs.end()) return xs[x + delta];
return 0;
}
T pop() {
auto m = xs.begin()->first - delta;
if (--xs[m] == 0) xs.erase(m);
return m;
}
};constexpr ll M1 = (ll)1e9 + 7;
constexpr ll M2 = (ll)998244353;
template <ll M = M1>
struct Mi {
ll v;
Mi(ll x = 0) : v(x) {
if (v >= M || v < -M) v %= M;
if (v < 0) v += M;
}
explicit operator ll() const { return v; }
Mi& operator+=(Mi o) { if ((v += o.v) >= M) v -= M; return *this; }
Mi& operator-=(Mi o) { if ((v -= o.v) < 0) v += M; return *this; }
Mi& operator*=(Mi o) { v = v * o.v % M; return *this; }
Mi& operator/=(Mi o) { return *this *= pot(o, M - 2); }
friend Mi operator+(Mi a, Mi b) { return a += b; }
friend Mi operator-(Mi a, Mi b) { return a -= b; }
friend Mi operator*(Mi a, Mi b) { return a *= b; }
friend Mi operator/(Mi a, Mi b) { return a /= b; }
friend ostream& operator<<(ostream& os, Mi a) { return os << a.v; }
};ll msb(ll x) { return x ? 63 - __builtin_clzll(x) : -1; }
ll lsb(ll x) { return x ? __builtin_ctzll(x) : -1; }ll ceilDiv(ll a, ll b) { assert(b != 0); return a/b+(a%b>0); }const ll MAXN = (ll)3e6, M = (ll)1e9 + 7;
array<ll, MAXN + 1> fac, inv, finv;
void init() {
if (fac[0]) return;
fac[0] = fac[1] = inv[1] = finv[0] = finv[1] = 1;
rep(i, 2, MAXN + 1) {
fac[i] = fac[i - 1] * i % M;
inv[i] = M - M / i * inv[M % i] % M;
finv[i] = finv[i - 1] * inv[i] % M;
}
}
ll nPr(ll n, ll k) {
init();
if (n < k || n * k < 0) return 0;
return fac[n] * finv[n - k] % M;
}
ll nCr(ll n, ll k) {
return nPr(n, k) * finv[k] % M;
}
template <typename T>
ll permrep(const map<T, ll>& hist) {
init();
ll den = 1, total = 0;
for (const auto& [k, v] : hist)
den = den * finv[v] % M, total += v;
return fac[total] * den % M;
}template <typename T, typename S>
bool equals(T a, S b) { return abs(a - b) < 1e-7; }
$a + b = (a \land b) + (a \lor b)$ .
$a + b = a \oplus b + 2 * (a \land b)$ .
$a \oplus b = \lnot(a \land b) \land (a \lor b)$ .
$S(n) = 0 \oplus 1 \oplus 2 \oplus ... \oplus n$ ;$S(n) = n \iff n = 0 \bmod 4$ ;$S(n) = 1 \iff n = 1 \bmod 4$ ;$S(n) = n + 1 \iff n = 2 \bmod 4$ ;$S(n) = 0 \iff n = 3 \bmod 4$ ;
Quantidade de pontos inteiros num segmento:
$gcd(abs(P.x - Q.x), abs(P.y - Q.y)) + 1$ .$P, Q$ são os pontos extremos do segmento.
Teorema de Pick: Seja
$A$ a área da treliça,$I$ a quantidade de pontos interiores com coordenadas inteiras e$B$ os pontos da borda com coordenadas inteiras. Então,$A = I + \frac{B}{2} - 1$ e$I = \frac{2A + 2 - B}{2}$ .
Distância de Chebyshev:
$dist(P, Q) = max(P.x - Q.x, P.y - Q.y)$ .$P, Q$ são dois pontos.
Manhattan para Chebyshev: Feita a transformação
$(x, y) \to (x + y, x - y)$ , temos uma equivalência entre as duas distâncias, podemos agora tratar$x$ e$y$ separadamente, fazer bounding boxes, entre outros...
Para contar paralelogramos em um conjunto de pontos podemos marcar o centro de cada segmento, coincidências entre dois centros formam um paralelogramo.
Quantidade de divisores de um número:
$\prod (a_i + 1)$ .$a_i$ é o expoente do$i$ -ésimo fator primo.
Soma dos divisores de um número:
$\prod \frac{p_i^{a_i + 1} - 1}{p_i - 1}$ .$a_i$ é o expoente do$i$ -ésimo fator primo$p_i$ .
Produto dos divisores de um número
$x$ :$x^{\frac{qd(x)}{2}}$ .$qd(x)$ é a quantidade de divisores dele.
Maior quantidade de divisores de um número:
$< 10^3$ é$32$ ;$< 10^6$ é$240$ ;$< 10^9$ é$1344$ ;$< 10^{18}$ é$107520$ .
Maior diferença entre dois primos consecutivos:
$< 10^7$ é$180$ ;$< 10^{18}$ é$1476$ . (Podemos concluir que a partir de um número arbitrário a distância para o coprimo mais próximo é bem menor que esse valor).
Maior quantidade de primos na fatoração de um número:
$< 10^3$ é$9$ ;$< 10^6$ é$19$ .
$gcd(a, b) = gcd(a, a - b)$ ,$gcd(a, b, c) = gcd(a, a - b, a - c)$ , segue o padrão.
$gcd(a, b) \leq a - b$ , considere$a \gt b$ . É igual exatamente quando$a - b$ é divisor de$a$ .
Para calcular o
$lcm$ de um conjunto de números com módulo, podemos fatorizar cada um, cada primo gerado vai ter uma potência que vai ser a maior, o produto desses primos elevados à essa potência será o$lcm$ , se queremos módulo basta fazer nessas operações.
Divisibilidade por
$3$ : soma dos algarismos divisível por$3$ .
Divisibilidade por
$4$ : número formado pelos dois últimos algarismos, divisível por$4$ .
Divisibilidade por
$6$ : se divisível por$2$ e$3$ .
Divisibilidade por
$7$ : soma alternada de blocos de três algarismos, divisível por$7$ .
Divisibilidade por
$8$ : número formado pelos três últimos algarismos, divisível por$8$ .
Divisibilidade por
$9$ : soma dos algarismos divisível por$9$ .
Divisibilidade por
$11$ : soma alternada dos algarismos divisível por$11$ .
Divisibilidade por
$12$ : se divisível por$3$ e$4$ .
Soma da progressão geométrica (
$\sum_{k=1}^n x^k$ é uma progressão geométrica):$\frac{a_n * r - a_1}{r - 1}$ .
Soma de progressão geométrica da forma:
$\sum_{k=1}^n kx^k = \frac {x(1-x^n)}{(1-x)^2}-\frac{nx^{n+1}}{1-x}$ , parte da fórmula normal, multiplica por x e subtrai.
Soma de termos ao quadrado:
$1^2 + 2^2 + ... + n^2 = \frac{n(n + 1)(2n + 1)}{6}$ .
Ao realizar operações com aritmética modular a paridade (sem módulo) não é preservada, se quer saber a paridade na soma vai checando a paridade do que está sendo somado e do número, na multiplicação e divisão conte e mantenha a quantidade de fatores iguais a dois.
Teorema de Euler:
$a^{\varphi(m)} = 1 \bmod m$ . Se$m$ é primo se reduz á$a^{m - 1} = 1 \bmod m$ .
$a^{b^c} \bmod m = a^{b^c \bmod \varphi(m)} \bmod m$ . Se$m$ é primo se reduz á$a^{b^c} \bmod m = a^{b^c \bmod (m - 1)} \bmod m$ .
$a^{\varphi(m) - 1} = a^{-1} \bmod m$ , mas precisa da condição que$gcd(a, m) = 1$ .
Teorema de Wilson:
$(n - 1)! = -1 \bmod n$ . Dá para calcular$x! \bmod n$ se$n - x \leq 10^6$ pois$x! = -[(x+1)...(m-1)]^{-1} \bmod n$ .
$(a+b)^n = \binom{n}{0} a^n + \binom{n}{1} a^{n-1} b + \binom{n}{2} a^{n-2} b^2 + \cdots + \binom{n}{k} a^{n-k} b^k + \cdots + \binom{n}{n} b^n$
Soma da
$n$ -ésima linha do triângulo de Pascal:$2^n$ .
Soma da
$m$ -ésima coluna do triângulo de Pascal:$\binom{n + 1}{m + 1}$ .$n$ é a quantidade de linhas.
A quantidade de ímpares na
$𝑛$ −ésima linha do triângulo de Pascal:$2^𝑐$ .$𝑐$ é a quantidade de bits ligados na representação binária de$𝑛$ .
Números de Catalan
$C_n$ : representa a quantidade de expressões válidas com parênteses de tamanho$2n$ . Também são relacionados às árvores, existem$C_n$ árvores binárias de$n$ vértices e$C_n-1$ árvores de$n$ vértices (as árvores são caracterizadas por sua aparência).$C_n = \frac{\binom{2n}{n}}{n + 1}$ . A fórmula recursiva é$f(n) = \sum_{k=1}^n f(k-1) \times f(n-k)$ , se chegar nessa dp, pode usar Catalan.
Lema de Burnside: o número de combinações em que simétricos são considerados iguais é o somatório
$\frac{1}{n} \sum_{k=1}^{n} c(k)$ .$n$ é a quantidade de maneiras de mudar a posição de uma combinação e$c(k)$ é a quantidade de combinações que são consideradas iguais à primeira maneira na$k$ -ésima maneira.
$min(f, g) = \frac{f + g}{2} - \frac{|f - g|}{2}$ . Se estamos fazendo para vários valores, para lidar com o módulo, se temos$f$ fixo, tentamos lidar com os$g$ maiores que$f$ e com os menores que$f$ separadamente.
Sejam
$p$ e$q$ dois períodos de uma string$s$ . Se$p + q − lcm(p, q) \leq |s|$ , então$lcm(p, q)$ também é período de$s$ .
Relação entre bordas e períodos: A sequência
$|s| − |border(s)|, |s| − |border^2(s)|, ..., |s| − |border^k(s)|$ é a sequência crescente de todos os possíveis períodos de$s$ .
Princípio da inclusão e exclusão: a união de
$n$ conjuntos é a soma de todas as interseções de um número ímpar de conjuntos menos a soma de todas as interseções de um número par de conjuntos.
Regra de Warnsdorf: heurística para encontrar um caminho em que o cavalo passa por todas as casas uma única vez, sempre escolher o próximo movimento para a casa com o menor número de casas alcançáveis.
Para utilizar ordenação customizada em sets/maps:
set<ll, decltype([](ll a, ll b) { ... }).
Por padrão python faz operações com até
$4000$ dígitos, para aumentar:import sys sys.set_int_max_str_digits(1000001)
Dado um grafo a quantidade de vértices pesados é
$\sqrt{N}$ , vértices leves são aqueles com degrau$\leq \sqrt{N}$ .