从2023济南K学习滑动窗口中位数问题

板子

• 对顶堆

template<class T>
struct DualHeap {Heap<T, std::greater<T>> small; // 小根堆，里面存放大的值Heap<T, std::less<T>> big;      // 大根堆，里面存放前k小的值//中位数就是big.top()DualHeap() {}void update() {if (big.size() == 0 and small.size() == 0) {return;}while (big.size() > small.size() + 1) {T x = big.top();big.pop();small.push(x);}while (big.size() < small.size()) {T x = small.top();small.pop();big.push(x);}}void push(T val) {if (big.size() == 0) {big.push(val);return;}if (val <= big.top()) {big.push(val);} else {small.push(val);}update();}void erase(T val) {assert(big.size() >= 1);if (val <= big.top()) {big.erase(val);} else {small.erase(val);}update();}};

• 可删堆

template <class T, class Cmp = std::less<T>>
struct Heap {//可删堆std::priority_queue<T, std::vector<T>, Cmp> qPush, qErase; // Heap=qPush-qErasei64 sum;Heap() : sum{0} {}void push(T x) {qPush.push(x);}void erase(T x) {qErase.push(x);}T top() {while (!qErase.empty() && qPush.top() == qErase.top())qPush.pop(), qErase.pop();return qPush.top();}void pop() {while (!qErase.empty() && qPush.top() == qErase.top()) {qPush.pop(), qErase.pop();}qPush.pop();}int size() {return qPush.size() - qErase.size();}
};

滑动窗口中位数

https://codeforces.com/gym/104901/problem/K

选区间内一个数，让区间内每个数到这个数的距离之和最小，动态维护这个距离之和

首先一个经典结论，这个数就是中位数。

那么问题转化成：滑动窗口维护区间每个数到中位数的距离之和 \(ans\)。

显然，ans 是所有比中位数 \(mid\) 与每个比中位数小的数 \(less\) 的差加上每个比中位数大的数 \(large\) 与中位数的差，也就是

\[ans = cnt_{less}\times mid - sum_{less} + sum_{large} - cnt_{large}\times mid \]

那么我们就是要维护三个信息：

\(less, large, mid\)

这很像对顶堆，less和large的相关信息都完全可以对应上其中的大根堆和小根堆

单纯的对顶堆，是不支持删除的。

想要维护滑动窗口的中位数，就得结合可删堆。

直接从应用入手，把两个对顶堆改成可删堆其中即可，而对 sum 的动态维护则在可删堆的 push，pop，erase 操作中实现即可，非常直观。

template <class T, class Cmp = std::less<T>>
struct Heap {//可删堆std::priority_queue<T, std::vector<T>, Cmp> qPush, qErase; // Heap=qPush-qErasei64 sum;//维护出这个堆对应的sumHeap() : sum{0} {}void push(T x) {//加入的同时更新sumsum += x;qPush.push(x);}void erase(T x) {//删除的同时更新sumsum -= x;qErase.push(x);}T top() {while (!qErase.empty() && qPush.top() == qErase.top())qPush.pop(), qErase.pop();return qPush.top();}void pop() {//一样，更新sumwhile (!qErase.empty() && qPush.top() == qErase.top()) {qPush.pop(), qErase.pop();}sum -= qPush.top();qPush.pop();}int size() {//真实的个数也可以通过可删堆维护出来return qPush.size() - qErase.size();}
};template<class T>
struct DualHeap {//结合可删堆，形成可删对顶堆Heap<T, std::greater<T>> small; // small rootHeap<T, std::less<T>> big;      // big rootDualHeap() {}void update() {if (big.size() == 0 and small.size() == 0) {return;}while (big.size() > small.size() + 1) {T x = big.top();big.pop();small.push(x);}while (big.size() < small.size()) {T x = small.top();small.pop();big.push(x);}}void push(T val) {if (big.size() == 0) {big.push(val);return;}if (val <= big.top()) {big.push(val);} else {small.push(val);}update();}void erase(T val) {assert(big.size() >= 1);if (val <= big.top()) {big.erase(val);} else {small.erase(val);}update();}i64 getResult() {if (big.size() == 0) {return 0;}//说明只有一个数int x{big.top()}; i64 ans1 = 1LL * x * big.size() - big.sum;//比中位数小的数的贡献i64 ans2 = small.sum - 1LL * x * small.size();//比中位数大的数的贡献return ans1 + ans2;}};void solve()
{
#define testsint n; i64 k; std::cin >> n >> k; std::vector<int> a(n); for (auto& ai : a) {std::cin >> ai; --ai;} for (int i = 0; i < n; i++) {a[i] -= i;}DualHeap<int> dheap; int ans{}; for (int l = 0, r = 0; r < n; r++) {//这题固定右指针，移动左指针更方便dheap.push(a[r]);while (l <= r and dheap.getResult() > k) {//如果不满足条件，就继续移动左指针dheap.erase(a[l]);l += 1;}ans = std::max(ans, r - l + 1);}std::cout << ans << '\n';}