Algoogle

Algorithm for Programming Contest

スライド最小値

基本情報


計算量

解説


区間の最小値を求める(同様にして最大値もできる).
幅を固定して列を舐めるときに有効な手法.
幅を固定しなくてもしゃくとりなど区間の両端の位置が単調非減少に推移するときに有効.

数列を左から右に舐めるのを考える.
dequeに値の位置を突っ込んでいく.
dequeのfrontに常に区間の最小値のうち一番後の位置が入るようにする.
区間の右端を進めるとき, 新しい値以上の位置があるとき後ろからそれらを全部popしていく.
その後, 右端の位置を入れる.
区間の左端を進めるときはfrontの位置が範囲外になるならpopする.

コードは幅wの区間を左からみて最小値を列挙する.

コード

(slide-min.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void rsucc(int &r, deque<int> &q) {
    while(!q.empty() and seq[q.back()] >= seq[r]) q.pop_back();
    q.push_back(r++);
}
// assume l < r
void lsucc(int &l, deque<int> &q) { if(q.front() == l++) q.pop_front(); }

vector<int> slide_min(const vector<int> &seq, int w) {
    vector<int> ret;
    deque<int> q;
    int l = 0, r = 0, n = seq.size();

    while(r < w) rsucc(r,q);
    while(r < n) {
        rsucc(r,q); lsucc(l,q);
        ret.push_back(seq[q.front()]);
    }
    return ret;
}

問題


Comments