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

题目描述

给定一个长度为 $n$ 的数列 $a$，对于其中每个长度为 $k$ 的子区间，请你求出这个这个子区间构成的数列的所有后缀最大值的位置个数。

一个下标 $i$ 是是数列 $b$ 的后缀最大值下标当且仅当：对于所有的 $i < j \leq |b|$，都有 $b_i > b_j$，其中 $|b|$ 表示 $b$ 的元素个数。

输入格式

第一行是两个整数，依次表示操作次数 $n$ 和子区间长度 $k$。

第二行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

输出格式

共输出 $n - k + 1$ 行每行一个整数，按左端点从小到大的顺序依次输出每个子区间构成的数列的后缀最大值位置个数。

样例 #1

样例输入 #1

5 3

2 1 3 5 4

样例输出 #1

1
1
2

提示

样例 1 解释

第一个子数列：$2, 1, 3$。其中 $3$ 是后缀最大值。

第二个子数列：$1, 3, 5$，其中 $5$ 是后缀最大值。

第三个子数列：$3,5,4$，其中 $5$ 和 $4$ 是后缀最大值。

数据规模与约定

对于全部的测试点，保证 $1 \leq k \leq n \leq 10^6$，$1 \leq x_i \lt 2^{64}$。

题解

#include <bits/stdc++.h>
#define AC return 0
using namespace std;

deque<int> ans;
int n, k;
unsigned long long a[1000010];

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        scanf("%llu", a + i);
        if (ans.size() && ans.front() + k - 1 < i)
            ans.pop_front();
        while (ans.size() && (a[i] >= a[ans.back()]))
            ans.pop_back();
        ans.push_back(i);
        if (i >= k)
            printf("%d\n", ans.size());
    }
    AC;
}