Indian Institute of Technology - Madras

Three of a Kind
Kaustubh Miglani, Vinit Dhandharia, Aryan Reddy

ICPC World Finals 2022

April 18, 2024
1 Numerical 1 { #define ford(i,n) for(ll i = n-1;i >= 0;i--) #define pb
if (prev == root) push_back
{ #define ll long long int
Numerical (1) t = root; //#define mod 998244353
break; #define pi pair<int,int>
1.1 Algos }
prev = prev->failLink;
#define pll pair<ll,ll>
#define mp make_pair
AhoCor.cpp } #define fi first
Description: AhoCorasick d41d8c, 122 lines
cur->failLink = t; #define se second
// assign ouptutLink //#pragma GCC optimize(” unroll−loops ”) //#pragma GCC optimize(”
struct AhoCorasick if (!((cur->failLink->ids).empty())) O3”)
{ { //#pragma GCC target (”avx2”)
struct node cur->outputLink = cur->failLink;
{ }
char c; else ConvexHullTrick.cpp
vector<int> ids; { Description: Container where you can add lines of the form kx+m, and
map<char, node *> go; cur->outputLink = cur->failLink->outputLink; query maximum values at points x. Useful for dynamic programming (“con-
node *failLink; } vex hull trick”).
node *outputLink; q.push(cur); Time: O (log N ) d41d8c, 31 lines
node(char _c) }
{ struct Line {
} mutable ll k, m, p;
c = _c; }
failLink = NULL; bool operator<(const Line& o) const { return k < o.k; }
vector<int> getCnt(string s, int limit) bool operator<(ll x) const { return p < x; }
outputLink = NULL; {
} };
node *curState = root;
}; node *nxt;
node *root; struct LineContainer : multiset<Line, less<>> {
int sz = s.size(); // ( for doubles , use i nf = 1/.0 , div (a , b) = a/b)
vector<string> words; vector<int> res(words.size(), 0);
AhoCorasick(vector<string> _words) : words(_words) static const ll inf = LLONG_MAX;
for (int i = 0; i < sz; i++) ll div(ll a, ll b) { // floored division
{ {
root = new node(0); return a / b - ((a ^ b) < 0 && a % b); }
char c = s[i]; bool isect(iterator x, iterator y) {
int sz = words.size(); nxt = curState->go[c];
for (int i = 0; i < sz; i++) if (y == end()) return x->p = inf, 0;
if (nxt == NULL) if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
{ {
insert(words[i], i); else x->p = div(y->m - x->m, x->k - y->k);
if (curState != root) return x->p >= y->p;
} {
genLinks(); }
i--; void add(ll k, ll m) {
} }
void insert(string s, int ind) auto z = insert({k, m, 0}), y = z++, x = y;
curState = curState->failLink; while (isect(y, z)) z = erase(z);
{ }
node *cur = root; if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
else while ((y = x) != begin() && (--x)->p >= y->p)
for (char c : s) {
{ isect(x, erase(y));
curState = nxt; }
node *&nxt = cur->go[c]; }
if (nxt == NULL) ll query(ll x) {
for (int cid : curState->ids) assert(!empty());
nxt = new node(c); if (res[cid] < limit)
cur = nxt; auto l = *lower_bound(x);
res[cid]++; //cout<<l . k<<” ”<<l .m<<”HH\n”;
} node *curOutput = curState->outputLink;
cur->ids.push_back(ind); return l.k * x + l.m;
while (curOutput != NULL) }
} {
void genLinks() };
for (int cid : curOutput->ids)
{ {
queue<node *> q; if (res[cid] == limit) Convexhull.cpp
root->failLink = root; break; Description: Convex Hull
for (auto tmp : root->go) d41d8c, 52 lines
res[cid]++;
{ } struct ConvexHull
tmp.second->failLink = root; curOutput = curOutput->outputLink; {
q.push(tmp.second); } using pint = pair<int,int>;
} } vector<pint> points;
while (!q.empty()) return res; vector<pint> hull;
{ } int n;
node *tp = q.front(); }; long long area(pint a,pint b,pint c)
q.pop(); {
for (auto tmp : tp->go) long long area = 0;
{ AryanTemplate.cpp area = 1ll * (b.first - a.first) * (c.second - b.second
node *cur = tmp.second; Description: Aryan Template );
node *prev = tp; <bits/stdc++.h> d41d8c, 13 lines area -= 1ll * (c.first - b.first) * (b.second - a.
node *t; #define all(v) v.begin(),v.end() second);
// assign failLink #define allr(v) v.rbegin(),v.rend() return area;
while ((t = prev->failLink->go[tmp.fi]) == NULL) #define fori(i,n) for(ll i=0;i<n;i++) }
IIT Madras AhoCor AryanTemplate ConvexHullTrick Convexhull Dinic DSU EulerCircuit Extendedeuclid 2
ConvexHull(vector<pint> _points): points(_points),n(_points return e2.cap; DSU.cpp
.size()) } Description: DSU d41d8c, 19 lines
{ void addEdge(int a, int b, T _cap, T _rcap = 0)
sort(points.begin(),points.end()); { struct DSU
points.erase(unique(points.begin(),points.end()),points int sz1 = adj[a].size(); { // benq implementation
.end()); int sz2 = adj[b].size(); vector<int> e;
n = points.size(); adj[a].pb({b, sz2, _cap}); DSU(int N) { e = vector<int>(N, -1); }
if(n < 3) adj[b].pb({a, sz1, _rcap}); // get representive component ( uses path compression) int
{ assert(_cap >= 0 && _rcap >= 0); get ( int x) { return e [ x ] < 0 ? x : e [ x ] = get (e [ x ] ) ; }
hull = points; }; bool same_set(int a, int b) { return get(a) == get(b); }
return; vector<int> level; int size(int x) { return -e[get(x)]; }
} vector<int> ptr; bool unite(int x, int y)
for(int i = 0;i < n;i++) bool setUpLevel(int s, int t) // returns i f t reachable { // union by s i z e
{ from s x = get(x), y = get(y);
while(hull.size() > 1 && area(hull[hull.size()-2], { if (x == y)
hull.back(),points[i]) <= 0) hull.pop_back(); level.assign(n, 0); // l e v e l s return false;
hull.push_back(points[i]); start from 1 !!ptr.assign(n, 0); if (e[x] > e[y])
} queue<int> q({s}); swap(x, y);
int lower_length = hull.size(); level[s] = 1; e[x] += e[y];
for(int i = n-2;i >= 0;i--) while (!q.empty()) e[y] = x;
{ { return true;
while(hull.size() > lower_length && area(hull[hull. int x = q.front(); }
size()-2],hull.back(),points[i]) <= 0) hull. q.pop(); };
pop_back(); int sz = adj[x].size();
hull.push_back(points[i]); for (int i = 0; i < sz; i++)
} { EulerCircuit.cpp
hull.pop_back(); int cap = adj[x][i].cap; Description: Euler circuit d41d8c, 18 lines
} int to = adj[x][i].to; multiset<int> adj[500005];
long long getTwiceAreaofHull() if (cap && !level[to]) vector<int> finale;
{ { void DFS(int u)
int sz = hull.size(); q.push(to); {
long long ans = 0; level[to] = level[x] + 1; vector<int> g;
for(int i =0;i < sz;i++) } while (!adj[u].empty())
{ } {
int j = (i+1)%sz; } auto x = *(adj[u].begin());
long long a1 = hull[i].first; return bool(level[t]); if (adj[u].find(x) == adj[u].end())
long long b1 = hull[i].second; } {
long long a2 = hull[j].first; T dfs(int x, int t, T curFlow) continue;
long long b2 = hull[j].second; { }
ans += a1 * b2 - a2 * b1; if (x == t) adj[u].erase(adj[u].find(x));
} return curFlow; adj[x].erase(adj[x].find(u));
return abs(ans); for (int &i = ptr[x]; i < (int)adj[x].size(); i++) DFS(x);
} //& very important O(E^2V) −> O(EV^2)) }
}; { finale.push_back(u);
Edg &e = adj[x][i]; }
if ((level[e.to] == level[x] + 1) && e.cap)
Dinic.cpp {
Description: Dinic if (T df =
d41d8c, 87 lines
dfs(e.to, t, min(curFlow, e.cap)))
Extendedeuclid.cpp
template <typename T> Description: Extended Euclid d41d8c, 19 lines
{
struct dinic e.cap -= df; int modInverse(int A, int M)
// Mostly copied , wrong s p e l l i n g ?? adj[e.to][e.rev].cap += df; {
{ return df; int m0 = M;
struct Edg } int y = 0, x = 1;
{ } if (M == 1)
int to, rev; } return 0;
T cap; return 0; while (A > 1)
}; } {
vector<vector<Edg>> adj; T getMxFlow(int s, int t) int q = A / M;
int n; { int t = M;
dinic(int _n) T res = 0; M = A % M, A = t;
{ while (setUpLevel(s, t)) t = y;
n = _n; while (T df = y = x - q * y;
adj.resize(n); dfs(s, t, numeric_limits<T>::max())) x = t;
} res += df; }
inline T getActualFlow(int a, int i) // i i s index of edge return res; if (x < 0)
in l i s t of adj [ a ] ; } x += m0;
{ }; return x;
Edg e = adj[a][i];
}
Edg e2 = adj[e.to][e.rev];
IIT Madras Divideandconquerfft FastHash FFT 3
Divideandconquerfft.h ta[i] = (1ll*ta[i]*tb[i])%MOD; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
<bits/stdc++.h> d41d8c, 120 lines } x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
using namespace std; fft(ta,true); return x ^ (x >> 31);
const int MAXN = 300005; c = ta; }
const int root = 1489; } size_t operator()(uint64_t x) const
const int root_1 = 296201594; void dnc(int l, int r) {
const int root_pw = (1<<19); { static const uint64_t FIXED_RANDOM =
const long long int MOD = 663224321; if(l+1 == r) chrono::steady_clock::now().time_since_epoch().
long long int fact[MAXN], invfact[MAXN], pow2[MAXN], all_graphs { count();
[MAXN], poly1[MAXN], poly2[MAXN]; poly2[l] = (all_graphs[l]*invfact[l-1] + MOD - poly2[l])% return splitmix64(x + FIXED_RANDOM);
long long int power(long long int a, int b) MOD; }
{ } }; // use gp hash table<typea , typeb , custom hash> //faster than
if(!b) else unordered and policy based as well ( ordered set )
return 1; {
long long int ans = power(a,b/2); int m = (l + r)/2; FFT.cpp
ans = (ans*ans)%MOD; dnc(l,m); Description: FFT
if(b%2) dnc(m,r); <bits/stdc++.h> d41d8c, 76 lines
ans = (ans*a)%MOD; }
vector <long long int> p1, p2, ans; using namespace std;
return ans;
} int sz = r - l;
for (int i = sz; i < 2*sz; ++i) const int N = 3e5 + 9;
// f f t code taken from e−maxx. ru/algo/ f f t m u l t i p l y
void fft (vector <long long int> &a, bool invert) {
p1.push_back(poly1[i]); const double PI = acos(-1);
{ struct base {
int n = (int) a.size(); }
for (int i = l; i < r; ++i) double a, b;
for (int i = 1, j = 0; i < n; ++i) base(double a = 0, double b = 0) : a(a), b(b) {}
{ {
p2.push_back(poly2[i]); const base operator + (const base &c) const
int bit = n >> 1; { return base(a + c.a, b + c.b); }
for (; j >= bit; bit>>=1) }
multiply(p1,p2,ans); const base operator - (const base &c) const
j-=bit; { return base(a - c.a, b - c.b); }
j+=bit; for (int i = 0; i < ans.size(); ++i)
{ const base operator * (const base &c) const
if(i < j) { return base(a * c.a - b * c.b, a * c.b + b * c.a); }
swap(a[i], a[j]); int pos = l + sz + i;
poly2[pos] = (poly2[pos] + ans[i])%MOD; };
} void fft(vector<base> &p, bool inv = 0) {
for (int len = 2; len <= n; len<<=1) }
} int n = p.size(), i = 0;
{ for(int j = 1; j < n - 1; ++j) {
long long int wlen = invert ? root_1 : root; int main()
{ for(int k = n >> 1; k > (i ^= k); k >>= 1);
for (int i = len; i < root_pw; i<<=1) if(j < i) swap(p[i], p[j]);
wlen = (wlen*wlen)%MOD; fact[0] = invfact[0] = pow2[0] = all_graphs[0] = 1;
for (int i = 1; i < MAXN; ++i) }
for (int i = 0; i < n; i+=len) for(int l = 1, m; (m = l << 1) <= n; l <<= 1) {
{ {
fact[i] = (fact[i-1]*i)%MOD; double ang = 2 * PI / m;
long long int w = 1; base wn = base(cos(ang), (inv ? 1. : -1.) * sin(ang)), w;
for (int j = 0; j < len/2; ++j) invfact[i] = power(fact[i], MOD-2);
pow2[i] = (pow2[i-1]*2)%MOD; for(int i = 0, j, k; i < n; i += m) {
{ for(w = base(1, 0), j = i, k = i + l; j < k; ++j, w = w *
int u = a[i+j], v = (a[i+j+len/2]*w)%MOD; all_graphs[i] = (all_graphs[i-1]*pow2[i-1])%MOD;
poly1[i] = (all_graphs[i]*invfact[i])%MOD; wn) {
a[i+j] = u+v < MOD ? u+v : u+v-MOD; base t = w * p[j + l];
a[i+j+len/2] = u-v >= 0 ? u-v : u-v+MOD; }
dnc(1,(1<<17)+1); p[j + l] = p[j] - t;
w = (w*wlen)%MOD; p[j] = p[j] + t;
} int t;
cin>>t; }
} }
} while(t--)
{ }
if(invert) if(inv) for(int i = 0; i < n; ++i) p[i].a /= n, p[i].b /= n;
{ int x;
cin>>x; }
int nrev = power(n, MOD-2); vector<long long> multiply(vector<int> &a, vector<int> &b) {
for (int i=0; i<n; ++i) cout<<(poly2[x]*fact[x-1])%MOD<<"\n";
} int n = a.size(), m = b.size(), t = n + m - 1, sz = 1;
a[i] = (a[i]*nrev)%MOD; while(sz < t) sz <<= 1;
} return 0;
} vector<base> x(sz), y(sz), z(sz);
} for(int i = 0 ; i < sz; ++i) {
void multiply(vector <long long int> &a, vector <long long int> x[i] = i < (int)a.size() ? base(a[i], 0) : base(0, 0);
&b, vector <long long int> &c) FastHash.cpp y[i] = i < (int)b.size() ? base(b[i], 0) : base(0, 0);
{ Description: Fast Hash }
vector <long long int> ta(a.begin(), a.end()), tb(b.begin(), <ext/pb ds/assoc container.hpp>, <ext/pb ds/tree policy.hpp> d41d8c, 19 lines fft(x), fft(y);
b.end()), tc; using namespace std; for(int i = 0; i < sz; ++i) z[i] = x[i] * y[i];
int sz = 2*a.size(); using namespace __gnu_pbds; fft(z, 1);
ta.resize(sz); #define int long long vector<long long> ret(sz);
tb.resize(sz); struct custom_hash for(int i = 0; i < sz; ++i) ret[i] = (long long) round(z[i].a
fft(ta,false); { );
fft(tb,false); static uint64_t splitmix64(uint64_t x) while((int)ret.size() > 1 && ret.back() == 0) ret.pop_back();
for (int i = 0; i < sz; ++i) { return ret;
{ x += 0x9e3779b97f4a7c15; }
IIT Madras Gauss Hungarian KMP LCALOGN 4
{ while (j > 0 && s[i] != s[j])
long long ans[N]; b[i] /= A[i][i]; j = p[j - 1];
int32_t main() { x[col[i]] = b[i]; if (s[i] == s[j])
ios_base::sync_with_stdio(0); for (int j = 0; j < i; ++j) j++;
cin.tie(0); b[j] -= A[j][i] * b[i]; p[i] = j;
int n, x; cin >> n >> x; } }
vector<int> a(n + 1, 0), b(n + 1, 0), c(n + 1, 0); return rank; // ( multiple solutions i f rank < m) return p;
int nw = 0; } }
a[0]++; b[n]++;
long long z = 0;
for (int i = 1; i <= n; i++) { Hungarian.cpp LCALOGN.cpp
int k; cin >> k; Description: Hungarian d41d8c, 44 lines Description: lca(LOGN) d41d8c, 60 lines
nw += k < x; const int INF = 1e18;
a[nw]++; b[-nw + n]++; int preorder[1000005];
int hungarianMethod(vector<vector<int>> A) //A i s one indexed int postorder[1000005];
z += c[nw] + !nw; c[nw]++; !!!!!!!!!!
} int timer = 0;
{ int dp[1000005][22];
auto res = multiply(a, b); int n = A.size()-1;
for (int i = n + 1; i < res.size(); i++) { vector<int> adj[1000005];
int m = A.size()-1; //change t h i s i f dimensions are void DFS(int u, int par)
ans[i - n] += res[i]; different
} {
vector<int> u (n+1), v (m+1), p (m+1), way (m+1); preorder[u] = timer;
ans[0] = z; for (int i=1; i<=n; ++i) {
for (int i = 0; i <= n; i++) cout << ans[i] << ’ ’; timer++;
p[0] = i; dp[u][0] = par;
cout << ’\n’; int j0 = 0;
return 0; for (int i = 1; i < 22; i++)
vector<int> minv (m+1, INF); {
} vector<char> used (m+1, false);
//https :// codeforces .com/contest/993/problem/E int z = dp[u][i - 1];
do { if (z == -1)
used[j0] = true; {
int i0 = p[j0], delta = INF, j1; dp[u][i] = -1;
Gauss.cpp for (int j=1; j<=m; ++j) continue;
Description: Gauss d41d8c, 47 lines if (!used[j]) { }
typedef vector<long double> vd; int cur = A[i0][j]-u[i0]-v[j]; dp[u][i] = dp[z][i - 1];
using vi = vector<int>; if (cur < minv[j]) }
const double eps = 1e-12; minv[j] = cur, way[j] = j0; for (auto x : adj[u])
int solveLinear(vector<vd> &A, vd &b, vd &x) if (minv[j] < delta) {
{ delta = minv[j], j1 = j; if (x == par)
int n = size(A), m = size(x), rank = 0, br, bc; } {
vi col(m); for (int j=0; j<=m; ++j) continue;
iota(begin(col), end(col), 0); if (used[j]) }
for (int i = 0; i < n; ++i) u[p[j]] += delta, v[j] -= delta; DFS(x, u);
{ else }
double v, bv = 0; minv[j] -= delta; postorder[u] = timer;
for (int r = i; r < n; ++r) j0 = j1; timer++;
for (int c = i; c < m; ++c) } while (p[j0] != 0); }
if ((v = fabs(A[r][c])) > bv) do { int is_ancestor(int u, int v)
br = r, bc = c, bv = v; int j1 = way[j0]; {
if (bv <= eps) p[j0] = p[j1]; if (preorder[u] <= preorder[v] && postorder[u] >= postorder
{ j0 = j1; [v])
for (int j = i; j < n; ++j) } while (j0); {
if (fabs(b[j]) > eps) } return 1;
return -1; }
break; vector<pair<int, int>> result; //mapping return 0;
} for (int i = 1; i <= m; ++i){ }
swap(A[i], A[br]); result.push_back(make_pair(p[i], i)); int lca(int u, int v)
swap(b[i], b[br]); } {
swap(col[i], col[bc]); if (is_ancestor(u, v))
for (int j = 0; j < n; ++j) int C = -v[0]; // t o t a l cost {
swap(A[j][i], A[j][bc]); return C; return u;
bv = 1 / A[i][i]; } }
for (int j = i + 1; j < n; ++j) int z = u;
{ KMP.cpp for (int i = 21; i >= 0; i--)
double fac = A[j][i] * bv; Description: KMP {
b[j] -= fac * b[i]; d41d8c, 15 lines if (dp[z][i] == -1)
for (int k = i + 1; k < m; ++k) vector<int> prefix_function(string s) {
A[j][k] -= fac * A[i][k]; { continue;
} int n = (int)s.length(); }
rank++; vector<int> p(n); if (is_ancestor(dp[z][i], v))
} for (int i = 1; i < n; i++) {
x.assign(m, 0); { continue;
for (int i = rank; i--;) int j = p[i - 1]; }
IIT Madras LCAO1 MCMF 5
z = dp[z][i]; } //doesn ’ t work for negative cycles
} }; //for undirected edges j u s t make the directed f l a g f a l s e
return dp[z][0]; sparse_table tab; //Complexity : O(min(E^2 ∗V log V, E logV ∗ flow ) )
} LCA(int N) using T = long long;
{ const T inf = 1LL << 61;
n = N; struct MCMF {
LCAO1.cpp adj.resize(n); struct edge {
Description: LCA (o(1)) d41d8c, 120 lines
level.resize(n); int u, v;
firstOcc.assign(n, -1); T cap, cost;
struct LCA } int id;
{ void addEdge(int a, int b) edge(int _u, int _v, T _cap, T _cost, int _id) {
int n; { u = _u;
vector<vector<int>> adj; adj[a].push_back(b); v = _v;
vector<int> level; adj[b].push_back(a); cap = _cap;
vector<int> firstOcc; } cost = _cost;
vector<int> eulerIndices; void init(int root) id = _id;
struct sparse_table { }
{ vector<bool> vis(n, false); };
int n; int d = 0; int n, s, t, mxid;
std::vector<std::vector<int>> table; int eulWalkCnt = 0; T flow, cost;
vector<int> logs; function<void(int)> dfs = [&](int x) vector<vector<int>> g;
vector<int> logpow; { vector<edge> e;
void init(std::vector<int> &arr, vector<int> &level) vis[x] = true; vector<T> d, potential, flow_through;
{ if (firstOcc[x] == -1) vector<int> par;
n = arr.size(); { bool neg;
logs.assign(n, 0); firstOcc[x] = eulWalkCnt; MCMF() {}
int t = 0, k = 1; } MCMF(int _n) { // 0−based indexing
logpow.push_back(1); level[x] = d; n = _n + 10;
for (int i = 0; i < n; i++) eulerIndices.push_back(x); g.assign(n, vector<int> ());
{ eulWalkCnt++; neg = false;
if (k > ((i + 1) >> 1)) d++; mxid = 0;
{ for (auto &i : adj[x]) }
logs[i] = t; { void add_edge(int u, int v, T cap, T cost, int id = -1, bool
} if (!vis[i]) directed = true) {
else { if(cost < 0) neg = true;
{ dfs(i); g[u].push_back(e.size());
k = (k << 1); eulerIndices.push_back(x); e.push_back(edge(u, v, cap, cost, id));
t++; eulWalkCnt++; g[v].push_back(e.size());
logpow.push_back(k); } e.push_back(edge(v, u, 0, -cost, -1));
logs[i] = t; } mxid = max(mxid, id);
} d--; if(!directed) add_edge(v, u, cap, cost, -1, true);
} }; }
table.resize(n); dfs(root); bool dijkstra() {
for (int i = 0; i < n; i++) tab.init(eulerIndices, level); par.assign(n, -1);
{ } d.assign(n, inf);
table[i].resize(logs[n - i - 1] + 1); int find_LCA(int a, int b) priority_queue<pair<T, T>, vector<pair<T, T>>, greater<pair
} { <T, T>> > q;
for (int i = 0; i < n; i++) if (a == b) d[s] = 0;
{ return a; q.push(pair<T, T>(0, s));
table[i][0] = arr[i]; if (firstOcc[a] > firstOcc[b]) while (!q.empty()) {
} swap(a, b); int u = q.top().second;
for (int j = 1; j <= logs[n - 1]; j++) return tab.RMQ(firstOcc[a], firstOcc[b], level); T nw = q.top().first;
{ } q.pop();
for (int i = 0; (i + logpow[j] - 1) < n; i++) int find_dist(int a, int b) if(nw != d[u]) continue;
{ { for (int i = 0; i < (int)g[u].size(); i++) {
int a = table[i][j - 1]; int lc = find_LCA(a, b); int id = g[u][i];
int b = table[(i + logpow[j - 1])][j - 1]; return level[a] + level[b] - 2 * level[lc]; int v = e[id].v;
table[i][j] = level[a] > level[b] ? b : a; } T cap = e[id].cap;
} }; T w = e[id].cost + potential[u] - potential[v];
} if (d[u] + w < d[v] && cap > 0) {
} d[v] = d[u] + w;
int RMQ(int i, int j, vector<int> &level) MCMF.cpp
Description: MCMF par[v] = id;
{ q.push(pair<T, T>(d[v], v));
if (i > j) <bits/stdc++.h> d41d8c, 165 lines
}
swap(i, j); using namespace std; }
int t = logs[j - i]; }
int a = table[i][t]; const int N = 3e5 + 9; for (int i = 0; i < n; i++) {
; if (d[i] < inf) d[i] += (potential[i] - potential[s]);
int b = table[j - logpow[t] + 1][t]; //Works for both directed , undirected and with negative cost }
return level[a] > level[b] ? b : a; too
IIT Madras ncr NTT orderedset 6
for (int i = 0; i < n; i++) { for (int i = 0; i < n; i++) { }
if (d[i] < inf) potential[i] = d[i]; for (int j = 0; j < n; j++) {
} int k; NTT.cpp
return d[t] != inf; // for max flow min cost cin >> k; Description: NTT
// return d [ t ] <= 0; // for min cost flow F.add_edge(i, j + n, 1, k, i * 20 + j); d41d8c, 48 lines

} } const int N = 1 << 20;

T send_flow(int v, T cur) { } const int mod = 998244353;
if(par[v] == -1) return cur; int s = 2 * n + 1, t = s + 1; const int root = 3;
int id = par[v]; for (int i = 0; i < n; i++) { int lim, rev[N], w[N], wn[N], inv_lim;
int u = e[id].u; F.add_edge(s, i, 1, 0); void reduce(int &x) { x = (x + mod) % mod; }
T w = e[id].cost; F.add_edge(i + n, t, 1, 0); int POW(int x, int y, int ans = 1) {
T f = send_flow(u, min(cur, e[id].cap)); } for (; y; y >>= 1, x = (long long) x * x % mod) if (y & 1)
cost += f * w; auto ans = F.solve(s, t).second; ans = (long long) ans * x % mod;
e[id].cap -= f; long long w = 0; return ans;
e[id ^ 1].cap += f; set<int> se; }
return f; for (int i = 0; i < n; i++) { //There should be an or in //rev [ i ] = rev [ i>>1]>>1(i&1)<<s ;
} for (int j = 0; j < n; j++) { void precompute(int len) {
//returns {maxflow , mincost} int p = i * 20 + j; lim = wn[0] = 1; int s = -1;
pair<T, T> solve(int _s, int _t, T goal = inf) { if (F.flow_through[p] > 0) { while (lim < len) lim <<= 1, ++s;
s = _s; se.insert(j); for (int i = 0; i < lim; ++i) rev[i] = rev[i >> 1] >> 1 | (i
t = _t; w += F.flow_through[p]; & 1) << s;
flow = 0, cost = 0; } const int g = POW(root, (mod - 1) / lim);
potential.assign(n, 0); } inv_lim = POW(lim, mod - 2);
if (neg) { } for (int i = 1; i < lim; ++i) wn[i] = (long long) wn[i - 1] *
// Run Bellman−Ford to find starting potential on the assert(se.size() == n && w == n); g % mod;
starting graph cout << ans << ’\n’; }
// I f the starting graph ( before pushing flow in the return 0; void ntt(vector<int> &a, int typ) {
residual graph) i s a DAG, } for (int i = 0; i < lim; ++i) if (i < rev[i]) swap(a[i], a[
// then t h i s can be calculated in O(V + E) using DP: rev[i]]);
// potential (v) = min({potential [u ] + cost [u ] [ v ]}) for for (int i = 1; i < lim; i <<= 1) {
each u −> v and potential [ s ] = 0 ncr.cpp for (int j = 0, t = lim / i / 2; j < i; ++j) w[j] = wn[j *
d.assign(n, inf); Description: ncr d41d8c, 36 lines
t];
d[s] = 0; for (int j = 0; j < lim; j += i << 1) {
bool relax = true; const int mxN = 100005; // dont forget to change mxN l l power( for (int k = 0; k < i; ++k) {
for (int i = 0; i < n && relax; i++) { l l x , l l n) //x base n exponent{ const int x = a[k + j], y = (long long) a[k + j + i] *
relax = false; if (n == 0) w[k] % mod;
for (int u = 0; u < n; u++) { return 1; reduce(a[k + j] += y - mod), reduce(a[k + j + i] = x -
for (int k = 0; k < (int)g[u].size(); k++) { if (x % mod == 0) y);
int id = g[u][k]; return 0; // For large N,%mod− > mod i s prime }
int v = e[id].v; n = n % (mod - 1); }
T cap = e[id].cap, w = e[id].cost; ll pow = 1; }
if (d[v] > d[u] + w && cap > 0) { while (n) if (!typ) {
d[v] = d[u] + w; { reverse(a.begin() + 1, a.begin() + lim);
relax = true; if (n & 1) for (int i = 0; i < lim; ++i) a[i] = (long long) a[i] *
} pow = (pow * x) % mod; inv_lim % mod;
} n = n >> 1; }
} x = (x * x) % mod; }
} }
for(int i = 0; i < n; i++) if(d[i] < inf) potential[i] = return pow; //Issues of t l e can arise i f you do not pop back the
d[i]; } uneccesaary 0 due to rounding to nearest 2
} vector<ll> fact(mxN + 1); //Already done in t h i s code but keep in mind
while (flow < goal && dijkstra()) flow += send_flow(t, goal vector<ll> invfact(mxN + 1); vector<int> multiply(vector<int> &f, vector<int> &g) {
- flow); void genfact() // dont forget to c a l l genfact (){ int n=(int)f.size() + (int)g.size() - 1;
flow_through.assign(mxid + 10, 0); fact[0] = 1; precompute(n);
for (int u = 0; u < n; u++) { fori(i, mxN) vector<int> a = f, b = g;
for (auto v : g[u]) { { a.resize(lim); b.resize(lim);
if (e[v].id >= 0) flow_through[e[v].id] = e[v ^ 1].cap; fact[i + 1] = (fact[i] * (ll)(i + 1)) % mod; ntt(a, 1), ntt(b, 1);
} } for (int i = 0; i < lim; ++i) a[i] = (long long) a[i] * b[i]
} invfact[mxN] = power(fact[mxN], mod - 2); % mod;
return make_pair(flow, cost); for (int i = mxN - 1; i >= 0; i--) ntt(a, 0);
} { while((int)a.size() && a.back() == 0) a.pop_back();
}; invfact[i] = (invfact[i + 1] * (i + 1)) % mod; return a;
int main() { } }
ios_base::sync_with_stdio(0); }
cin.tie(0); ll ncr(ll n, ll r)
{ orderedset.cpp
int n; Description: orderedset
cin >> n; if (n - r < 0 || r < 0)
return 0; <ext/pb ds/assoc container.hpp>, <ext/pb ds/tree policy.hpp> d41d8c, 4 lines
assert(n <= 10);
MCMF F(2 * n); return ((fact[n] * invfact[n - r]) % mod * invfact[r]) % using namespace __gnu_pbds;
mod; #define int long long
IIT Madras persistentsegtree PersistentTrie rng SCCwithtopo 7
typedef sz[now_root]+=sz[prev_root]+1; int SCC_Topo[N]; //Vertex of SCC, Topologically
tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag, for (int i=0;i<=18;i++) sz[ww[i]]=sz[a[ww[i]][0]]+sz[a[ww[i Sorted .
tre e_order_statistics_node_update> ordered_set; ]][1]]; int SCC_Topo_Index[N]; //Index of vertex v in the
} topological sort .
persistentsegtree.cpp void findxor(int v, int l, int x) {
Description: Persistent Segtree for (int i=18;i>=0;i--) { //Note − Adj List may store multiple edges between 2 vertex
d41d8c, 41 lines int edge=(x & (1 << i)); vector<int> SCC_adj[N]; //Adj l i s t in SCC compressed ,
struct Node{ if (edge!=0) edge=1; outgoing edges .
int val; if (ind[a[v][1-edge]]>=l) { vector<int> SCC_incoming[N]; //Adj l i s t in SCC compressed ,
Node* l; v=a[v][1-edge]; incoming edges .
Node* r; ans+=(1-edge)*(1 << i);
Node(){ } //Helpers
val=0; else { int disc[N], low[N], In_stk[N], SCC_time;
l=nullptr; v=a[v][edge]; stack<int> stk;
r=nullptr; ans+=edge*(1 << i);
} } //Helper DFS for SCC
}; } void SCC_DFS(int chi)
Node* build(int lx,int rx){ } {
if(rx-lx==1){return new Node();} int findless(int v, int x) { //Assigns the low and disc values
Node* ret = new Node(); int ans=0; SCC_time++; disc[chi]=SCC_time; low[chi]=SCC_time;
int m=(lx+rx)/2; for (int i=18;i>=0;i--) { stk.push(chi); In_stk[chi]=1; //Put them in Stack
ret->l=build(lx,m); int edge=(x & (1 << i));
ret->r=build(m,rx); if (edge!=0) edge=1; //Runs DFS
return ret; for (int j=0;j<edge;j++) ans+=sz[a[v][j]]; for(auto x: adj[chi])
} v=a[v][edge]; {
Node* modify(int lx,int rx,Node* a,int i,int z){ } if(disc[x]==-1) { SCC_DFS(x); low[chi] = min(low[chi],
if(rx-lx==1){ ans+=sz[v]; low[x]); }
Node* ret=new Node(); return ans; else if(In_stk[x]==1) low[chi] = min(low[chi], disc[x])
ret->val=(a->val)^z; } ;
return ret; void findkth(int vr, int vl, int x) { }
} for (int i=18;i>=0;i--) {
Node* ret = new Node(); for (int j=0;j<=1;j++) // i f low = disc , i t i s the head node , and thus extracts the
ret->val=a->val; if (sz[a[vr][j]]-sz[a[vl][j]]<x) x-=sz[a[vr][j]]-sz subtree
ret->l=a->l; [a[vl][j]]; if(low[chi]==disc[chi])
ret->r=a->r; else { {
ret->val=((ret->val)^z); vr=a[vr][j]; int w; SCC_Nodes.push_back(chi); SCC_Component[chi].
int m=(lx+rx)/2; vl=a[vl][j]; push_back(chi);
if(i<m){ret->l = modify(lx,m,ret->l,i,z);} ans+=j*(1 << i); while(stk.top()!=chi)
else{ret->r = modify(m,rx,ret->r,i,z);} break; {
return ret; } w=stk.top(); stk.pop(); In_stk[w]=0;
} } SCC_par[w]=chi; SCC_Component[chi].push_back(w);
int getans(int lx,int rx,Node* a,int li,int ri) } }
{ stk.pop(); In_stk[chi]=0; SCC_par[chi]=chi;
if(lx>=li && rx<=ri){return a->val;} }
if(lx>=ri || li>=rx){return 0;} rng.cpp }
int m=(lx+rx)/2; Description: rng d41d8c, 2 lines
return getans(lx,m,a->l,li,ri)^getans(m,rx,a->r,li,ri); std::mt19937 rng((unsigned int) void SCC_Toposort() //Topologically sorts the newly for
} std::chrono::steady_clock::now().time_since_epoch().count()); DAG of SCC
{
PersistentTrie.cpp int in_deg[num_vertex+1] = {0};
Description: Persistent Trie SCCwithtopo.cpp for(int i=1; i<=num_vertex; i++) in_deg[i] = SCC_incoming[i
<iostream>, <cstdio> d41d8c, 56 lines
Description: scc with topo d41d8c, 95 lines
].size();
using namespace std; npconst int N = 1e5; queue<int> topo_qu; int topo_cnt=0;
int a[10000000][2],ww[20],sz[10000000],type,root[600000],m,ind for(int i=1; i<=num_vertex; i++) if(in_deg[i]==0) topo_qu.
[10000000]; vector<int> adj[N]; push(i);
int ans,n,v,l,r,x; int num_vertex;
void add(int prev_root, int now_root, int x) { while(!topo_qu.empty())
for (int i=18;i>=0;i--) { //KDVinit ’ s Implementation for Tarjan ’ s Algorithm (GFG) {
int edge=(x & (1 << i)); //Global Variables for SCC, int node = topo_qu.front(); topo_qu.pop();
if (edge!=0) edge=1; //This w i l l additionally use N = max, adj [N] for edges , SCC_Topo[++topo_cnt] = (node);
v++; //and Vertexes are defined from 1 −> num vertex . for(auto x: SCC_adj[node]) { in_deg[x]--; if(in_deg[x
ww[i]=now_root; ]==0) topo_qu.push(x); }
ind[v]=n; //Outputs of the Tarjan ’ s Algorithm }
a[now_root][edge]=v; vector<int> SCC_Nodes; //Nodes from main graph that
a[now_root][1-edge]=a[prev_root][1-edge]; are heads of SCC. for(int i=1; i<=num_vertex; i++) SCC_Topo_Index[SCC_Topo[i
sz[now_root]=sz[a[now_root][1-edge]]; vector<int> SCC_Component[N]; //Vertexes in the SCC Component ]]=i;
now_root=v; of a head node . }
prev_root=a[prev_root][edge]; int SCC_par[N]; //SCC Head of a node from
} original graph .
IIT Madras SegtreeKaustubhAddinarangeMax segtree segtree2d 8
//Main Function for SCC. } if (i < m)
void SCC_Compress() {
{ void propogate(int lx,int rx,int curr) update(lx, m, 2 * curr + 1, i, z);
// I n i t i a l i z e s Containers ( for multiple testcases ) { }
while(!stk.empty()) stk.pop(); SCC_Nodes.clear(); SCC_time if(rx-lx==1){return;} else
=0; maxa[2*curr+1].first+=ops[curr]; {
for(int i=1; i<=num_vertex; i++) { disc[i]=-1; In_stk[i]=0; maxa[2*curr+2].first+=ops[curr]; update(m, rx, 2 * curr + 2, i, z);
SCC_adj[i].clear(); } ops[2*curr+1]+=ops[curr]; }
ops[2*curr+2]+=ops[curr]; v[curr] = min(v[2 * curr + 1], v[2 * curr + 2]);
//SCC DFS from vertex unvisited ops[curr]=0; }
for(int i=1; i<=num_vertex; i++) if(disc[i]==-1) SCC_DFS(i) return; int getans(int lx, int rx, int curr, int l, int r)
; } {
if (lx >= l && rx <= r)
//To add edges to SCC Compressed void update(int lx,int rx,int curr,int l,int r,int val) {
for(int i=1; i<=num_vertex; i++) { return v[curr];
{ if(lx>=l && rx<=r) }
for(auto x: adj[i]) { if (l >= rx || lx >= r)
{ maxa[curr].first+=val; {
int su = SCC_par[i], sv = SCC_par[x]; //Head of ops[curr]+=val; return 1e12;
SCC comp return; }
if(su==sv) continue; //Belong to } int m = (lx + rx) / 2;
same comp return min(getans(lx, m, 2 * curr + 1, l, r), getans(m,
SCC_adj[su].push_back(sv); //Can if(l>=rx || lx>=r){return;} rx, 2 * curr + 2, l, r));
possible add multiple edges between 2 vertex propogate(lx,rx,curr); }
SCC_incoming[sv].push_back(su); int m=(lx+rx)/2; };
} update(lx,m,2*curr+1,l,r,val);
} update(m,rx,2*curr+2,l,r,val);
maxa[curr]=comb(maxa[2*curr+1],maxa[2*curr+2]); segtree2d.cpp
//Topologically sorts the newly for DAG of SCC Description: Segtree 2D d41d8c, 168 lines
SCC_Toposort(); }
} vector<vector<pair<int, int>>> zz;
pair<int,int> getans(int lx,int rx,int curr,int l,int r) vector<pair<int, int>> merger(vector<pair<int, int>> &a, vector
{ <pair<int, int>> &b)
SegtreeKaustubhAddinarangeMax.cpp if(lx>=l && rx<=r){return maxa[curr];} {
Description: Segtree kaustubh (add in a range, max in a range, cnt) if(lx>=r || l>=rx){return {-1,0};} int n = a.size();
d41d8c, 78 lines int m = b.size();
struct segtree propogate(lx,rx,curr); int curra = 0;
{ int m=(lx+rx)/2; int currb = 0;
vector<pair<int,int>> maxa; //Max, cnt of max?? return comb(getans(lx,m,2*curr+1,l,r),getans(m,rx,2* vector<pair<int, int>> v;
vector<int> ops; curr+2,l,r)); while (curra < n && currb < m)
} {
void init(int n) }; if (a[curra] < b[currb])
{ {
int curr=1; v.push_back(a[curra]);
while(curr<n){curr*=2;} segtree.cpp curra++;
Description: segtree kaustubh }
for(int i=0;i<2*curr;i++) d41d8c, 47 lines else
{ struct segtree {
maxa.push_back({0,0}); { v.push_back(b[currb]);
ops.push_back(0); vector<int> v; currb++;
} void init(int n) }
} { }
int curr = 1; while (curra < n)
void init_sp(int lx,int rx,int curr) while (curr < n) {
{ { v.push_back(a[curra]);
if(rx-lx==1){maxa[curr]={0,1};return;} curr = curr * 2; curra++;
maxa[curr]={0,rx-lx}; } }
int m=(lx+rx)/2; for (int i = 0; i < 2 * curr; i++) while (currb < m)
init_sp(lx,m,2*curr+1); { {
init_sp(m,rx,2*curr+2); v.push_back(0); v.push_back(b[currb]);
} } currb++;
} }
pair<int,int> comb(pair<int,int> a,pair<int,int> b) void update(int lx, int rx, int curr, int i, int z) return v;
{ { }
int maxs=max(a.first,b.first); if (rx - lx == 1) struct segtree
int cnt=0; { {
if(a.first==maxs){cnt+=a.second;} v[curr] = z; vector<pair<int, int>> present;
if(b.first==maxs){cnt+=b.second;} return; vector<int> v;
} int sizes;
return {maxs,cnt}; int m = (lx + rx) / 2; int ind_to_upd(int y, int i)
IIT Madras segtreelazyaryan 9
{ v[curr].present = zz[lx]; segtreelazyaryan.cpp
return lower_bound(present.begin(), present.end(), v[curr].init(zz[lx].size()); Description: Segtree Lazy Aryan d41d8c, 141 lines
make_pair(y, i)) - pre sent.begin(); re turn;
} } struct Node
int ind_just_g(int y, int i) int m = (lx + rx) / 2; {
{ build(2 * curr + 1, lx, m); ll val;
return lower_bound(present.begin(), present.end(), build(2 * curr + 2, m, rx); ll len;
make_pair(y, i)) - pre sent.begin(); v[curr].present = merger(v[2 * curr + 1].present, v[2 * };
} curr + 2].prese nt); template <typename ValType, typename OpType>
int ind_just_l(int y, int i) v[curr].init(v[curr].present.size()); struct segtree
{ } {
// returns 1 more as required by segtree void real_init(int n) int treesize;
return (lower_bound(present.begin(), present.end(), { vector<ValType> values;
make_pair(y + 1, i)) - present.begin()); int curr = 1; vector<OpType> operations;
} while (curr < n) ValType IDENTITY_ELEMENT;
void init(int n) { OpType NO_OPERATION; // No operation for modify op
{ curr = curr * 2; ValType (*calc_op)(ValType, ValType);
int curr = 1; } OpType (*composite)(OpType, OpType);
while (curr < n) for (int i = 0; i < 2 * curr; i++) ValType (*modify_op)(ValType, OpType);
{ { void build(int x, int l, int r) // build i s not called ,
curr = curr * 2; struct segtree x; c a l l i t manually
} x.init(1); {
for (int i = 0; i < 2 * curr; i++) v.push_back(x); if (l == r)
{ } // be careful l can be out of bound of
v.push_back(0); } vector you are assigning values from
} void real_update(int lx, int rx, int ix, int i, int y, int {
sizes = n; z, int curr) ValType res;
} { res.val = 0;
void update(int lx, int rx, int curr, int i, int z) int zz = v[curr].ind_to_upd(y, i); res.len = 1;
{ v[curr].update(0, v[curr].sizes, 0, zz, z); values[x] = res; // change to required
if (rx - lx == 1) if (rx - lx == 1) values in build and dont forget to build if
{ { required, its not included in init return;
v[curr] = z; return; }
return; } int mid = (l + r) / 2;
} int m = (lx + rx) / 2; build(2 * x + 1, l, mid);
int m = (lx + rx) / 2; if (ix < m) build(2 * x + 2, mid + 1, r);
if (i < m) { values[x] =
{ real_update(lx, m, ix, i, y, z, 2 * curr + 1); calc_op(values[2 * x + 1], values[2 * x + 2]);
update(lx, m, 2 * curr + 1, i, z); } }
} else segtree(int n, ValType identity, OpType noop, ValType (*cop
else { )(ValType, ValType), OpType (*comp)(OpType, OpType),
{ real_update(m, rx, ix, i, y, z, 2 * curr + 2); ValType (*modiop)(ValType, OpType))
update(m, rx, 2 * curr + 2, i, z); } {
} } IDENTITY_ELEMENT = identity;
v[curr] = min(v[2 * curr + 1], v[2 * curr + 2]); int real_getans(int lx, int rx, int ixl, int ixr, int i, NO_OPERATION = noop;
} int yl, int yr, int curr) calc_op = cop;
int getans(int lx, int rx, int curr, int l, int r) { composite = comp;
{ if (lx >= ixl && rx <= ixr) modify_op = modiop;
if (lx >= l && rx <= r) { init(n);
{ // cout<<”FFG\n”; build(0, 0, treesize - 1);
return v[curr]; int lly = v[curr].ind_just_g(yl, -1e12); }
} int rry = v[curr].ind_just_l(yr, -1e12); void init(int n) // Allocate space and i n i t i a l i z e values
if (l >= rx || lx >= r) // cout<<l l y <<” ”<<rry<<”\n”; for seg tree
{ // for (auto x : v [ curr ] . present ){cout<<x . f i r s t <<” {
return 1e12; "<<x.second<<" HH\n ";} // included in build function
} return v[curr] treesize = 1;
int m = (lx + rx) / 2; .getans(0, v[curr].sizes, 0, lly, rry); while (treesize < n)
return min(getans(lx, m, 2 * curr + 1, l, r), getans(m, } {
rx, 2 * curr + 2, l, r)); // cout<<"HIH\n"; treesize *= 2;
} if (ixl >= rx || lx >= ixr) }
}; { operations.assign(2 * treesize, NO_OPERATION); //
struct segtree_2d return 1e12; I n i t i a l state values dont forget to change
{ } values.assign(2 * treesize, IDENTITY_ELEMENT);
vector<struct segtree> v; int m = (lx + rx) / 2; }
void build(int curr, int lx, int rx) return min(real_getans(lx, m, ixl, ixr, i, yl, yr, 2 * OPERATIONS
{ curr + 1), real_getans(m, rx, ixl, ixr, i, yl, yr, inline void
// cout<<curr<<” ”<<lx<<” ”<<rx<<”\n”; 2 * curr + 2)); apply_modify_op(ValType &a, OpType b)
if (rx - lx == 1) } {
{ }; a = modify_op(a, b);
IIT Madras Seive SuffixArray 10
} { temp[pos[C[i].first]] = C[i];
inline void propagate(int x, int l, int r) if (b == 2) pos[C[i].first]++;
{ return a; }
if (x >= treesize - 1) Node res; return;
return; res.val = b * a.len; }
operations[2 * x + 1] = res.len = a.len; void suffixarr(vector<int> &j)
composite(operations[x], operations[2 * x + 1]); return res; {
operations[2 * x + 2] = } str += " ";
composite(operations[x], operations[2 * x + 2]); ll composite(ll a, ll b) n++;
apply_modify_op(values[2 * x + 1], operations[x]); { vector<pair<char, int>> init(n);
apply_modify_op(values[2 * x + 2], operations[x]); if (a == 2) fori(i, n) { init[i] = {str[i], i}; }
operations[x] = NO_OPERATION; return b; sort(init.begin(), init.end());
} return a; vector<int> value(n), j_new(n), value_new(n);
void modify(OpType val, int ql, int qr, int curr, int l, } int k = 0;
int r) fori(i, n) { j[i] = init[i].second; }
{ value[j[0]] = 0;
propagate(curr, l, r); Seive.cpp fori(i, n - 1)
if (l > qr || ql > r) Description: Seive d41d8c, 27 lines {
{ vector<ll> primes; if (init[i].first == init[i + 1].first)
return; vector<ll> leastPrime; {
} void sieveofErath(int mxSieve) value[j[i + 1]] = value[j[i]];
if (l >= ql && r <= qr) { eqclasses[k][j[i + 1]] = value[j[i]];
leastPrime.assign(mxSieve + 1, 0); }
{ leastPrime[1] = -1; else
operations[curr] = ll p; {
composite(val, operations[curr]); for (p = 2; p <= mxSieve; p++) value[j[i + 1]] = value[j[i]] + 1;
apply_modify_op(values[curr], val); { eqclasses[k][j[i + 1]] = value[j[i]] + 1;
return; if (!leastPrime[p]) }
} { }
int mid = (l + r) / 2; leastPrime[p] = p; int t;
modify(val, ql, qr, 2 * curr + 1, l, mid); primes.pb(p); vector<pair<int, int>> C(n), C_new(n);
modify(val, ql, qr, 2 * curr + 2, mid + 1, r); } while ((1 << k) < n)
values[curr] = for (int j = 0; j < primes.size() && {
calc_op(values[2 * curr + 1], values[2 * curr + 2]) (primes[j] * p) <= mxSieve; t = 1 << k;
; j++) fori(i, n) { C[i] = {value[(j[i] - t + n) % n], (j[
} { i] - t + n) % n}; }
void modify(OpType val, int ql, int qr) leastPrime[primes[j] * p] = counting_sort(C, C_new);
{ primes[j]; value_new[C_new[0].second] = 0;
if (ql > qr) if (!(p % primes[j])) fori(i, n - 1)
return; { {
modify(val, ql, qr, 0, 0, treesize - 1); break; if (C_new[i].first == C_new[i + 1].first &&
} } value[(C_new[i].second + t) % n] == value[(
ValType calc(int ql, int qr, int curr, int l, int r) } C_new[i + 1].second + t) % n])
{ } {
propagate(curr, l, r); } value_new[(C_new[i + 1]).second] =
if (l > qr || ql > r) value_new[(C_new[i]).seco nd];
return IDENTITY_ELEMENT; eqclasses[k + 1][(C_new[i + 1]).second] =
if (l >= ql && r <= qr) SuffixArray.cpp value_new[(C_new[i]).s econd];
{ Description: SuffixArray d41d8c, 118 lines
}
return values[curr]; else
} struct suffixArray {
int mid = (l + r) / 2; { value_new[(C_new[i + 1]).second] =
ValType a = calc(ql, qr, 2 * curr + 1, l, mid); int n; value_new[(C_new[i]).seco nd] + 1;
ValType b = calc(ql, qr, 2 * curr + 2, mid + 1, r); int lgN; eqclasses[k + 1][(C_new[i + 1]).second] =
return calc_op(a, b); string str; value_new[(C_new[i]).s econd] + 1;
} vector<vector<int>> eqclasses; }
ValType calc(int ql, int qr) vector<int> arraySuffix; }
{ vector<int> lcparray; fori(i, n) { j[i] = C_new[i].second; }
return calc(ql, qr, 0, 0, treesize - 1); void counting_sort(vector<pair<int, int>> &C, vector<pair< swap(value, value_new);
} int, int>> &temp) k++;
}; { }
Node calc_op(Node a, Node b) int n = C.size(); str.pop_back();
{ vector<int> pos(n); n--;
Node res; int arr[n]; return;
res.val = a.val + b.val; fori(i, n) { arr[i] = 0; } }
res.len = a.len + b.len; fori(i, n) { (arr[C[i].first])++; } void lcp()
return res; pos[0] = 0; {
} fori(i, n - 1) { pos[i + 1] = pos[i] + arr[i]; } str += ’ ’;
Node modify_op(Node a, ll b) fori(i, n) n++;
{
IIT Madras Trie ZAlgo hld 11
vector<int> invsuff(n); cur = cur->nxt[b]; {
fori(i, n) cur->sz++; int n = a.size();
{ } z.assign(n, 0);
invsuff[arraySuffix[i]] = i; } z[0] = n;
} int query(int x, int k) for (int i = 1, l = 0, r = 0; i < n; i++)
int k = 0; { // number of values s . t . val ^ x < k node∗ cur = root ; {
fori(i, n - 1) int ans = 0; if (i >= r)
{ for (int i = B - 1; i >= 0; i--) {
while ((arraySuffix[invsuff[i] - 1] + k < n) && (i { int c = i, d = 0;
+ k < n) && (str[i + k] == str[arraySuffix[ if (cur == NULL) while (c < n && a[c] == a[d])
invsuff[i] - 1] + k])) break; c++, d++;
{ int b1 = x >> i & 1, b2 = k >> i & 1; l = i, r = c;
k++; if (b2 == 1) z[i] = d;
} { }
lcparray[invsuff[i] - 1] = k; if (cur->nxt[b1]) else
k = max(k - 1, 0); ans += cur->nxt[b1]->sz; {
} cur = cur->nxt[!b1]; // l . . i . . r i . . r−> i−l . . r−l −> 0 . . r−i
str.pop_back(); } int offset = min(z[i - l], r - i);
n--; else int c = i + offset, d = offset;
} cur = cur->nxt[b1]; while (c < n && a[c] == a[d])
suffixArray(string input) } c++, d++;
{ return ans; if (c > r)
n = input.size(); } l = i, r = c;
str = input; int get_max(int x) z[i] = d;
int lgN = 0; { // returns maximum of val ^ x node∗ cur = root ; }
int cur = 1; int ans = 0; }
while (cur < n) for (int i = B - 1; i >= 0; i--) }
{ { };
cur = (cur << 1); int k = x >> i & 1;
lgN++; if (cur->nxt[!k])
} cur = cur->nxt[!k], ans <<= 1, ans++; hld.h d41d8c, 54 lines
eqclasses.assign(lgN + 2, vector<int>(n + 1, 0)); else
arraySuffix.assign(n + 1, 0); cur = cur->nxt[k], ans <<= 1; vector<int> parent, depth, heavy, head, pos;
lcparray.assign(n, 0); } int cur_pos;
suffixarr(this->arraySuffix); return ans;
lcp(); } int dfs(int v, vector<vector<int>> const& adj) {
} int get_min(int x) int size = 1;
}; { // returns minimum of val ^ x node∗ cur = root ; int max_c_size = 0;
int ans = 0; for (int c : adj[v]) {
for (int i = B - 1; i >= 0; i--) if (c != parent[v]) {
Trie.cpp { parent[c] = v, depth[c] = depth[v] + 1;
Description: Trie int k = x >> i & 1; int c_size = dfs(c, adj);
d41d8c, 84 lines size += c_size;
if (cur->nxt[k])
struct Trie cur = cur->nxt[k], ans <<= 1; if (c_size > max_c_size)
{ else max_c_size = c_size, heavy[v] = c;
static const int B = 31; cur = cur->nxt[!k], ans <<= 1, ans++; }
struct node } }
{ return ans; return size;
node *nxt[2]; } }
void del(node *cur)
int sz; { void decompose(int v, int h, vector<vector<int>> const& adj) {
node() for (int i = 0; i < 2; i++) head[v] = h, pos[v] = cur_pos++;
{ if (cur->nxt[i]) if (heavy[v] != -1)
nxt[0] = nxt[1] = NULL; del(cur->nxt[i]); decompose(heavy[v], h, adj);
sz = 0; delete (cur); for (int c : adj[v]) {
} } if (c != parent[v] && c != heavy[v])
} *root; } t; decompose(c, c, adj);
Trie() }
{ }
root = new node(); ZAlgo.cpp
} Description: Z Algo void init(vector<vector<int>> const& adj) {
void insert(int val) d41d8c, 35 lines int n = adj.size();
{ template <typename T> parent = vector<int>(n);
node *cur = root; depth = vector<int>(n);
cur->sz++; struct ZAlgo heavy = vector<int>(n, -1);
for (int i = B - 1; i >= 0; i--) { head = vector<int>(n);
{ vector<int> z; pos = vector<int>(n);
int b = val >> i & 1; // z [ i ] −> maximum length of a substring starting at i , and cur_pos = 0;
if (cur->nxt[b] == NULL) also a prefix
cur->nxt[b] = new node(); ZAlgo(T a) dfs(0, adj);
IIT Madras VirtualTree persistantCentroidDecomposition 12
decompose(0, 0, adj); // sort by entry time }
} sort(v.begin(), v.end(), [](int x, int y) { return 0;
int query(int a, int b) { return st[x] < st[y]; }
int res = 0; }); // https :// codeforces .com/contest/613/problem/D
for (; head[a] != head[b]; b = parent[head[b]]) { // finding a l l the ancestors , there are few of them
if (depth[head[a]] > depth[head[b]]) int s = v.size(); persistantCentroidDecomposition.h
swap(a, b); for (int i = 0; i < s - 1; i++) { <bits/stdc++.h> d41d8c, 165 lines
int cur_heavy_path_max = segment_tree_query(pos[head[b int lc = lca(v[i], v[i + 1]);
]], pos[b]); v.push_back(lc); using namespace std;
res = max(res, cur_heavy_path_max); }
} // removing duplicated nodes const int N = 2e5 + 9, M = N * 2 + N * 19 * 2;
if (depth[a] > depth[b]) sort(v.begin(), v.end());
swap(a, b); v.erase(unique(v.begin(), v.end()), v.end()); vector<pair<int, int>> g[N * 2], G[N];
int last_heavy_path_max = segment_tree_query(pos[a], pos[b // again sort by entry time inline void add_edge(int u, int v, int w) {
]); sort(v.begin(), v.end(), [](int x, int y) { g[u].push_back({v, w});
res = max(res, last_heavy_path_max); return st[x] < st[y]; }
return res; }); int T;
} stack<int> st; void binarize(int u, int p = 0) {
st.push(v[0]); int last = 0, tmp = 0;
for (int i = 1; i < v.size(); i++) { for (auto e : G[u]) {
VirtualTree.h int v = e.first, w = e.second;
<bits/stdc++.h> d41d8c, 114 lines
while (!isanc(st.top(), v[i])) st.pop();
t[st.top()].push_back(v[i]); if (v == p) continue;
using namespace std; st.push(v[i]); ++tmp;
} if (tmp == 1) {
const int N = 3e5 + 9; return v; add_edge(u, v, w);
} add_edge(v, u, w);
vector<int> g[N]; int ans; last = u;
int par[N][20], dep[N], sz[N], st[N], en[N], T; int imp[N]; } else if (tmp == ((int) G[u].size()) - (u != 1)) {
void dfs(int u, int pre) { int yo(int u) { add_edge(last, v, w);
par[u][0] = pre; vector<int> nw; add_edge(v, last, w);
dep[u] = dep[pre] + 1; for (auto v : t[u]) nw.push_back(yo(v)); } else {
sz[u] = 1; if (imp[u]) { T++;
st[u] = ++T; for (auto x : nw) if (x) ans++; add_edge(last, T, 0);
for (int i = 1; i <= 18; i++) par[u][i] = par[par[u][i - 1]][ return 1; add_edge(T, last, 0);
i - 1]; } else { last = T;
for (auto v : g[u]) { int cnt = 0; add_edge(T, v, w);
if (v == pre) continue; for (auto x : nw) cnt += x > 0; add_edge(v, T, w);
dfs(v, u); if (cnt > 1) { }
sz[u] += sz[v]; ans++; }
} return 0; for (auto e : G[u]) {
en[u] = T; } int v = e.first;
} return cnt; if (v == p) continue;
int lca(int u, int v) { } binarize(v, u);
if (dep[u] < dep[v]) swap(u, v); } }
for (int k = 18; k >= 0; k--) if (dep[par[u][k]] >= dep[v]) u int32_t main() { }
= par[u][k]; ios_base::sync_with_stdio(0); int sz[N * 2];
if (u == v) return u; cin.tie(0); int tot, done[N * 2], cenpar[N * 2];
for (int k = 18; k >= 0; k--) if (par[u][k] != par[v][k]) u = int i, j, k, n, m, q, u, v; void calc_sz(int u, int p) {
par[u][k], v = par[v][k]; cin >> n; tot ++;
return par[u][0]; for (i = 1; i < n; i++) cin >> u >> v, g[u].push_back(v), g[v sz[u] = 1;
} ].push_back(u); for (auto e : g[u]) {
int kth(int u, int k) { dfs(1, 0); int v = e.first;
for (int i = 0; i <= 18; i++) if (k & (1 << i)) u = par[u][i cin >> q; if(v == p || done[v]) continue;
]; while (q--) { calc_sz(v, u);
return u; cin >> k; sz[u] += sz[v];
} vector<int> v; }
int dist(int u, int v) { for (i = 0; i < k; i++) cin >> m, v.push_back(m), imp[m] = }
int lc = lca(u, v); 1; int find_cen(int u, int p) {
return dep[u] + dep[v] - 2 * dep[lc]; int fl = 1; for (auto e : g[u]) {
} for (auto x : v) if (imp[par[x][0]]) fl = 0; int v = e.first;
int isanc(int u, int v) { ans = 0; if(v == p || done[v]) continue;
return (st[u] <= st[v]) && (en[v] <= en[u]); vector<int> nodes; else if(sz[v] > tot / 2) return find_cen(v, u);
} if (fl) nodes = buildtree(v); }
vector<int> t[N]; if (fl) yo(nodes.front()); return u;
// given s p e c i f i c nodes , construct a compressed directed tree if (!fl) ans = -1; }
with these vertices ( i f needed some other nodes included ) cout << ans << ’\n’; long long d[20][N * 2];
// returns the nodes of the tree // clear the tree void yo(int u, int p, long long nw, int l) {
// nodes . front () i s the root for (auto x : nodes) t[x].clear(); d[l][u] = nw;
// t [ ] i s the s p e c i f i c tree for (auto x : v) imp[x] = 0; for(auto e : g[u]) {
vector<int> buildtree(vector<int> v) { int v = e.first;
IIT Madras MillerRabin 13
long long w = e.second; int u, v, w; int a = 2 + rand() % (n - 4);
if (v == p || done[v]) continue; cin >> u >> v >> w;
yo(v, u, nw + w, l); G[u].push_back({v, w}); // Compute a^d % n
} G[v].push_back({u, w}); int x = power(a, d, n);
} }
int st[N * 2], en[N * 2], DT; T = n; if (x == 1 || x == n-1)
struct node { binarize(1); return true;
vector<int> ct; //adjacent edges in centroid tree root[0] = decompose(1);
int level = 0, id = 0, cnt = 0; for(int i = 1; i <= n; i++) root[i] = upd(root[i - 1], a[i]); // Keep squaring x while one of the following doesn ’ t
long long sum = 0, parsum = 0; long long ans = 0; // happen
} t[M]; const int mod = 1 << 30; // ( i ) d does not reach n−1
int decompose(int u, int p = 0, int l = 0) { while(q--) { // ( i i ) (x^2) % n i s not 1
tot = 0; int ty; // ( i i i ) (x^2) % n i s not n−1
calc_sz(u, p); cin >> ty; while (d != n-1)
int cen = find_cen(u, p); if(ty == 1) { {
cenpar[cen] = p; int l, r, u; x = (x * x) % n;
done[cen] = 1; cin >> l >> r >> u; d *= 2;
u = cen; l ^= ans;
st[u] = ++DT; r ^= ans; if (x == 1) return false;
t[u].id = u; u ^= ans; if (x == n-1) return true;
t[u].level = l; ans = query(root[r], u) - query(root[l - 1], u); }
yo(u, p, 0, l); cout << ans << ’\n’;
for (auto e : g[u]) { ans %= mod; // Return composite
int v = e.first; } else { return false;
if(v == p || done[v]) continue; int x; }
int x = decompose(v, u, l + 1); cin >> x;
t[u].ct.push_back(x); x ^= ans; // I t returns f a l s e i f n i s composite and returns true i f n
} root[x] = upd(root[x - 1], a[x + 1]); // i s probably prime . k i s an input parameter that determines
en[u] = DT; swap(a[x], a[x + 1]); // accuracy l e v e l . Higher value of k indicates more accuracy .
return u; } bool isPrime(int n, int k)
} } {
int insub(int r, int c) { return 0; // Corner cases
r = t[r].id, c = t[c].id; } if (n <= 1 || n == 4) return false;
return st[r] <= st[c] && en[c] <= en[r]; //https :// codeforces .com/contest/757/problem/G if (n <= 3) return true;
}
int upd(int cur, int u) { //update node u in cur tree MillerRabin.h // Find r such that n = 2^d ∗ r + 1 for some r >= 1
T++; <bits/stdc++.h> d41d8c, 92 lines
int d = n - 1;
assert(T < M); while (d % 2 == 0)
t[T] = t[cur]; // C++ program Miller−Rabin primality t e s t d /= 2;
cur = T; using namespace std;
t[cur].cnt++; // Iterate given number of ’ k ’ times
t[cur].sum += d[t[cur].level][u]; // U t i l i t y function to do modular exponentiation . for (int i = 0; i < k; i++)
for(auto &v : t[cur].ct) if(insub(v, u)) { // I t returns (x^y) % p if (!miillerTest(d, n))
v = upd(v, u); int power(int x, unsigned int y, int p) return false;
t[v].parsum += d[t[cur].level][u]; {
} int res = 1; // I n i t i a l i z e r e s u l t return true;
return cur; x = x % p; // Update x i f i t i s more than or }
} // equal to p
long long query(int cur, int u) { //query on cur tree while (y > 0) // Driver program
long long ans = 0; { int main()
while (t[cur].id != t[u].id) { // I f y i s odd , multiply x with r e s u l t {
int v = 0; if (y & 1) int k = 4; // Number of iterations
for (auto x : t[cur].ct) if(insub(x, u)) v = x; res = (res*x) % p;
assert(v); cout << "All primes smaller than 100: \n";
ans += d[t[cur].level][t[u].id] * (t[cur].cnt - t[v].cnt); // y must be even now for (int n = 1; n < 100; n++)
ans += t[cur].sum - t[v].parsum; y = y>>1; // y = y/2 if (isPrime(n, k))
cur = v; x = (x*x) % p; cout << n << " ";
} }
ans += t[cur].sum; return res; return 0;
return ans; } }
}
int a[N], root[N]; // This function i s called for a l l k t r i a l s . I t returns
int32_t main() { // f a l s e i f n i s composite and returns true i f n i s
ios_base::sync_with_stdio(0); // probably prime .
cin.tie(0); // d i s an odd number such that d∗2 = n−1
int n, q; // for some r >= 1
cin >> n >> q; bool miillerTest(int d, int n)
for(int i = 1; i <= n; i++) cin >> a[i]; {
for (int i = 1; i < n; i++) { // Pick a random number in [ 2 . . n−2]
// Corner cases make sure that n > 4