滑动窗口逆序对(Sliding Window Inversions)

题目描述

本题对应 CSES Problem Set 3223：Sliding Window Inversions。

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$ 以及滑动窗口大小 $k$。

请从左到右依次求出每一个长度为 $k$ 的连续子数组 $a[i \dots i+k-1]$（$1 \le i \le n - k + 1$）内部的逆序对数量。

窗口内的两个下标 $p, q$（$i \le p < q \le i + k - 1$）若满足 $a_p > a_q$，则构成一个逆序对。

输入格式

第一行包含两个正整数 $n, k$，分别表示数组长度与滑动窗口大小。

第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$。

输出格式

输出一行 $n - k + 1$ 个整数，用空格隔开，依次表示每个长度为 $k$ 的滑动窗口内的逆序对数量。

样例输入 #1

8 3
1 2 3 2 5 2 3 1

样例输出 #1

0 1 1 1 2 2

样例输入 #2

5 2
5 4 3 2 1

样例输出 #2

1 1 1 1

数据范围

对于 $100\%$ 的数据，$1 \le k \le n \le 2 \times 10^5$，$1 \le a_i \le 10^9$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

测试点分布

出处：原题链接