other_algorithms/test/doubling.yuki3305.test.cpp

• View this file on GitHub
• Last update: 2025-10-07 09:40:50+09:00
• Problem: https://yukicoder.me/problems/no/3305

Depends on

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

Code

#define PROBLEM "https://yukicoder.me/problems/no/3305"
#include "../doubling.hpp"

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for (auto &a : A) cin >> a;

    vector<int> nexts(N, N);

    vector<pair<int, int>> st;
    st.emplace_back(N, N);
    for (int i = N - 1; i >= 0; --i) {
        while (st.back().first < A.at(i)) st.pop_back();
        nexts.at(i) = st.back().second;
        st.emplace_back(A.at(i), i);
    }

    const BinaryLifting binary_lifting(nexts);

    while (Q--) {
        int l, r;
        cin >> l >> r;
        --l;
        cout << r - l - binary_lifting.distance(l, r) << '\n';
    }
}

#line 1 "other_algorithms/test/doubling.yuki3305.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/3305"
#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
        }
    }
};
#line 3 "other_algorithms/test/doubling.yuki3305.test.cpp"

#include <iostream>
#include <utility>
#line 7 "other_algorithms/test/doubling.yuki3305.test.cpp"
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for (auto &a : A) cin >> a;

    vector<int> nexts(N, N);

    vector<pair<int, int>> st;
    st.emplace_back(N, N);
    for (int i = N - 1; i >= 0; --i) {
        while (st.back().first < A.at(i)) st.pop_back();
        nexts.at(i) = st.back().second;
        st.emplace_back(A.at(i), i);
    }

    const BinaryLifting binary_lifting(nexts);

    while (Q--) {
        int l, r;
        cin >> l >> r;
        --l;
        cout << r - l - binary_lifting.distance(l, r) << '\n';
    }
}

Back to top page