232-aka-pretty-pi 님의 블로그 232-aka-pretty-pi 님의 블로그

struct Trie { constexpr static int L = 30; struct Node { int to[2]; int cnt; Node() { to[0] = 0; to[1] = 0; cnt = 0; } int operator[](int idx) const { return to[idx]; } int& operator[](int idx) { return to[idx]; } }; std::vector a; Trie() : a({{}}) { void(0); } void add(int x, int s = 1) { int v = 0; a[v].cnt += s; assert(..

need RollBackUnionFindstruct OfflineDynamicConnectivity { int n; std::vector> edges; OfflineDynamicConnectivity(int n) : n(n) { assert(n > 0); } void addEdge(int l, int r, int u, int v) { assert(0 solve(const std::vector>& qrs) const { int q = int(qrs.size()); assert(q > 0); std::vector>> seg(2 * q - 1); for (const auto& [l, r, u, v] : edges) { assert(0 void { ..

TODO : fix odc with new impl.use first impl if you need to use odcelse use second impl.struct RollBackUnionFind { int n; std::vector f; std::vector siz; std::vector> history; RollBackUnionFind(int _n) : n(_n) { f.resize(n); std::iota(f.begin(), f.end(), 0); siz.resize(n, 1); } int find(int x) { assert(0 = 0); for (int it = 0; it struct RollbackUnionFind { int n; std::vect..

need getStronglyConnectedComponent.struct TwoSat { // x : x > g; std::vector scc_id; TwoSat(int n) : n(n), g(n answer() const { std::vector res(n); for (int i = 0; i

std::vector getScc(const std::vector>& g) { int n = int(g.size()); int timer = 0; std::vector vis(n, -1); std::vector reach(n); std::vector stk; std::vector scc_id(n); std::vector done(n); int new_id = 0; auto dfs = [&](auto&& dfs, int x) -> void { stk.push_back(x); reach[x] = vis[x] = timer++; for (const auto& y : g[x]) { if (vis[y] == -1) { dfs(dfs, y); rea..

namespace knuth_x { struct Node { int id; int siz; Node* leader; Node* up; Node* down; Node* left; Node* right; Node(int id = -1) : id(id), siz(0), leader(nullptr), up(nullptr), down(nullptr), left(nullptr), right(nullptr) { void(0); } }; void cover(Node* leader) { leader->right->left = leader->left; leader->left->right = leader->right; for (Node* i = ..

template struct Fenwick2D { int n, m; std::vector> a; Fenwick2D(int n, int m) : n(n), m(m) { a.assign(n, std::vector(m)); } template Fenwick2D(const std::vector>& v) { n = int(v.size()); m = (n == 0 ? 0 : int(v[0].size())); a.assign(n, std::vector(m)); for (int i = 0; i = 0; i = (i & (i + 1)) - 1) { for (int j = y; j >= 0; j = (j & (j + 1)) - 1) { res += a[i][j]..

using int128 = __int128;std::istream& operator >> (std::istream& stream, int128& x) { long long t; stream >> t; x = t; return stream;}std::ostream& operator