#LAISIR12. 滑動窗口中位數查詢(Sliding Median)

滑動窗口中位數查詢(Sliding Median)

題目名稱:滑動窗口中位數查詢(Sliding Median)

題目描述:

給定一個長度為 nn 的整數序列 a1,a2,,ana_1, a_2, \dots, a_n,以及一個整數 kk,表示滑動窗口的大小。

請你計算每個長度為 kk 的連續子序列的中位數。

中位數定義如下:

若子序列長度為奇數,則中位數為排序後的中間元素。

若子序列長度為偶數,則中位數為排序後靠左的中間元素(即第 k/2k/2 小的元素)。

輸入格式:

第一行包含兩個整數 nnkk,表示序列的長度和滑動窗口的大小。

第二行包含 nn 個整數 a1,a2,,ana_1, a_2, \dots, a_n,表示序列中的元素。

輸出格式:

輸出共 nk+1n - k + 1 行,每行一個整數,依序表示每個滑動窗口的中位數。

範例輸入:

7 3
1 3 -1 -3 5 3 6

範例輸出:

1
-1
-1
3
5

📘 說明: 對於給定的序列和窗口大小,滑動窗口的位置及其對應的中位數如下:

窗口 [1, 3, -1] → 排序後 [-1, 1, 3] → 中位數為 1

窗口 [3, -1, -3] → 排序後 [-3, -1, 3] → 中位數為 -1

窗口 [-1, -3, 5] → 排序後 [-3, -1, 5] → 中位數為 -1

窗口 [-3, 5, 3] → 排序後 [-3, 3, 5] → 中位數為 3

窗口 [5, 3, 6] → 排序後 [3, 5, 6] → 中位數為 5

📌 限制條件: 1kn1051 \leq k \leq n \leq 10^5

109ai109-10^9 \leq a_i \leq 10^9