PD CSES 1076 Sliding Median

相信大家都知道什麼是中位數吧，這題最直觀的方式就是針對每一個 window 去做排序，做完排序就可以找到每個 window 的中位數，但…這很花時間，這樣的時間複雜度是

$O((n-k+1)\ast klogk)$ ，會 TLE ，因此我們不能使用這個方法。

這題我們提供一個作法，也就是利用 multiset 去做優化，具體上怎麼做呢？我們來看看！
我們要做的就是維護兩個 multiset ，一個是包含中位數的左邊的 left ，另一個是中位數右邊的 right ，並且使 left 的 multiset 會指向我們的中位數，這樣一來我們就可以取 *left 當做我們的中位數，並且隨著 window 移動，我們也可以很快的刪除以及加入元素，這樣的複雜度就會是

$O((n-k+1)\ast logk)$ ，就能順利的拿到這一題。
要記得 multiset 的底層是紅黑樹，因此在插入以及刪除都是

$O(logn)$ 。

這邊要注意一個點就是 multiset 在 erase 元素的時候如果是塞 multiset.erase(value) ，這樣會使整個容器內的 value 值都被刪掉，因此如果只要刪除某個 value 的其中一個值，記得是塞 iterator ，例如 multiset.erase(*left.begin()) 。

#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
void balance(multiset<int, greater<int> > &left, multiset<int, less<int> > &right){
    while(left.size() > right.size()){
        right.insert(*left.begin());
        left.erase(left.begin());
    }
    while(left.size() < right.size()){
        left.insert(*right.begin());
        right.erase(right.begin());
    }
}
int main(){
    IOS
    int n, k, arr[200005];
    cin >> n >> k;
    for(int i = 0;i < n;i++) cin >> arr[i];
    multiset<int, greater<int> > left;
    multiset<int, less<int> > right;
    for(int i = 0;i < n;i++){
        if(!left.size() || arr[i] <= *left.begin()) left.insert(arr[i]);
        else right.insert(arr[i]);
        if(i >= k){
            if(left.size() && arr[i - k] <= *left.begin())
                left.erase(left.find(arr[i - k]));
            else right.erase(right.find(arr[i - k]));
        }
        balance(left, right);
        if(i >= k - 1) cout << *left.begin() << ' ';
    }
    cout << '\n';

    return 0;
}