Skip to content

Instantly share code, notes, and snippets.

View NamPE286's full-sized avatar

Bùi Hùng Nam NamPE286

13 followers · 0 following
View GitHub Profile
@NamPE286
NamPE286 / segtree.cpp
Created November 16, 2024 08:39
Segment tree
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class SegmentTree {
struct Node {
pair<ll, ll> range;
ll left = 0, right = 0, value = INT_MAX;
};
@NamPE286
NamPE286 / centroidDecomp.cpp
Created October 30, 2024 15:33
Centroid decomposition
// https://codeforces.com/problemset/problem/342/E
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF = 1e9;
class Tree {
@NamPE286
NamPE286 / BCC.cpp
Created December 6, 2023 16:52
Block cut tree (Biconnected component)
// https://cses.fi/problemset/result/7855807/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class BinaryLifting {
vector<vector<ll>> graph;
vector<vector<ll>> parent;
@NamPE286
NamPE286 / mergeSortTreeImmutable.cpp
Created December 5, 2023 07:44
Merge Sort Tree Immutable
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class MergeSortTreeImmutable {
struct Node {
vector<ll> v;
pair<ll, ll> range;
Node* left = nullptr;
@NamPE286
NamPE286 / dsuRollBack.cpp
Last active December 8, 2023 03:27
DSU with rollback
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class DSU {
vector<ll> p; // parent if positive, size if negative, parent of root is the size of component
stack<pair<ll, ll>> log; // keep track of p[i] value history, first is index, second is value
stack<ll> size;
@NamPE286
NamPE286 / scc.cpp
Created November 1, 2023 03:02
Find strongly connected component (SCC) with dfs tree
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class DFSTree {
vector<ll> nums, low;
vector<bool> deleted;
stack<ll> st;
vector<ll> scc;
@NamPE286
NamPE286 / hld.cpp
Last active November 16, 2024 08:42
Heavy Light Decomposition
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
class SegmentTree {
struct Node {
pair<ll, ll> range;
ll left = 0, right = 0, value = 0;
};
@NamPE286
NamPE286 / sparseTable.cpp
Last active October 26, 2023 09:14
Sparse table
// https://cses.fi/problemset/task/1647
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class SparseTable {
private:
vector<vector<ll>> ST;
@NamPE286
NamPE286 / monotoneChain.cpp
Created September 26, 2023 01:33
Convex Hull (monotone chain algorithm)
// https://cses.fi/problemset/task/2195/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll crossProd(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c) {
return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
}
@NamPE286
NamPE286 / binaryLifing.cpp
Last active September 16, 2023 04:34
Binary lifting template
// https://cses.fi/problemset/task/1688/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class BinaryLifting {
ll MAXLOG;
vector<vector<ll>> parent;