BISHI122　区间后缀极大位置计数¶

简单通过率 25.6%python3样例通过牛客 AC

一句话

每个长度为 k 的窗口内后缀最大值位置的个数。

解题思路¶

这题考什么¶

BISHI121 的滑动窗口版。由 BISHI121 的结论：

「后缀最大值位置的集合」= 单调递减栈（队列）里的元素集合，

所以本题答案就是单调递减队列在该窗口下的长度—— 代码几乎就是滑动窗口最大值模板，只是输出 len(q) 而不是 a[q[0]]。

数据规模与复杂度¶

n <= 1e6，时限「其他语言 2 秒」。O(n)，但常数必须压到极限：

用 list + 两个整数指针 h/t 代替 deque，省掉方法调用（快 1.5-2 倍）；
队列长度直接是 t - h + 1，连 len() 调用都省了；
一次性 read / 一次性 join 输出。

坑在哪¶

弹队尾用 <=（相等也弹），因为要求严格大于右边所有元素；
队首过期判断 q[h] <= i - k，写成 < 会让窗口变成 k+1 长；
k 可以等于 1，也可以等于 n，两个边界都要能跑；
输出是 n-k+1 行（不是一行空格分隔），和 BISHI114 不同，别抄串了。

Python 常数¶

n=1e6 配「其他语言 2 秒」，各段耗时大致是读入 0.15s、建表 0.25s、主循环 1.0-1.5s、输出 0.2s，本文件这份写法在 Python 3 下实测通过。余量并不宽裕，上面三条优化都是为压常数而设：换回 deque、在循环里调 len()、或逐行 print，都会让主循环明显变慢。

样例复核¶

a = [2,1,3,5,4]、k=3。窗口 [2,1,3] 弹到只剩下标 3（值 3），长度 1；窗口 [1,3,5] 同理只剩 5，长度 1；窗口 [3,5,4] 里 5 弹掉了 3， 4 比 5 小留在队尾，队列是 (5,4)，长度 2。与期望输出 1 1 2 一致。

参考实现¶

solutions/BISHI122.py
import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    a = list(map(int, data[2:2 + n]))
    # 用定长 list 加两个整数指针手写队列：h、t 都只增不减，
    # 每个下标最多被写入一次、被 t 越过一次，所以 n 长的数组够用
    q = [0] * n                              # 存下标
    h = 0                                    # 队首（含）
    t = -1                                   # 队尾（含）；t < h 表示队列为空
    res = []
    push = res.append
    for i in range(n):
        x = a[i]
        # 队尾那些 <= x 的下标既更小又更早过期，不可能再是任何窗口的后缀最大值
        while t >= h and a[q[t]] <= x:       # 相等也弹（严格大于）
            t -= 1                           # 「出队」只是把尾指针往回挪，不动数组
        t += 1
        q[t] = i
        # 窗口每步只右移一格，最多一个下标滑出，用 if 足够
        if q[h] <= i - k:                    # 队首过期
            h += 1
        if i >= k - 1:                       # i = k-1 时窗口首次填满
            push(t - h + 1)                  # ★ 答案就是队列长度
    sys.stdout.write("\n".join(map(str, res)) + "\n")


main()

BISHI122 区间后缀极大位置计数¶