Nghịch Thế Cửa Sổ Trượt

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một mảng gồm $n$ số nguyên, hãy đếm số nghịch thế trong mỗi cửa sổ trượt gồm $k$ phần tử liên tiếp. Một nghịch thế là một cặp vị trí $(i, j)$ với $i < j$ mà phần tử trước lớn hơn phần tử sau.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $k$ : kích thước mảng và kích thước cửa sổ.

Dòng thứ hai chứa $n$ số nguyên $x_{1}, x_{2}, \dots, x_{n}$ : các phần tử của mảng.

Dữ liệu ra

In ra $n - k + 1$ số nguyên, mỗi số là số nghịch thế trong cửa sổ tương ứng.

Ràng buộc

$1 \leq k \leq n \leq 2 \cdot 10^{5}$
$1 \leq x_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
8 3 1 2 3 2 5 2 4 4	0 1 1 1 2 0	[1,2,3]→0, [2,3,2]→1, [3,2,5]→1, [2,5,2]→1, [5,2,4]→2, [2,4,4]→0

Bình luận

Không có bình luận tại thời điểm này.