封装对顶堆板子

Dear 丶 2024-03-29 16:21 70阅读 0赞

**不懂，这都能称为板子吗**

**无所谓，下午太闲随便写的，已经靠这个水掉好几道洛谷了嘻嘻**

参考的是这个：

![5b330d47f8809ced9530ff398a8d4af5.png][]

[P1801 黑匣子 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P1801 _ - _ _ _ _luogu.com.cn]

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=2e5+10;
    struct d_heap{
        /*封装对顶堆
        mode=1:维护第k大
        mode=2:维护第k小*/
        priority_queue<int> q1;
        priority_queue<int,vector<int>,greater<int> > q2;
        void adpt(int k,int mode){
            if(mode==1){
                if(q2.size()<k){
                    while(q2.size()!=k){
                        q2.push(q1.top());
                        q1.pop();
                    }
                }else if(q2.size()>k){
                    while(q2.size()!=k){
                        q1.push(q2.top());
                        q2.pop();
                    }
                }
            }else{
                if(q1.size()<k){
                    while(q1.size()!=k){
                        q1.push(q2.top());
                        q2.pop();
                    }
                }else if(q1.size()>k){
                    while(q1.size()!=k){
                        q2.push(q1.top());
                        q1.pop();
                    }
                }
            }
        }
        void insert(int x,int k,int mode){
            if(mode==1){
                if(q2.empty()||x>=q2.top()) q2.push(x);
                else q1.push(x);
            }else{
                if(q1.empty()||x<=q1.top()) q1.push(x);
                else q2.push(x);
            }
            adpt(k,mode);
        }
        int find(int k,int mode){
            adpt(k,mode);
            if(mode==1){
                if(q2.empty()) return 0;
                return q2.top();
            }else{
                if(q1.empty()) return 0;
                return q1.top();
            }
        }
        void del(int k,int mode){
            if(mode==1) q2.pop();
            else q1.pop();
            adpt(k,mode);
        }
    };
    int n,m,x,l=1,tot=0;
    int a[mxn],b[mxn];
    void solve(){
        d_heap q;
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=m;i++){
            cin>>x;
            tot++;
            if(l==x+1) q.adpt(tot,0);
            for(int j=l;j<=x;j++) q.insert(a[j],tot,0);
            cout<<q.find(tot,0)<<'\n';
            l=x+1;
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[5b330d47f8809ced9530ff398a8d4af5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/4019b9a76ede4f47afd5859a73d104e3.png
[P1801 _ - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P1801