题解 | 区间后缀极大位置计数

import java.util.*;
import java.io.*;

//双端队列搞个滑动窗口
//窗口中只存满足条件地值
//窗口单调减
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] nums = new int[n+1];
        for(int i =1 ; i <=n ;i++){
            nums[i] = in.nextInt();
        }
        Deque<Integer> queue = new ArrayDeque<>();
        for(int i =1 ;i <=n;i++){
            while(!queue.isEmpty() && i - queue.peekFirst() + 1 > k){
                queue.pollFirst();
            }
            while(!queue.isEmpty() && nums[i] >= nums[queue.peekLast()]){
                queue.pollLast();
            }
            queue.offerLast(i);
            if(i >= k){
                out.println(queue.size());
            }
        }
        out.flush();
    }
}