# 競プロで使えそうなライブラリ・手法(上級者向け)

## 多倍長数

boostライブラリの多倍長整数のテンプレート

boostが無いと使用不可

PCKでboostが使えるかは知らない

あとC++の多倍長整数は計算速度が遅いことに注意

#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
using Bint = cpp_int;//任意長整数
using Real32 = number<cpp_dec_float<32>>;//仮数部が32桁の浮動小数

## UnionFind木

頂点の連結判定や，木の結合，閉路検知を$O(α(N))$(ただし，$α(N)$は逆アッカーマン関数)で行えるデータ構造

UnionFind uf(N); 頂点数Nで宣言

uf.root(x); 頂点xの親ノードを返す

uf.same(x,y); xとyが同じ木の中にあるかをboolで返す

uf.unite(x,y); xの木とyの木を結合させる

uf.size(); 連結成分の数を返す

uf.v_size(x): xの木の頂点数を返す

uf.Ancestor(); それぞれの木の親を返す

class UnionFind {
  private:
    int N;
    int num;
    vector<int> par;
    vector<int> rank;
    vector<int> depth;
    unordered_set<int> ancestor;

  public:
    UnionFind(int n) {
        num = n;
        par.resize(n);
        rank.resize(n, 0);
        depth.resize(n, 1);
        for (int i = 0; i < n; i++) {
            par[i] = i;
            ancestor.insert(i);
        }
    }

    int root(int x) {
        return par[x] == x ? x : par[x] = root(par[x]);
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }

    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y)
            return false;
        if (rank[x] < rank[y]) {
            par[x] = y;
            depth[y] += depth[x];
            ancestor.erase(x);
        }
        else {
            if (rank[x] == rank[y]) {
                rank[x]++;
            }
            par[y] = x;
            depth[x] += depth[y];
            ancestor.erase(y);
        }
        num--;
        return true;
    }

    int size() {
        return num;
    }

    int v_size(int x) {
        return depth[x];
    }

    unordered_set<int> Ancestor() {
        return ancestor;
    }
};

## ダイクストラ法

グラフの最短経路を求めるのに使える

計算量は$O(E\log V)$ (Eは辺の数，Vは頂点の数)

//頂点のクラス
class node
{
public:
    int cost = 2147483647;
    vector<pair<int, int>> to_v;
    bool dis = false;
};

// 始点から各頂点へ移動した場合の最小コストが格納された配列を返す
// mode:0 無向辺 , mode:1 有向辺
// V:頂点数 , a,b:a から b へつながる辺 , c:cost , S:始点の頂点番号
template <typename T>
vector<node> dijkstra(T V, vector<T> &a, vector<T> &b, vector<T> &c, T S, int mode)
{
    vector<node> Graph(V);
    for (ll i = 0; i < a.size(); i++)
    {
        Graph[a[i]].to_v.push_back(make_pair(b[i], c[i]));
        if (mode == 0)
        {
            Graph[b[i]].to_v.push_back(make_pair(a[i], c[i]));
        }
    }
    Graph[S].cost = 0;
    Graph[S].dis = true;
    priority_queue<pair<T, T>, vector<pair<T, T>>, greater<pair<T, T>>> q;
    q.push(make_pair(0, S));
    while (!q.empty())
    {
        Graph[q.top().second].dis = true;
        for (pair<int, int> x : Graph[q.top().second].to_v)
        {
            if (!Graph[x.first].dis)
            {
                Graph[x.first].cost = min(Graph[x.first].cost, q.top().first + x.second);
                q.push(make_pair(Graph[x.first].cost, x.first));
            }
        }
        q.pop();
    }
    return Graph;
}

## 遅延伝搬セグメントツリー

[セグメント木を徹底解説！0から遅延評価やモノイドまで](https://algo-logic.info/segment-tree/)からコードを引っ張ってきた

ちなみにこれはRMQ(区間内の最小の値を取得するクエリ)のセグ木である

/* RMQ：[0,n-1] について、区間ごとの最小値を管理する構造体
    set(int i, T x), build(): i番目の要素をxにセット。まとめてセグ木を構築する。O(n)
    update(i,x): i 番目の要素を x に更新。O(log(n))
    query(a,b): [a,b) での最小の要素を取得。O(log(n))
    find_rightest(a,b,x): [a,b) で x以下の要素を持つ最右位置を求める。O(log(n))
    find_leftest(a,b,x): [a,b) で x以下の要素を持つ最左位置を求める。O(log(n))
*/
template <typename T>
struct RMQ {
    const T e = numeric_limits<T>::max();
    function<T(T, T)> fx = [](T x1, T x2) -> T { return min(x1, x2); };
    int n;
    vector<T> dat;
    RMQ(int n_) : n(), dat(n_ * 4, e) {
        int x = 1;
        while (n_ > x) {
            x *= 2;
        }
        n = x;
    }

    void set(int i, T x) { dat[i + n - 1] = x; }
    void build() {
        for (int k = n - 2; k >= 0; k--) dat[k] = fx(dat[2 * k + 1], dat[2 * k + 2]);
    }

    void update(int i, T x) {
        i += n - 1;
        dat[i] = x;
        while (i > 0) {
            i = (i - 1) / 2;  // parent
            dat[i] = fx(dat[i * 2 + 1], dat[i * 2 + 2]);
        }
    }

    // the minimum element of [a,b)
    T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
    T query_sub(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) {
            return e;
        } else if (a <= l && r <= b) {
            return dat[k];
        } else {
            T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return fx(vl, vr);
        }
    }

    int find_rightest(int a, int b, T x) { return find_rightest_sub(a, b, x, 0, 0, n); }
    int find_leftest(int a, int b, T x) { return find_leftest_sub(a, b, x, 0, 0, n); }
    int find_rightest_sub(int a, int b, T x, int k, int l, int r) {
        if (dat[k] > x || r <= a || b <= l) {  // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn a-1
            return a - 1;
        } else if (k >= n - 1) {  // 自分が葉ならその位置をreturn
            return (k - (n - 1));
        } else {
            int vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
            if (vr != a - 1) {  // 右の部分木を見て a-1 以外ならreturn
                return vr;
            } else {  // 左の部分木を見て値をreturn
                return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
            }
        }
    }
    int find_leftest_sub(int a, int b, T x, int k, int l, int r) {
        if (dat[k] > x || r <= a || b <= l) {  // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn b
            return b;
        } else if (k >= n - 1) {  // 自分が葉ならその位置をreturn
            return (k - (n - 1));
        } else {
            int vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
            if (vl != b) {  // 左の部分木を見て b 以外ならreturn
                return vl;
            } else {  // 右の部分木を見て値をreturn
                return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
            }
        }
    }
};

## フェニック木(BIT)

[Binary Indexed Tree(フェニック木)](https://take44444.github.io/Algorithm-Book/range/bit/main.html)から引っ張ってきた

値更新可能な累積和

template <typename T>
struct BinaryIndexedTree {
  int n;
  vector<T> data;

  BinaryIndexedTree(int size) {
    n = ++size;
    data.assign(n, 0);
  }

  // get sum of [0,k]
  T sum(int k) const {
    if (k < 0) return 0;
    T ret = 0;
    for (++k; k > 0; k -= k&(-k)) ret += data[k];
    return ret;
  }

  // getsum of [l,r]
  inline T sum(int l, int r) const { return sum(r) - sum(l-1); }

  // data[k] += x
  void add(int k, T x) {
    for (++k; k < n; k += k&(-k)) data[k] += x;
  }

## 最小共通祖先(LCA)

[ダブリングによる木の最近共通祖先（LCA：Lowest Common Ancestor）を求めるアルゴリズム](https://algo-logic.info/lca/)から引っ張ってきた

最小共通祖先(頂点uと頂点vに共通する最初の親)を高速に求めるアルゴリズム

木上で任意の二点間の距離を高速に求めるときに使える

(u-v間距離=根からuまでの距離+根からvまでの距離-2\*根から最小共通祖先までの距離)

struct Edge {
    long long to;
};
using Graph = vector<vector<Edge>>;

/* LCA(G, root): 木 G に対する根を root として Lowest Common Ancestor を求める構造体
    query(u,v): u と v の LCA を求める。計算量 O(logn)
    前処理: O(nlogn)時間, O(nlogn)空間
*/
struct LCA {
    vector<vector<int>> parent;  // parent[k][u]:= u の 2^k 先の親
    vector<int> dist;            // root からの距離
    LCA(const Graph &G, int root = 0) { init(G, root); }

    // 初期化
    void init(const Graph &G, int root = 0) {
        int V = G.size();
        int K = 1;
        while ((1 << K) < V) K++;
        parent.assign(K, vector<int>(V, -1));
        dist.assign(V, -1);
        dfs(G, root, -1, 0);
        for (int k = 0; k + 1 < K; k++) {
            for (int v = 0; v < V; v++) {
                if (parent[k][v] < 0) {
                    parent[k + 1][v] = -1;
                } else {
                    parent[k + 1][v] = parent[k][parent[k][v]];
                }
            }
        }
    }

    // 根からの距離と1つ先の頂点を求める
    void dfs(const Graph &G, int v, int p, int d) {
        parent[0][v] = p;
        dist[v] = d;
        for (auto e : G[v]) {
            if (e.to != p) dfs(G, e.to, v, d + 1);
        }
    }

    int query(int u, int v) {
        if (dist[u] < dist[v]) swap(u, v);  // u の方が深いとする
        int K = parent.size();
        // LCA までの距離を同じにする
        for (int k = 0; k < K; k++) {
            if ((dist[u] - dist[v]) >> k & 1) {
                u = parent[k][u];
            }
        }
        // 二分探索で LCA を求める
        if (u == v) return u;
        for (int k = K - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
};

## 一般化された繰り返し二乗法

モノイドのN乗をO(MlogN) (Mは演算の計算量)で行える

T X : 演算対象

T op(T,T) : S×S→Sとなる二項演算の関数

T e() : 単位元

ll N : 何回演算を行うか

template <class T> T pow_t(T X, T (*op)(T, T), T (*e)(), ll N) {
    T ans = e();
    while(N) {
        if(N & 1) {
            ans = op(ans, X);
        }
        X = op(X, X);
        N >>= 1;
    }
    return ans;
}

使用例(行列のN乗)

template <class T> T pow_t(T X, T (*op)(T, T), T (*e)(), ll N) {
    T ans = e();
    while(N) {
        if(N & 1) {
            ans = op(ans, X);
        }
        X = op(X, X);
        N >>= 1;
    }
    return ans;
}

vector<vector<ll>> op(vector<vector<ll>> A, vector<vector<ll>> B) {
    ll H, W;
    H = A.size();
    W = B.size();
    vector<vector<ll>> C(H, vector<ll>(W, 0));
    for(ll i = 0; i < H; i++) {
        for(ll j = 0; j < W; j++) {
            for(ll k = 0; k < W; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return C;
}

ll sz = 2;

vector<vector<ll>> e() {
    vector<vector<ll>> e(sz, vector<ll>(sz, 0));
    rep(i, sz) { e[i][i] = 1; }
    return e;
}

int main() {
    ll N;
    cin >> N;
    sz = N;
    vector<vector<ll>> A(sz, vector<ll>(sz, 0));
    rep(i, N) {
        rep(j, N) { cin >> A[i][j]; }
    }
    ll B;
    cin >> B;
    A = pow_t(A, op, e, B);
    rep(i, N) {
        rep(j, N) { cout << A[i][j] << " "; }
        cout << endl;
    }
    return 0;
}

## 座標圧縮版1次元累積和

巨大かつ疎な配列に対する累積和を取ることができるデータ構造

普通の累積和と比べて計算量は落ちているがlogがつくだけなため、Atcoderではほぼ完全上位互換

verify:https://judge.yosupo.jp/submission/170035 https://atcoder.jp/contests/abc326/submissions/me

// 座標圧縮版の累積和
// [l,r)の範囲の総和をO(logN)で求められる
// 前計算O(NlogN),クエリの処理O(logN)
template<class T>
class cumulative_sum {
  private:
    map<long long,T> v;
    long long Max = numeric_limits<long long>::max();
    long long Min = numeric_limits<long long>::min();
  public:
    cumulative_sum() {
        v[Max] = 0;
        v[Min] = 0;
    }
    cumulative_sum(map<long long,T> &m) {
        for(auto x:m){
            v[x.first] = x.second;
        }
        v[Max] = 0;
        v[Min] = 0;
    }
    // v[idx]にxを代入
    // O(logN)
    void set(long long idx, T x) {
        v[idx] = x;
    }

    // v[idx]にxを加算
    // O(logN)
    void add(long long idx,T x){
        v[idx] += x;
    }
    // v[idx]を削除
    //O(logN)
    void erase(long long idx){
        v.erase(idx);
    }
    // 累積和を構築
    // O(NlogN)
    void build() {
        auto itr = v.begin();
        auto itr2 = itr;
        itr2++;
        for(; itr2 != v.end(); itr++,itr2++)
            (*itr2).second += (*itr).second;
    }
    // [l,r)の総和を返す
    // O(logN)
    long long prod(long long l, long long r) { 
        auto itr = v.lower_bound(l);
        itr--;
        auto itr2 = v.lower_bound(r);
        itr2--;
        return (*itr2).second - (*itr).second;
    }

    T &operator[](long long i){return v[i];}
};