The idea is to maintain a BST of the window and just search for the k/2 largest element and k/2 smallest element then the average of these two is the median of the window.

Now if the STL's multiset BST maintained how many element were in each subtree finding each median would take O(log k) time but since it doesn't it takes O(k) time to find each median.

```
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
multiset<int> mp;
vector<double> med;
for(int i=0; i<k-1; ++i) mp.insert(nums[i]);
for(int i=k-1; i< nums.size(); ++i){
mp.insert(nums[i]); // Add the next number
auto itb = mp.begin(); advance(itb, (k-1)/2); //Find the lower median
auto ite = mp.end(); advance(ite, -(k+1)/2); //Find the upper median
double avg = ((long)(*itb) + (*ite)) / 2.0;
med.push_back(avg);
mp.erase(mp.find(nums[i-k+1])); //Remove the oldest element
}
return med;
}
};
```