CSES - Sliding Median

Solution 1: Maintaining two multisets

To accomplish finding the sorted median of a sliding window, we can store the window within two sets: one containing the lower values of the window and the other containing the upper values. If we ensure that the size of the lower set is always greater than or equal to the size of the upper set, then the largest element in the lower set will be the median. This works for all sizes of windows. In odd windows, the size of the lower set will be one larger than the upper set, therefore its largest element will be the median. In even windows, the problem calls for the smallest of the two centermost values so this strategy still works.

To implement, we need a function that will handle inserting and removing elements in the window. For inserting, compare the incoming value to the current median and place it in the upper set if it is greater than the median, put it in the lower set otherwise. If one set fills above its max size, transfer an element to the other set. Erasing is more simple, just find the element and erase it.

Implementation

Time Complexity: $\mathcal{O}(N\log N)$

Copy
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;

long N, M;
long arr[200010];
multiset<long> up;
multiset<long> low;

Solution 2: Fenwick Tree

We can use a Fenwick tree to simulate an order statistic tree/indexed set.

The Fenwick array (let's call it fa)can be treated as a frequency array. For example, if 5 is inserted into the window, fa[5] += 1. This enables us to binary search for an integer $x$ such that

and find $k$ from there. Clearly, the values of the array would need to be compressed, as an array of size $10^9$ is infeasible. There will also be an extra $\log$ factor from using the Fenwick tree sum operation, yielding a total time complexity of $\mathcal{O}(n\log^2{n})$. Note that a more precise upper bound is $\mathcal{O}((n-k+1) \cdot \log^2{k} + n \log{n})$ (there are $(n-k+1)$ windows), but it's tricky to express the maximum value of this in terms of $n$ and $k$; therefore, $\mathcal{O}(n \log^2{n})$ is better.

Copy
#include <bits/stdc++.h>
using namespace std;

const int sz = 200005;
int fa[sz], a[sz], bit[sz], n, k;
map<int, int> compressed, decompress;

int psum(int x, int sum = 0) {
	for (; x > 0; x -= x & -x) sum += bit[x];
	return sum;

Solution 3: Order Statistic Tree

Copy
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;

OS-SELECT(x, i):
    if (i < x.left.size + 1)
	return OS-SELECT(x.left, i);
    else if (i > x.left.size + x.count)
	return OS-SELECT(x.right, i - x.left.size - x.count);
    else
	return x;

Copy
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int N = io.nextInt();
		int K = io.nextInt();
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) arr[i] = io.nextInt();