фывфыв

Идея в том, чтобы хранить последовательность возрастающих минимумов. Первый элемент последовательности равен минимуму всего текущего окна, следом идёт минимум на суффиксе после этого элемента, и так далее. Например, для последовательности [2,3,1,5,4,8,7,6,9] это будут минимумы [1,4,6,9]

Когда происходит добавление элемента справа (incR, push_back), последовательность меняется следующим образом: все большие элементы убираются, сам элемент добавляется в конец.

Несколько примеров, для [1,4,6,9]:

Добавление 5: [1,4,6,9] -> [1,4] -> [1,4,5]

Добавление 100: [1,4,6,9] -> [1,4,6,9,100]

Добавление 0: [1,4,6,9] -> [] -> [0]

При удалении элемента слева (incL, pop_front) нужно знать, был ли главный минимум первым элементом окна. Просто по значению этого не понять, поэтому в последовательности помимо значений нужно хранить в паре с ними позиции этих значении. Пример выше превратится в последовательность [(1,2), (4,4), (6,7), (9,8)], если элементы нумеруются с нуля. Границы текущего окна нужно хранить явно в виде пары чисел l и r. Итак, если первый элемент последовательности является первым элементом окна, то есть его позиция равна l, то его необходимо просто удалить, более ничего в последовательности не изменится.

Реализация:

int inf = 2e9;
struct sliding_window{
    deque<pair<int,int>> d;
    int l, r;
    
    sliding_window(){
        l = r = 0;
    }
    
    void push_back(int x){
        while(!d.empty() && d.back().first >= x) d.pop_back();
        d.emplace_back(x,r);
        ++r;
    }
    
    void pop_front(){
        if(d.front().second == l) d.pop_front();
        ++l;
    }
    
    int get_min(){
        return d.empty() ? inf : d.front().first;
    }
};

int inf = 2e9;
struct sliding_window{
    vector<int> l, r;
    int rmin;
    
    sliding_window(){
        rmin = inf;
    }
    
    void push_back(int x){
        r.push_back(x);
        rmin = min(rmin, x);
    }
    
    void pop_front(){
        if(l.empty()){
            for(int mn = inf; !r.empty();){
                mn = min(mn, r.back());
                l.push_back(mn);
                r.pop_back();
            }
            rmin = inf;
        }
        l.pop_back();
    }
    
    int get_min(){
        int res = rmin;
        if(!l.empty()) res = min(res, l.back());
        return res;
    }
};