滑窗第k小，multiset

用multiset维护两个多重集合A和B，A维护着区间中k个最小值，B维护着区间中剩余的值

无论是插入还是删除x，首先判断x所属集合。然后从所属集合中添加或删除。再判断A集合大小是否为k：大于k则移动一个最大值到B中，小于k则移动B中的最小值到A中。

struct Kmin {
    int K;
    // st1 保存前 K 小值，st2 保存其它值
    multiset<long long> st1, st2;

    Kmin(int K): K(K){}

    void adjust() {
        while (st1.size() < K && st2.size() > 0) {
            long long t = *(st2.begin());
            st1.insert(t);
            st2.erase(st2.begin());
        }
        while (st1.size() > K) {
            long long t = *st1.rbegin();
            st2.insert(t);
            st1.erase(st1.find(t));
        }
    }

    // 插入元素 x
    void add(long long x) {
        // x大于k，放第二个集合
        if (!st2.empty() && x >= *(st2.begin())) st2.insert(x);
        // x小于k，放第一个集合
        else st1.insert(x);
        adjust();
        
    }

    // 删除元素 x
    void del(long long x) {
        auto it = st1.find(x);
        if (it != st1.end()) st1.erase(it);
        else st2.erase(st2.find(x));
        adjust();
    }
    long long getK() {
        return *st1.rbegin();
    }
};

滑窗第k小，二叉堆

用二叉堆维护一个大根堆A和小根堆B，A维护着区间中k个最小值，B维护着区间中剩余的值。

堆无法删除，我们采用延时删除，记录需要延时删除的数x需要删除的次数cnt[x]。

记录A和B中清除无用数据后的大小sz1, sz2。

每次获取堆顶前，清除堆顶的无用数据。

无论是插入还是删除x，首先判断x所属集合。然后从所属集合中添加或删除。再判断A集合大小是否为k：大于k则移动一个最大值到B中，小于k则移动B中的最小值到A中。

值得注意的是删除x，不能再cnt[x]++后立刻清除无用数据x，因为还需要判断x所处集合，并让对于集合大小减少1，如果直接删除，那么无法确定x在原来的集合。

struct Kmin {
    // 第K小, 集合大小（有效数据）
    int K, sz1, sz2;
    // st1 保存前 K 小值，st2 保存其它值
    priority_queue<long long> st1;
    priority_queue<long long, vector<long long>, greater<>> st2;
    // 待删除的数x的次数cnt[x]，堆顶为x且cnt[x]存在则删除
    map<long long, int> cnt;

    Kmin(int K): K(K), sz1(0), sz2(0){}

    void clear() {
        // 优先删除非k小的，避免调整
        while (st2.size() && cnt.count(st2.top())) {
            if (--cnt[st2.top()] == 0) cnt.erase(st2.top());
            st2.pop(); 
        }
        while (st1.size() && cnt.count(st1.top())) {
            if (--cnt[st1.top()] == 0) cnt.erase(st1.top());
            st1.pop(); 
        }
    }
    void adjust() {
        clear();
        while (sz1 < K && sz2 > 0) {
            st1.emplace(st2.top());
            st2.pop();
            sz1++;
            sz2--;
        }
        while (sz1 > K) {
            st2.emplace(st1.top());
            st1.pop();
            sz1--;
            sz2++;
        }
    }

    // 插入元素 x
    void add(long long x) {
        clear();
        if (sz2>0 && x >= st2.top()) {
            st2.emplace(x);
            sz2++;
        } else {
            st1.emplace(x);
            sz1++;
        }
        adjust();
    }

    // 删除元素 x
    void del(long long x) {
        clear();
        cnt[x]++; // 不能清理x，无法判断x所属集合
        if (sz2>0 && x >= st2.top()) {
            sz2--;
        } else {
            sz1--;
        }
        adjust();
    }
    long long getK() {
        clear();
        return st1.top();
    }
};

滑窗最大值，延迟删除堆

相比multiset常数小

template <typename T>
struct Heap {
    std::priority_queue<T> p, q;
    int size() { return p.size() - q.size(); }
    void push(T x) { p.push(x); }
    int top() {
        while (q.size() && p.top() == q.top())
            p.pop(), q.pop();
        return p.top();
    }
    void pop() {
        while (q.size() && p.top() == q.top())
            p.pop(), q.pop();
        p.pop();
    }
    void erase(T x) { q.push(x); }
};