单调队列区间问题

P1440 求m区间内的最小值

137292zW @ 2022-01-19 11:18:59

1.为什么单调队列要小于n - 1 而不是 n 2.前m个数到它本身,不是 队列第一个数 到 它本身, 个数应该 +1,应该小于 i 吗?

#include<iostream>
#include<deque>
using namespace std;

deque<int> q;
int a[3000005];

int main(){

    int n, m;
    cin >> n >> m;

    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    cout << 0 << endl;

    for(int i = 0; i < n - 1; i++){//这里
        if(q.size() && q.front() + m <= i//这里)
            q.pop_front();
        while(q.size() && a[i] <= a[q.back()])
            q.pop_back();
        q.push_back(i);
        printf("%d\n", a[q.front()]);
    }

    return 0;
}

|