val_range
(lib/others/val_range.hpp)

• View this file on GitHub
• Last update: 2024-05-04 18:06:16+09:00
• Include: #include "lib/others/val_range.hpp"

val_range

概要

要素数 $N$ の数列 $v$ において、以下のものが求められます。

$i : (0 \leq i \leq N - 1)$ について、 $\min(v_{l + 1}, …, v_{i - 1}, v_{i}) = v_i$ が成り立つ最小の $l$ と $\min(v_i, v_{i + 1}, …, v_{r - 1}) = v_i$ が成り立つ最大の $r$

引数における is_min = false とすれば、$\max$ についても同様に求められます。

計算量

$\mathrm{O}(N)$

Code

#pragma once

/**
 * @brief val_range
 * @docs docs/others/val_range.md
 */

 // 0-indexed, (l, i], [i, r)
template<typename T>
pair<vector<int>, vector<int>> val_range(const vector<T> &v, bool is_min){
    pair<vector<int>, vector<int>> res;
    int n = v.size();
    res.first.assign(n, -1);
    res.second.assign(n, n);
    stack<int> st;
    st.push(-1);
    for(int i = 0; i < n; ++i){
        while(st.top() != -1){
            if(is_min ^ (v[st.top()] < v[i])){
                res.second[st.top()] = i;
                st.pop();
            } else{
                break;
            }
        }
        res.first[i] = st.top();
        st.push(i);
    }
    return res;
}

#line 2 "lib/others/val_range.hpp"

/**
 * @brief val_range
 * @docs docs/others/val_range.md
 */

 // 0-indexed, (l, i], [i, r)
template<typename T>
pair<vector<int>, vector<int>> val_range(const vector<T> &v, bool is_min){
    pair<vector<int>, vector<int>> res;
    int n = v.size();
    res.first.assign(n, -1);
    res.second.assign(n, n);
    stack<int> st;
    st.push(-1);
    for(int i = 0; i < n; ++i){
        while(st.top() != -1){
            if(is_min ^ (v[st.top()] < v[i])){
                res.second[st.top()] = i;
                st.pop();
            } else{
                break;
            }
        }
        res.first[i] = st.top();
        st.push(i);
    }
    return res;
}

Back to top page