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

板子

  • 对顶堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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();
    }

};
  • 可删堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
template <class T, class Cmp = std::less<T>>
struct Heap {//可删堆
    std::priority_queue<T, std::vector<T>, Cmp> qPush, qErase; // Heap=qPush-qErase
    i64 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 操作中实现即可，非常直观。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
template <class T, class Cmp = std::less<T>>
struct Heap {//可删堆
    std::priority_queue<T, std::vector<T>, Cmp> qPush, qErase; // Heap=qPush-qErase
    i64 sum;//维护出这个堆对应的sum
 
    Heap() : sum{0} {}
 
    void push(T x) {//加入的同时更新sum
        sum += x;
        qPush.push(x);
    }
 
    void erase(T x) {//删除的同时更新sum
        sum -= x;
        qErase.push(x);
    }
 
    T top() {
        while (!qErase.empty() && qPush.top() == qErase.top())
            qPush.pop(), qErase.pop();
        return qPush.top();
    }
 
    void pop() {//一样，更新sum
        while (!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 root
    Heap<T, std::less<T>> big;      // big root
 
    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();
    }

    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 tests
    int 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';

}