CP145 · 最近请求次数

简单模拟核心代码模式队列滑动窗口时限 1000 ms(参考)
题目描述

服务器依次收到 n 个请求,时间戳 t 严格递增。对第 i 个请求,求时间区间 [t_i − w, t_i] 内(含两端)到达的请求个数(包括第 i 个自身)。本题为「核心代码模式」:模板已内置整数读入与输出脚手架,只需补全指定函数。要求用队列维护窗口,整体线性时间。

输入描述

第一行两个整数 n、w(1 ≤ n ≤ 10^5,0 ≤ w ≤ 10^9);第二行 n 个严格递增的整数 t(1 ≤ t ≤ 10^9)。

输出描述

一行 n 个整数,用空格分隔:每个请求对应的窗口内请求数。