洛谷 B3667. 求区间所有后缀最大值的位置

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

unsigned long long n, k, a[1000010];

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 单调递减队列
    deque<unsigned long long> q;
    for (int i = 1; i <= n; i++) {
        while (q.size() && q.front() + k <= i) q.pop_front();
        while (q.size() && a[q.back()] <= a[i]) q.pop_back();
        q.push_back(i);
        if (i >= k) cout << q.size() << endl;
    }

    return 0;
}