Untitled

#ifndef CHEATSHEET_H
#define CHEATSHEET_H

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <tuple>
#include <math.h>
#include <functional>

using namespace std;

//=====================================================================================
// 1. bfs, dfs - pe un graf orientat sau neorientat (retinere generica)
// usage example:
// graf g(5, false);
// g.adaugaMuchie(0, 1);
// g.adaugaMuchie(1, 2);
// vector<int> rez_bfs = g.bfs(0);
// vector<int> rez_dfs = g.dfs(0);
//=====================================================================================
class Graf {
public:
    int n;
    bool orientat;
    vector<vector<int>> adj;

    Graf(int n, bool orientat = false) : n(n), orientat(orientat) {
        adj.resize(n);
    }

    void adaugaMuchie(int u, int v) {
        adj[u].push_back(v);
        if(!orientat) {
            adj[v].push_back(u);
        }
    }

    // bfs
    vector<int> bfs(int start) {
        vector<int> viz(n, 0), rez;
        queue<int> q;
        viz[start] = 1;
        q.push(start);
        while(!q.empty()) {
            int node = q.front();
            q.pop();
            rez.push_back(node);
            for(auto &vecin : adj[node]) {
                if(!viz[vecin]) {
                    viz[vecin] = 1;
                    q.push(vecin);
                }
            }
        }
        return rez;
    }

    // dfs (recursiv)
    void dfsUtil(int node, vector<int> &viz, vector<int> &rez) {
        viz[node] = 1;
        rez.push_back(node);
        for(auto &vecin : adj[node]) {
            if(!viz[vecin]) {
                dfsUtil(vecin, viz, rez);
            }
        }
    }

    vector<int> dfs(int start) {
        vector<int> viz(n, 0), rez;
        dfsUtil(start, viz, rez);
        return rez;
    }
};

//=====================================================================================
// 2. noduri critice (articulation points) si muchii critice (bridges)
// usage example (stapane, daca vrei sa afli ce noduri si muchii iti pot da dureri de cap):
// graphcritic gc(5);
// gc.adaugaMuchie(0,1);
// gc.adaugaMuchie(1,2);
// gc.findArticulationPointsAndBridges();
// vector<bool> ap = gc.articulation;
// vector<pair<int,int>> br = gc.bridges;
//=====================================================================================
class GraphCritic {
public:
    int n;
    vector<vector<int>> adj;
    vector<int> disc, low, parent;
    vector<bool> articulation;
    int timp;
    vector<pair<int,int>> bridges;

    GraphCritic(int n) : n(n) {
        adj.resize(n);
        disc.resize(n, -1);
        low.resize(n, -1);
        parent.resize(n, -1);
        articulation.resize(n, false);
        timp = 0;
    }

    void adaugaMuchie(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void dfsAP(int u) {
        disc[u] = low[u] = timp++;
        int copii = 0;
        for(int v : adj[u]) {
            if(disc[v] == -1) {
                parent[v] = u;
                copii++;
                dfsAP(v);
                low[u] = min(low[u], low[v]);

                if(parent[u] == -1 && copii > 1) {
                    articulation[u] = true;
                }
                if(parent[u] != -1 && low[v] >= disc[u]) {
                    articulation[u] = true;
                }
                if(low[v] > disc[u]) {
                    bridges.push_back({u, v});
                }
            } else if(v != parent[u]) {
                low[u] = min(low[u], disc[v]);
            }
        }
    }

    void findArticulationPointsAndBridges() {
        for(int i = 0; i < n; i++) {
            if(disc[i] == -1) {
                dfsAP(i);
            }
        }
    }
};

//=====================================================================================
// 3. tarjan pentru strongly connected components (graf orientat)
// usage example (ai un graf orientat si vrei scc?):
// tarjanscc t(5);
// t.adaugaMuchie(0,1);
// t.adaugaMuchie(1,2);
// t.buildSCCs();
// vector<vector<int>> componente = t.sccs;
//=====================================================================================
class TarjanSCC {
public:
    int n;
    vector<vector<int>> adj;
    vector<int> disc, low, stiva;
    vector<bool> inStack;
    int timp;
    vector<vector<int>> sccs;

    TarjanSCC(int n) : n(n) {
        adj.resize(n);
        disc.resize(n, -1);
        low.resize(n, -1);
        inStack.resize(n, false);
        timp = 0;
    }

    void adaugaMuchie(int u, int v) {
        adj[u].push_back(v);
    }

    void tarjanDFS(int u) {
        disc[u] = low[u] = timp++;
        stiva.push_back(u);
        inStack[u] = true;

        for(auto &v : adj[u]) {
            if(disc[v] == -1) {
                tarjanDFS(v);
                low[u] = min(low[u], low[v]);
            } else if(inStack[v]) {
                low[u] = min(low[u], disc[v]);
            }
        }

        if(low[u] == disc[u]) {
            vector<int> comp;
            while(true) {
                int node = stiva.back();
                stiva.pop_back();
                inStack[node] = false;
                comp.push_back(node);
                if(node == u) break;
            }
            sccs.push_back(comp);
        }
    }

    void buildSCCs() {
        for(int i = 0; i < n; i++) {
            if(disc[i] == -1) {
                tarjanDFS(i);
            }
        }
    }
};

//=====================================================================================
// 4. verificare bipartit (graf neorientat) - bfs/dfs
// usage example (vrei sa vezi daca graful e bipartit?):
// vector<vector<int>> adj(4);
// adj[0] = {1};
// adj[1] = {0,2};
// bool e_ok = bipartit_check(adj);
//=====================================================================================
bool bipartit_check(const vector<vector<int>> &adj) {
    int n = (int)adj.size();
    vector<int> color(n, -1);

    for(int start = 0; start < n; start++) {
        if(color[start] == -1) {
            queue<int> q;
            color[start] = 0;
            q.push(start);
            while(!q.empty()) {
                int u = q.front();
                q.pop();
                for(auto &v : adj[u]) {
                    if(color[v] == -1) {
                        color[v] = 1 - color[u];
                        q.push(v);
                    } else if(color[v] == color[u]) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

//=====================================================================================
// 5. euler path/circuit (hierholzer) - pentru graf neorientat eulerian
// usage example (bai stapane, daca graful tau are toate gradele pare, poti sa faci asa):
// vector<vector<int>> adj(3);
// adj[0] = {1,2};
// adj[1] = {0,2};
// adj[2] = {0,1};
// vector<int> circuit = eulerian_circuit(adj);
//=====================================================================================
vector<int> eulerian_circuit(vector<vector<int>> &adj) {
    vector<int> circuit;
    stack<int> st;
    st.push(0);
    while(!st.empty()) {
        int u = st.top();
        if(!adj[u].empty()) {
            int v = adj[u].back();
            adj[u].pop_back();
            st.push(v);
        } else {
            circuit.push_back(u);
            st.pop();
        }
    }
    return circuit;
}

//=====================================================================================
// 6. edmond-karp (max flow) - o(v*e^2)
// usage example (cand vrei flux maxim, bossule):
// vector<vector<int>> capacity = {{0,10,0},{0,0,5},{0,0,0}};
// int mf = edmond_karp(capacity, 0, 2);
//=====================================================================================
int edmond_karp(vector<vector<int>> capacity, int source, int sink) {
    int n = capacity.size();
    vector<vector<int>> flow(n, vector<int>(n, 0));
    int max_flow = 0;

    while(true) {
        vector<int> parent(n, -1);
        parent[source] = source;
        queue<int> q;
        q.push(source);

        while(!q.empty() && parent[sink] == -1) {
            int u = q.front();
            q.pop();
            for(int v = 0; v < n; v++) {
                if(capacity[u][v] - flow[u][v] > 0 && parent[v] == -1) {
                    parent[v] = u;
                    q.push(v);
                }
            }
        }

        if(parent[sink] == -1) break;

        int augment = INT_MAX;
        int v = sink;
        while(v != source) {
            int u = parent[v];
            augment = min(augment, capacity[u][v] - flow[u][v]);
            v = u;
        }
        v = sink;
        while(v != source) {
            int u = parent[v];
            flow[u][v] += augment;
            flow[v][u] -= augment;
            v = u;
        }
        max_flow += augment;
    }

    return max_flow;
}

//=====================================================================================
// 7. mst: prim, kruskal (pe un graf neorientat cu costuri)
// usage example (n-ai bani multi, deci vrei cost minim?):
// graf_neorientat g(4);
// g.adauga_muchie(0,1,5);
// g.adauga_muchie(1,2,3);
// int cost_prim = g.prim();
// int cost_kruskal = g.kruskal();
//=====================================================================================
class graf_neorientat {
private:
    int n;
    vector<vector<pair<int,int>>> adj;
public:
    graf_neorientat(int n) : n(n) {
        adj.resize(n);
    }

    void adauga_muchie(int u, int v, int cost) {
        adj[u].push_back({v, cost});
        adj[v].push_back({u, cost});
    }

    // prim
    int prim(int start = 0) {
        vector<int> viz(n, 0);
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        pq.push({0, start});
        int total_cost = 0;

        while(!pq.empty()) {
            auto [c, node] = pq.top();
            pq.pop();
            if(viz[node]) continue;
            viz[node] = 1;
            total_cost += c;
            for(auto &ed : adj[node]) {
                if(!viz[ed.first]) {
                    pq.push({ed.second, ed.first});
                }
            }
        }
        return total_cost;
    }

    // kruskal
    struct dsu {
        vector<int> par, rnk;
        dsu(int n) : par(n), rnk(n, 0) {
            for(int i = 0; i < n; i++) par[i] = i;
        }
        int find(int x) {
            if(par[x] == x) return x;
            return par[x] = find(par[x]);
        }
        bool unite(int a, int b) {
            a = find(a);
            b = find(b);
            if(a == b) return false;
            if(rnk[a] < rnk[b]) swap(a, b);
            par[b] = a;
            if(rnk[a] == rnk[b]) rnk[a]++;
            return true;
        }
    };

    int kruskal() {
        vector<tuple<int,int,int>> edges;
        for(int u = 0; u < n; u++) {
            for(auto &p : adj[u]) {
                int v = p.first;
                int c = p.second;
                if(u < v) {
                    edges.push_back({c, u, v});
                }
            }
        }
        sort(edges.begin(), edges.end(),
            [](auto &a, auto &b) { return get<0>(a) < get<0>(b); });
        dsu d(n);
        int total_cost = 0;
        for(auto &e : edges) {
            int c, u, v;
            tie(c, u, v) = e;
            if(d.unite(u, v)) {
                total_cost += c;
            }
        }
        return total_cost;
    }

    vector<vector<pair<int,int>>> getAdj() {
        return adj;
    }

    // cate varfuri (minim) sunt intre nodurile nod1 si nod2
    // usage example (daca vrei distanta in numar de noduri intre 2 capete):
    // unsigned dist = g.distanta_dintre_noduri(0,2);
    unsigned distanta_dintre_noduri(unsigned nod1, unsigned nod2) {
        unsigned distanta = 0;
        vector<int> viz(n, 0);
        queue<pair<int, int>> q;
        q.push({nod1, 0});
        viz[nod1] = 1;
        while(!q.empty()) {
            auto [nod, dist] = q.front();
            q.pop();
            if(nod == (int)nod2) {
                distanta = dist;
                break;
            }
            for(auto &vecin : adj[nod]) {
                if(!viz[vecin.first]) {
                    viz[vecin.first] = 1;
                    q.push({vecin.first, dist + 1});
                }
            }
        }
        return distanta;
    }
};

//=====================================================================================
// 8. dijkstra - o(e log v)
// usage example (te dai barosan si vrei cea mai scurta distanta dintr-un nod spre rest?):
// vector<vector<pair<int,int>>> adj(5);
// adj[0].push_back({1,10});
// vector<int> distante = dijkstra(adj, 0);
//=====================================================================================
vector<int> dijkstra(const vector<vector<pair<int,int>>> &adj, int start) {
    int n = adj.size();
    vector<int> dist(n, INT_MAX);
    dist[start] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0, start});

    while(!pq.empty()) {
        auto [cd, node] = pq.top();
        pq.pop();
        if(cd > dist[node]) continue;
        for(auto &edge : adj[node]) {
            int vecin = edge.first;
            int cost = edge.second;
            if(dist[node] + cost < dist[vecin]) {
                dist[vecin] = dist[node] + cost;
                pq.push({dist[vecin], vecin});
            }
        }
    }
    return dist;
}

//=====================================================================================
// 9. bellman-ford - o(v*e)
// usage example (cand ai costuri negative, da' nu cicluri negative):
// vector<tuple<int,int,int>> edges;
// edges.push_back({0,1,5});
// vector<int> d = bellman_ford(5, 0, edges);
//=====================================================================================
vector<int> bellman_ford(int n, int start, vector<tuple<int,int,int>> &edges) {
    vector<int> dist(n, INT_MAX);
    dist[start] = 0;
    for(int i = 0; i < n - 1; i++) {
        for(auto &e : edges) {
            int u, v, c;
            tie(u, v, c) = e;
            if(dist[u] != INT_MAX && dist[u] + c < dist[v]) {
                dist[v] = dist[u] + c;
            }
        }
    }
    return dist;
}

//=====================================================================================
// 10. floyd-warshall - o(v^3)
// usage example (vrei distantele intre toate perechile, boss):
// vector<vector<int>> mat = {{0,5,9999},{9999,0,2},{9999,9999,0}};
// floyd_warshall(mat);
//=====================================================================================
void floyd_warshall(vector<vector<int>> &mat) {
    int n = mat.size();
    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(mat[i][k] < INT_MAX && mat[k][j] < INT_MAX) {
                    mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
                }
            }
        }
    }
}

//=====================================================================================
// 11. levenshtein distance (edit distance)
// usage example (vrei sa vezi cate operatii difera doua stringuri):
// int d = levenshtein_distance("bai","ratoi");
//=====================================================================================
int levenshtein_distance(const string &s1, const string &s2) {
    int n = s1.size(), m = s2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for(int i = 0; i <= n; i++) dp[i][0] = i;
    for(int j = 0; j <= m; j++) dp[0][j] = j;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
            }
        }
    }
    return dp[n][m];
}

//=====================================================================================
// 12. sortari (mergesort, quicksort) si cautare binara
// usage example (cand vrei sa fii rapid si ordonat, stapane):
// vector<int> arr = {3,1,2};
// merge_sort(arr, 0, arr.size()-1);
// int pos = binary_search_custom(arr, 2);
//=====================================================================================
void merge_sort(vector<int> &arr, int left, int right) {
    if(left >= right) return;
    int mid = (left + right) / 2;
    merge_sort(arr, left, mid);
    merge_sort(arr, mid + 1, right);

    vector<int> temp;
    int i = left, j = mid + 1;
    while(i <= mid && j <= right) {
        if(arr[i] < arr[j]) temp.push_back(arr[i++]);
        else temp.push_back(arr[j++]);
    }
    while(i <= mid) temp.push_back(arr[i++]);
    while(j <= right) temp.push_back(arr[j++]);

    for(int k = left; k <= right; k++) {
        arr[k] = temp[k - left];
    }
}

int partition_qs(vector<int> &arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for(int j = low; j < high; j++) {
        if(arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quicksort(vector<int> &arr, int low, int high) {
    if(low < high) {
        int pi = partition_qs(arr, low, high);
        quicksort(arr, low, pi - 1);
        quicksort(arr, pi + 1, high);
    }
}

int binary_search_custom(const vector<int> &arr, int val) {
    int left = 0, right = (int)arr.size() - 1;
    while(left <= right) {
        int mid = (left + right) / 2;
        if(arr[mid] == val) return mid;
        else if(arr[mid] < val) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

//=====================================================================================
// 13. verificare graf hamiltonian
// usage example (vrei sa vezi daca exista un drum care trece prin toate nodurile):
// vector<vector<int>> adj = {{0,1},{1,0}};
// bool e_hamil = hasHamiltonianPath(adj);
//=====================================================================================
bool hasHamiltonianPath(const vector<vector<int>> &adj) {
    int n = (int)adj.size();
    vector<vector<bool>> dp(1 << n, vector<bool>(n, false));

    for(int v = 0; v < n; v++){
        dp[1 << v][v] = true;
    }

    for(int mask = 0; mask < (1 << n); mask++){
        for(int v = 0; v < n; v++){
            if(!dp[mask][v]) continue;
            for(int next = 0; next < n; next++){
                if(!(mask & (1 << next)) && adj[v][next] == 1) {
                    int nextMask = mask | (1 << next);
                    dp[nextMask][next] = true;
                }
            }
        }
    }

    int fullMask = (1 << n) - 1;
    for(int v = 0; v < n; v++){
        if(dp[fullMask][v]) {
            return true;
        }
    }
    return false;
}

//=====================================================================================
// 14. verificare daca e arbore (graf neorientat conex fara cicluri)
// usage example (bagi un graf si vrei sa stii daca e copac?):
// vector<vector<int>> adj(3);
// adj[0] = {1};
// adj[1] = {0,2};
// bool e_arb = isTree(adj);
//=====================================================================================
bool isTree(const vector<vector<int>> &adj) {
    int n = (int)adj.size();
    vector<int> viz(n, 0);

    function<bool(int,int)> dfs = [&](int node, int parent) {
        viz[node] = 1;
        for(auto &vecin : adj[node]) {
            if(viz[vecin] == 0) {
                if(dfs(vecin, node) == false) return false;
            } else if(vecin != parent) {
                return false;
            }
        }
        return true;
    };

    if(dfs(0, -1) == false) return false;
    for(int i = 0; i < n; i++){
        if(viz[i] == 0) return false;
    }
    return true;
}

//=====================================================================================
// 15. lowest common ancestor (lca)
// usage example (cauti stramosul comun, stapane?):
// vector<vector<int>> adj(4);
// adj[0].push_back(1);
// lca l(4, adj, 0);
// int ancestor = l.get_lca(1,2);
//=====================================================================================
class LCA {
public:
    int n, LOG;
    vector<vector<int>> up;
    vector<int> depth;

    LCA(int n, vector<vector<int>> &adj, int root = 0) : n(n) {
        LOG = log2(n) + 1;
        up.assign(n, vector<int>(LOG, -1));
        depth.assign(n, 0);
        dfs(root, -1, adj);
    }

    void dfs(int node, int parent, vector<vector<int>> &adj) {
        up[node][0] = parent;
        for(int i = 1; i < LOG; i++) {
            if(up[node][i - 1] != -1)
                up[node][i] = up[up[node][i - 1]][i - 1];
        }
        for(int v : adj[node]) {
            if(v != parent) {
                depth[v] = depth[node] + 1;
                dfs(v, node, adj);
            }
        }
    }

    int get_lca(int u, int v) {
        if(depth[u] < depth[v]) swap(u, v);
        for(int i = LOG - 1; i >= 0; i--) {
            if(up[u][i] != -1 && depth[up[u][i]] >= depth[v])
                u = up[u][i];
        }
        if(u == v) return u;
        for(int i = LOG - 1; i >= 0; i--) {
            if(up[u][i] != up[v][i]) {
                u = up[u][i];
                v = up[v][i];
            }
        }
        return up[u][0];
    }
};

//=====================================================================================
// 16. centroid decomposition
// usage example (cand vrei sa faci chestii avansate pe arbore, bosule):
// vector<vector<int>> adj(5);
// centroiddecomposition cd(5, adj);
//=====================================================================================
class CentroidDecomposition {
public:
    int n;
    vector<vector<int>> adj, tree;
    vector<int> subtree;
    vector<bool> removed;

    CentroidDecomposition(int n, vector<vector<int>> &adj) : n(n), adj(adj) {
        tree.resize(n);
        removed.assign(n, false);
        subtree.assign(n, 0);
        build(0, -1);
    }

    int find_centroid(int node, int parent, int size) {
        for(int v : adj[node]) {
            if(v != parent && !removed[v] && subtree[v] > size / 2)
                return find_centroid(v, node, size);
        }
        return node;
    }

    void calc_subtree(int node, int parent) {
        subtree[node] = 1;
        for(int v : adj[node]) {
            if(v != parent && !removed[v]) {
                calc_subtree(v, node);
                subtree[node] += subtree[v];
            }
        }
    }

    void build(int node, int parent) {
        calc_subtree(node, -1);
        int centroid = find_centroid(node, -1, subtree[node]);
        removed[centroid] = true;
        if(parent != -1) tree[parent].push_back(centroid);
        for(int v : adj[centroid]) {
            if(!removed[v]) build(v, centroid);
        }
        removed[centroid] = false;
    }
};

//=====================================================================================
// 17. heavy-light decomposition (hld) - implementare completa
// usage example (daca vrei query de tip sum pe un arbore, de exemplu):
// heavylightdecomposition hld(n);
// - initializezi cu add edge
// hld.init(0); // root = 0
// hld.build_segment_tree();
// hld.update(u, val); // update un nod
// int ans = hld.query(u,v); // query pe drumul dintre u si v
//=====================================================================================
struct segtree_hld {
    int n;
    vector<int> st;
    segtree_hld(int n) : n(n) {
        st.resize(4*n, 0);
    }
    void build(vector<int> &vals, int idx, int left, int right) {
        if(left == right) {
            st[idx] = vals[left];
            return;
        }
        int mid = (left+right)/2;
        build(vals, idx*2, left, mid);
        build(vals, idx*2+1, mid+1, right);
        st[idx] = st[idx*2] + st[idx*2+1];
    }
    void update(int idx, int left, int right, int pos, int val) {
        if(left == right) {
            st[idx] = val;
            return;
        }
        int mid = (left+right)/2;
        if(pos <= mid) update(idx*2,left,mid,pos,val);
        else update(idx*2+1,mid+1,right,pos,val);
        st[idx] = st[idx*2] + st[idx*2+1];
    }
    int query(int idx, int left, int right, int ql, int qr) {
        if(ql>qr || ql>right || qr<left) return 0;
        if(ql<=left && right<=qr) return st[idx];
        int mid=(left+right)/2;
        return query(idx*2,left,mid,ql,qr) + query(idx*2+1,mid+1,right,ql,qr);
    }
};

class HeavyLightDecomposition {
public:
    int n;
    vector<vector<int>> adj;
    vector<int> parent, depth, heavy, size, head, pos;
    vector<int> base_array; 
    segtree_hld *seg; 
    int curPos;

    HeavyLightDecomposition(int n) : n(n) {
        adj.resize(n);
        parent.resize(n);
        depth.resize(n);
        heavy.resize(n, -1);
        size.resize(n, 0);
        head.resize(n);
        pos.resize(n);
        curPos = 0;
    }

    void add_edge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int dfs(int u, int p) {
        parent[u] = p;
        size[u] = 1;
        int mx=-1;
        for(auto &v : adj[u]) {
            if(v == p) continue;
            depth[v] = depth[u] + 1;
            int sz = dfs(v,u);
            if(sz>mx) {
                mx=sz;
                heavy[u] = v;
            }
            size[u]+=sz;
        }
        return size[u];
    }

    void decompose(int u, int h) {
        head[u] = h;
        pos[u] = curPos++;
        base_array[pos[u]] = 0; // if you want to store initial node values, place them here
        if(heavy[u] != -1) {
            decompose(heavy[u], h);
        }
        for(auto &v : adj[u]) {
            if(v==parent[u] || v==heavy[u]) continue;
            decompose(v,v);
        }
    }

    void init(int root) {
        dfs(root,-1);
        base_array.resize(n,0);
        decompose(root,root);
    }

    void build_segment_tree() {
        seg = new segtree_hld(n);
        seg->build(base_array,1,0,n-1);
    }

    void update(int u, int val) {
        int idx = pos[u];
        seg->update(1,0,n-1,idx,val);
    }

    int query_path(int u, int v) {
        int res = 0;
        while(head[u] != head[v]) {
            if(depth[head[u]] > depth[head[v]]) swap(u,v);
            res += seg->query(1,0,n-1,pos[head[v]], pos[v]);
            v = parent[head[v]];
        }
        if(depth[u] > depth[v]) swap(u,v);
        res += seg->query(1,0,n-1,pos[u],pos[v]);
        return res;
    }

    int query(int u, int v) {
        return query_path(u,v);
    }
};

//=====================================================================================
// 18. fenwick tree (bit)
// usage example (vrei update si query rapid pe sume?):
// fenwicktree ft(10);
// ft.update(1,5);
// int s = ft.range_sum(1,3);
//=====================================================================================
class FenwickTree {
    vector<int> bit;
    int n;
public:
    FenwickTree(int n) : n(n) {
        bit.assign(n + 1, 0);
    }

    void update(int idx, int delta) {
        for(; idx <= n; idx += idx & -idx)
            bit[idx] += delta;
    }

    int sum(int idx) {
        int s = 0;
        for(; idx > 0; idx -= idx & -idx)
            s += bit[idx];
        return s;
    }

    int range_sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
};

//=====================================================================================
// 19. segment tree (completa)
// usage example (cand ai intervale si vrei query/update smecher, stapane):
// segmenttree st(n);
// st.build(arr,1,0,n-1);
// st.update(1,0,n-1,idx,val);
// int rez = st.query(1,0,n-1,l,r);
//=====================================================================================
class SegmentTree {
public:
    int n;
    vector<int> tree;
    SegmentTree(int n) : n(n) {
        tree.resize(4*n, 0);
    }

    void build(vector<int> &arr, int idx, int start, int end) {
        if(start == end) {
            tree[idx] = arr[start];
            return;
        }
        int mid = (start+end)/2;
        build(arr, idx*2, start, mid);
        build(arr, idx*2+1, mid+1, end);
        tree[idx] = tree[idx*2] + tree[idx*2+1];
    }

    void update(int idx, int start, int end, int pos, int val) {
        if(start == end) {
            tree[idx] = val;
            return;
        }
        int mid = (start+end)/2;
        if(pos <= mid) update(idx*2, start, mid, pos, val);
        else update(idx*2+1, mid+1, end, pos, val);
        tree[idx] = tree[idx*2] + tree[idx*2+1];
    }

    int query(int idx, int start, int end, int left, int right) {
        if(left>right || left> end || right<start) return 0;
        if(left<=start && end<=right) {
            return tree[idx];
        }
        int mid = (start+end)/2;
        int q1 = query(idx*2, start, mid, left, right);
        int q2 = query(idx*2+1, mid+1, end, left, right);
        return q1 + q2;
    }
};

//=====================================================================================
// 20. treap / avl tree / splay tree - exemple minimaliste
// usage example (cand vrei structuri de date mai avansate, stapane):
// ai trei clase: treap, avl, splay. le folosesti cum vrei tu, boss
//=====================================================================================

//-------------------------------------------------------------------------------------
// treap implementation (inserare + cautare)
//-------------------------------------------------------------------------------------
struct TreapNode {
    int key, priority;
    TreapNode* left;
    TreapNode* right;
    TreapNode(int key) : key(key), priority(rand()), left(nullptr), right(nullptr) {}
};

class Treap {
public:
    TreapNode* root;
    Treap() : root(nullptr) {}

    TreapNode* rotateRight(TreapNode* y) {
        TreapNode* x = y->left;
        TreapNode* t2 = x->right;
        x->right = y;
        y->left = t2;
        return x;
    }

    TreapNode* rotateLeft(TreapNode* x) {
        TreapNode* y = x->right;
        TreapNode* t2 = y->left;
        y->left = x;
        x->right = t2;
        return y;
    }

    TreapNode* insertNode(TreapNode* node, int key) {
        if(!node) return new TreapNode(key);
        if(key < node->key) {
            node->left = insertNode(node->left, key);
            if(node->left->priority > node->priority) {
                node = rotateRight(node);
            }
        } else {
            node->right = insertNode(node->right, key);
            if(node->right->priority > node->priority) {
                node = rotateLeft(node);
            }
        }
        return node;
    }

    void insertKey(int key) {
        root = insertNode(root, key);
    }

    bool searchNode(TreapNode* node, int key) {
        if(!node) return false;
        if(node->key == key) return true;
        if(key < node->key) return searchNode(node->left, key);
        return searchNode(node->right, key);
    }

    bool searchKey(int key) {
        return searchNode(root, key);
    }
};

//-------------------------------------------------------------------------------------
// avl tree implementation (inserare + cautare)
//-------------------------------------------------------------------------------------
struct AVLNode {
    int key;
    AVLNode* left;
    AVLNode* right;
    int height;
    AVLNode(int key) : key(key), left(nullptr), right(nullptr), height(1) {}
};

class AVL {
public:
    AVLNode* root;
    AVL() : root(nullptr) {}

    int getHeight(AVLNode* node) {
        return (node ? node->height : 0);
    }

    int getBalance(AVLNode* node) {
        if(!node) return 0;
        return getHeight(node->left) - getHeight(node->right);
    }

    AVLNode* rotateRight(AVLNode* y) {
        AVLNode* x = y->left;
        AVLNode* t2 = x->right;
        x->right = y;
        y->left = t2;
        y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
        x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
        return x;
    }

    AVLNode* rotateLeft(AVLNode* x) {
        AVLNode* y = x->right;
        AVLNode* t2 = y->left;
        y->left = x;
        x->right = t2;
        x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
        y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
        return y;
    }

    AVLNode* insertNode(AVLNode* node, int key) {
        if(!node) return new AVLNode(key);
        if(key < node->key) node->left = insertNode(node->left, key);
        else node->right = insertNode(node->right, key);

        node->height = 1 + max(getHeight(node->left), getHeight(node->right));
        int balance = getBalance(node);

        // left left
        if(balance > 1 && key < node->left->key) {
            return rotateRight(node);
        }
        // right right
        if(balance < -1 && key > node->right->key) {
            return rotateLeft(node);
        }
        // left right
        if(balance > 1 && key > node->left->key) {
            node->left = rotateLeft(node->left);
            return rotateRight(node);
        }
        // right left
        if(balance < -1 && key < node->right->key) {
            node->right = rotateRight(node->right);
            return rotateLeft(node);
        }
        return node;
    }

    void insertKey(int key) {
        root = insertNode(root, key);
    }

    bool searchNode(AVLNode* node, int key) {
        if(!node) return false;
        if(node->key == key) return true;
        if(key < node->key) return searchNode(node->left, key);
        else return searchNode(node->right, key);
    }

    bool searchKey(int key) {
        return searchNode(root, key);
    }
};

//-------------------------------------------------------------------------------------
// splay tree implementation (inserare + cautare + splay)
//-------------------------------------------------------------------------------------
struct SplayNode {
    int key;
    SplayNode* left;
    SplayNode* right;
    SplayNode(int key) : key(key), left(nullptr), right(nullptr) {}
};

class SplayTree {
public:
    SplayNode* root;
    SplayTree() : root(nullptr) {}

    SplayNode* rightRotate(SplayNode* x) {
        SplayNode* y = x->left;
        x->left = y->right;
        y->right = x;
        return y;
    }

    SplayNode* leftRotate(SplayNode* x) {
        SplayNode* y = x->right;
        x->right = y->left;
        y->left = x;
        return y;
    }

    // splay operation: bring key to root
    SplayNode* splay(SplayNode* root, int key) {
        if(!root || root->key == key) return root;

        // key < root->key
        if(key < root->key) {
            if(!root->left) return root;
            // zig-zig
            if(key < root->left->key) {
                root->left->left = splay(root->left->left, key);
                root = rightRotate(root);
            }
            // zig-zag
            else if(key > root->left->key) {
                root->left->right = splay(root->left->right, key);
                if(root->left->right) {
                    root->left = leftRotate(root->left);
                }
            }
            return (!root->left) ? root : rightRotate(root);
        }
        else {
            if(!root->right) return root;
            // zig-zig
            if(key > root->right->key) {
                root->right->right = splay(root->right->right, key);
                root = leftRotate(root);
            }
            // zig-zag
            else if(key < root->right->key) {
                root->right->left = splay(root->right->left, key);
                if(root->right->left) {
                    root->right = rightRotate(root->right);
                }
            }
            return (!root->right) ? root : leftRotate(root);
        }
    }

    SplayNode* insertNode(SplayNode* root, int key) {
        if(!root) return new SplayNode(key);
        root = splay(root, key);
        if(root->key == key) return root; 
        SplayNode* newNode = new SplayNode(key);
        if(key < root->key) {
            newNode->right = root;
            newNode->left = root->left;
            root->left = nullptr;
        } else {
            newNode->left = root;
            newNode->right = root->right;
            root->right = nullptr;
        }
        return newNode;
    }

    void insertKey(int key) {
        root = insertNode(root, key);
    }

    bool searchKey(int key) {
        root = splay(root, key);
        return (root && root->key == key);
    }
};

#endif // CHEATSHEET_H

// exemplu minimal in main, daca vrei sa testezi ceva:
int main() {


}