SlideMost - スライド最小値/最大値
(lib/13-static-range-query/SlideMost.cpp)

• View this file on GitHub
• Last update: 2023-06-13 08:02:50+09:00

SlideMost

• スライド最小値/最大値
• 0-indexed
• 最大値か最小値のクラスをテンプレートで渡す必要がある
  • 下記が一例

    template<class T> struct ValueMin {
    using TypeValue = T;
    inline static constexpr bool func_compare(TypeValue l,TypeValue r){return l>=r;}
    };
    

コンストラクタ

• SlideMost(void)

メソッド

• vector window(vector& vec, const int& width)
  • vecをスライドした最小値/最大値を返す
  • $O(N)$
  • width 区間幅
  • [l,r]のスライドした値がrにセットされて返ってくる

Verified with

• test/static-range-query/SlideMost.test.cpp

Code

/*
 * @title SlideMost - スライド最小値/最大値
 * @docs md/static-range-query/SlideMost.md
 */
template<class Operator> class SlideMost {
    using TypeValue = typename Operator::TypeValue;
public:
    SlideMost(void){
    }
    vector<TypeValue> window(vector<TypeValue>& vec, const int& width){
        vector<TypeValue> res(vec.size());
        deque<TypeValue> deq;
        for(int i = 0; i < vec.size(); ++i) {
            while(deq.size() && Operator::func_compare(vec[deq.back()],vec[i]) ) deq.pop_back();
            deq.push_back(i);
            res[i] = vec[deq.front()];
            if(i+1>=width && deq.front()==i+1-width) deq.pop_front();
        }
        return res;
    }
};
//最小値クエリ
template<class T> struct ValueMin {
    using TypeValue = T;
    inline static constexpr bool func_compare(TypeValue l,TypeValue r){return l>=r;}
};
//最大値クエリ
template<class T> struct ValueMax {
    using TypeValue = T;
    inline static constexpr bool func_compare(TypeValue l,TypeValue r){return l<=r;}
};

#line 1 "lib/13-static-range-query/SlideMost.cpp"
/*
 * @title SlideMost - スライド最小値/最大値
 * @docs md/static-range-query/SlideMost.md
 */
template<class Operator> class SlideMost {
    using TypeValue = typename Operator::TypeValue;
public:
    SlideMost(void){
    }
    vector<TypeValue> window(vector<TypeValue>& vec, const int& width){
        vector<TypeValue> res(vec.size());
        deque<TypeValue> deq;
        for(int i = 0; i < vec.size(); ++i) {
            while(deq.size() && Operator::func_compare(vec[deq.back()],vec[i]) ) deq.pop_back();
            deq.push_back(i);
            res[i] = vec[deq.front()];
            if(i+1>=width && deq.front()==i+1-width) deq.pop_front();
        }
        return res;
    }
};
//最小値クエリ
template<class T> struct ValueMin {
    using TypeValue = T;
    inline static constexpr bool func_compare(TypeValue l,TypeValue r){return l>=r;}
};
//最大値クエリ
template<class T> struct ValueMax {
    using TypeValue = T;
    inline static constexpr bool func_compare(TypeValue l,TypeValue r){return l<=r;}
};

Back to top page