#STL018. 窗口极值索引

窗口极值索引

窗口极值索引

一条观测带记录了 n 个整数。检验员用长度为 k 的框从左向右逐格移动,每次既记录最小值和最大值,也标出它们在整条观测带上的位置。

同一个极值可能在框中出现多次,检验员总是标出框内最靠左的那一次。请为每个连续长度为 k 的窗口生成记录。

输入格式

第一行两个整数 n、k。第二行 n 个整数 a₁,…,aₙ。

输出格式

共输出 n−k+1 行,依次对应左端点为 1、2、…、n−k+1 的窗口。每行四个整数:最小值、最小值最早位置、最大值、最大值最早位置。

位置是原数组的 1 基下标。重复的最小值或最大值,都取当前窗口内最靠左的位置。k=1 时,最小值与最大值相同,两个位置也相同。

数据范围与约定

  • 1≤k≤n≤200000。
  • −1000000000≤aᵢ≤1000000000。
  • 窗口从不为空;k=n 时只输出一行。

样例 1

输入:

6 3
2 1 1 4 4 0

输出:

1 2 2 1
1 2 4 4
1 3 4 4
0 6 4 4

说明:四个窗口依次为 [2,1,1]、[1,1,4]、[1,4,4]、[4,4,0]。第一窗最小值 1 取位置 2;第三窗最大值 4 取位置 4;最后一窗最大值同样取位置 4。

样例 2

输入:

3 1
-5 0 -5

输出:

-5 1 -5 1
0 2 0 2
-5 3 -5 3

说明:窗口长度为 1,每个窗口的极小、极大都是它唯一的元素;位置仍按整个数组从 1 计数。

原创说明

本题的场景、题面、样例、实现与数据由本题单作者独立编写;仅使用公开的算法概念与 C++ 标准库接口,未使用第三方题面或测试文件。