// Sliding Window Median class Solution { public: vector medianSlidingWindow(vector& nums, int k) { vector r; multiset a(nums.begin(), nums.begin()+k); auto mid = next(a.begin(), (k-1)/2); for (int i = k; ; i++) { r.push_back((double(*mid)+*next(mid, 1-k%2))/2); if (i == nums.size()) break; a.insert(nums[i]); if (nums[i] < *mid) --mid; if (nums[i-k] <= *mid) ++mid; a.erase(a.lower_bound(nums[i-k])); } return r; } }; /// class Solution { vector fenwick; void add(int x, int n, int v) { for (; x < n; x |= x+1) fenwick[x] += v; } int select(int k, int n) { int r = -1; for (int x = 1<<31-__builtin_clz(n); x; x >>= 1) if (r+x < n && fenwick[r+x] <= k) k -= fenwick[r += x]; return r+1; } public: vector medianSlidingWindow(vector& nums, int k) { vector r; vector a = nums; int n = nums.size(); fenwick.assign(n, 0); sort(a.begin(), a.end()); for (int i = 0; i < k; i++) add(lower_bound(a.begin(), a.end(), nums[i])-a.begin(), n, 1); for (int i = k; i <= nums.size(); i++) { r.push_back(0.5*(double(a[select((k-1)/2, n)])+a[select(k/2, n)])); add(lower_bound(a.begin(), a.end(), nums[i-k])-a.begin(), n, -1); if (i < nums.size()) add(lower_bound(a.begin(), a.end(), nums[i])-a.begin(), n, 1); } return r; } };