Binary lifting / doubling （ダブリング）
(other_algorithms/doubling.hpp)

• View this file on GitHub
• Last update: 2025-10-07 09:40:50+09:00
• Include: #include "other_algorithms/doubling.hpp"
• Link: https://atcoder.jp/contests/arc060/submissions/7039451

Functional graph 上のダブリングライブラリ． binary_lifting.hpp とは異なり辺に重みなどは載せられない．

使用方法

BinaryLifting binary_lifting(std::vector<int> to)

コンストラクタ．引数として $g(0), \ldots, g(n - 1)$ を与える．

直感的には，各頂点 $i = 0, \ldots, n - 1$ について $i$ から頂点 $g(i)$ へ有向辺が張られている functional graph に相当する． $g(i)$ の値は $0$ 未満や $n$ 以上でも構わない（下記の各関数は， $[0, n)$ の範囲外の頂点 $i$ からは $i$ 自身への重み $e$ の自己ループが生えている，と解釈するとつじつまが合うように設計されている）．

int kth_next(int s, long long k)

$g^k (s)$ の値（途中で $[0, n)$ の範囲外に出る場合はその値）を $O(\log k)$ で返す．

int distance(int l, int r)

$g^k (s)$ の値が初めて r 以上になる $k$ を計算する．この条件が満たされることはない場合は -1 を返す．

この条件に関する単調性が必要．

問題例

• No.3305 Shift Sort - yukicoder

Verified with

• other_algorithms/test/doubling.yuki3305.test.cpp

Code

#pragma once
#include <cassert>
#include <vector>

// Binary lifting / `Doubling`
// Complexity: O(NlogN) precalculation / O(logN) per query
// https://atcoder.jp/contests/arc060/submissions/7039451
struct BinaryLifting {
    int N, lgD;

    bool is_valid(int idx) const { return 0 <= idx and idx < N; }

    std::vector<std::vector<int>> mat;
    BinaryLifting() : N(0), lgD(0) {}
    BinaryLifting(const std::vector<int> &to, int lgd = 0) : N(to.size()), lgD(lgd) {
        while ((1LL << lgD) < N) lgD++;
        mat.assign(lgD, std::vector<int>(N));
        mat[0] = to;

        for (int d = 0; d < lgD - 1; d++) {
            for (int i = 0; i < N; i++) {
                mat[d + 1][i] = mat[d][is_valid(mat[d][i]) ? mat[d][i] : i];
            }
        }
    }

    int kth_next(int now, long long k) const {
        assert(k >= 0);
        assert(k < (1LL << lgD));
        for (int d = 0; k and is_valid(now); d++, k >>= 1) {
            if (k & 1) now = mat[d][now];
        }
        return now;
    }

    // Distance from l to [r, \infty)
    // Requirement: mat[0][i] >= r (i = r, r + 1, ...) (monotone)
    int distance(int l, int r) const {
        if (l >= r) return 0;
        int ret = 0;
        for (int d = lgD - 1; d >= 0; d--) {
            if (mat[d][l] < r and is_valid(mat[d][l])) ret += 1 << d, l = mat[d][l];
        }

        if (!is_valid(mat[0][l]) or mat[0][l] >= r) {
            return ret + 1;
        } else {
            return -1; // Unable to reach
        }
    }
};

#line 2 "other_algorithms/doubling.hpp"
#include <cassert>
#include <vector>

// Binary lifting / `Doubling`
// Complexity: O(NlogN) precalculation / O(logN) per query
// https://atcoder.jp/contests/arc060/submissions/7039451
struct BinaryLifting {
    int N, lgD;

    bool is_valid(int idx) const { return 0 <= idx and idx < N; }

    std::vector<std::vector<int>> mat;
    BinaryLifting() : N(0), lgD(0) {}
    BinaryLifting(const std::vector<int> &to, int lgd = 0) : N(to.size()), lgD(lgd) {
        while ((1LL << lgD) < N) lgD++;
        mat.assign(lgD, std::vector<int>(N));
        mat[0] = to;

        for (int d = 0; d < lgD - 1; d++) {
            for (int i = 0; i < N; i++) {
                mat[d + 1][i] = mat[d][is_valid(mat[d][i]) ? mat[d][i] : i];
            }
        }
    }

    int kth_next(int now, long long k) const {
        assert(k >= 0);
        assert(k < (1LL << lgD));
        for (int d = 0; k and is_valid(now); d++, k >>= 1) {
            if (k & 1) now = mat[d][now];
        }
        return now;
    }

    // Distance from l to [r, \infty)
    // Requirement: mat[0][i] >= r (i = r, r + 1, ...) (monotone)
    int distance(int l, int r) const {
        if (l >= r) return 0;
        int ret = 0;
        for (int d = lgD - 1; d >= 0; d--) {
            if (mat[d][l] < r and is_valid(mat[d][l])) ret += 1 << d, l = mat[d][l];
        }

        if (!is_valid(mat[0][l]) or mat[0][l] >= r) {
            return ret + 1;
        } else {
            return -1; // Unable to reach
        }
    }
};

Back to top page