发布时间：2024-08-11

左偏树

P3377 【模板】左偏树/可并堆

pb_ds版

#define heap __gnu_pbds::priority_queue<pair<int,int>,greater<pair<int,int>>,pairing_heap_tag> 
int par[N];
bool vis[N];
int find(int x){
    return par[x]==x?x:par[x]=find(par[x]);
}
heap q[N];
void solve(){
    int n,m;
    cin>>n>>m;
    iota(par+1,par+n+1,1);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        q[i].push({x,i});
    }
    while(m--){
        int op,x,y;
        cin>>op;
        if(op==1){
            cin>>x>>y;
            if(vis[x]||vis[y])continue;
            x=find(x),y=find(y);
            if(x==y)continue;
            par[x]=y;
            q[y].join(q[x]);
        }
        else{
            cin>>x;
            if(vis[x]){
                cout<<"-1\n";
                continue;
            }
            x=find(x);
            y=q[x].top().first;
            int z=q[x].top().second;
            q[x].pop();
            cout<<y<<"\n";
            vis[z]=1;
        }
    }
}

手写版

int dis[N],l[N],r[N],v[N];
bool cmp(int x,int y){
    if(v[x]!=v[y])return v[x]<v[y];
    return x<y;
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(cmp(y,x))swap(x,y);//y>x
    r[x]=merge(r[x],y);
    if(dis[r[x]]>dis[l[x]])swap(l[x],r[x]);
    dis[x]=dis[r[x]]+1;
    return x;
}

P4331 [BalticOI 2004] Sequence 数字序列

题意：
给定整数序列 $a_1,a_2,a_3,...,a_n$,求一个递增序列满足 $b_1<b_2<b_3<..<b_n$,使得 $\sum_{i=1}^N |a_i-b_i|$ 最小
思路：

• 令 $a_i=a_i-i,b_i=b_i-i$ ,则变成求 $b_1 \leq b_2 \leq ... \leq b_n$
• 结论：
  • 假设b的所有值相等，则根据中位数定理，取中位数
  • 假设将一个区间分成两个区间，第一个区间中位数为u，第二个区间中位数为v
  • $u<v$ ,不用管
  • 否则，合并两个区间，取新的中位数
  • 这样构造出来的答案为最小
• 用可并堆维护中位数，注意本题属于特殊情况才可以用可并堆维护

#define heap __gnu_pbds::priority_queue<int,less<int>,pairing_heap_tag> 
struct Segment{
    int end,root,size;
};
void solve(){
    int n;
    cin>>n;
    vector<Segment> st;
    vector<int> a(n+1);
    heap q[n+1];
    for(int i=1;i<=n;i++)cin>>a[i],a[i]-=i;
    for(int i=1;i<=n;i++){
        auto cur=Segment{i,a[i],1};
        q[i].push(a[i]);
        while(st.size()&&cur.root<st.back().root){
            auto [end,root,size]=st.back();
            st.pop_back();
            q[cur.end].join(q[end]);
            if(cur.size%2&&size%2)q[cur.end].pop();
            cur.root=q[cur.end].top();
            cur.size+=size;
        }
        st.push_back(cur);
    }
    vector<int> ans(n+1);
    int res=0,i=1;
    for(auto &[end,root,size]:st){
        while(i<=end){
            ans[i]=root;
            res+=abs(ans[i]-a[i]);
            i++;
        }
    }
    cout<<res<<"\n";
    for(int i=1;i<=n;i++)cout<<ans[i]+i<<" \n"[i==n];
}

不需要记录方案的堆做法

void solve(){
    int n;
    cin>>n;
    priority_queue<int> q;
    vector<int> a(n+1);
    int ans=0,res=0;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        q.push(a[i]);
        if(q.top()>a[i]){
            ans+=q.top()-a[i];
            q.pop();
            q.push(a[i]);
        }
    }
    {//不上升
        priority_queue<int,vector<int>,greater<int>> q;
        for(int i=1;i<=n;i++){
            q.push(a[i]);
            if(q.top()<a[i]){
                res+=a[i]-q.top();
                q.pop();
                q.push(a[i]);
            }
        }
        ans=min(ans,res);
    }
    cout<<ans<<"\n";
}

POJ3016 K-单调

题意：
将序列加1或减1，使得序列有k个部分单调
思路：

• $O(n^2)$ 预处理每个部分的最小贡献，单调减的话让每个数取反即可
• $O(n^2k)$ dp转移

#define heap __gnu_pbds::priority_queue<int,less<int>,pairing_heap_tag>
struct Segment{
    int end,root;
    int tree_size,tree_sum,size,sum;
    int get(){
        return root*tree_size-tree_sum+sum-tree_sum-root*(size-tree_size);
    }
};
void solve(){
    int n,k;
    while(cin>>n>>k,n||k){
        vector<int> a(n+1),w(n+1);
        vector<vector<int>> cost(n+1,vector<int>(n+1,1e9)),f(n+1,vector<int>(k+1,1e9));
        auto getcost=[&](int u){
            heap q[n+1];
            vector<Segment> st;
            int res=0;
            for(int i=u;i<=n;i++){
                auto cur=Segment{i,w[i],1,w[i],1,w[i]};
                q[i].push(w[i]);
                while(!st.empty()&&cur.root<st.back().root){
                    auto [end,root,tree_size,tree_sum,size,sum]=st.back();
                    res-=st.back().get();
                    st.pop_back();
                    q[cur.end].join(q[end]);
                    bool ispop=cur.size%2&&size%2;
                    cur.tree_size+=tree_size;
                    cur.tree_sum+=tree_sum;
                    cur.size+=size;
                    cur.sum+=sum;
                    if(ispop){
                        auto big=q[cur.end].top();
                        q[cur.end].pop();
                        cur.tree_size--;
                        cur.tree_sum-=big;
                    }
                    cur.root=q[cur.end].top();
                }
                st.push_back(cur);
                res+=cur.get();
                cost[u][i]=min(cost[u][i],res);
            }
        };
        for(int i=1;i<=n;i++)cin>>a[i],w[i]=a[i]-i;
        for(int i=1;i<=n;i++)getcost(i);
        for(int i=1;i<=n;i++)w[i]=-a[i]-i;
        for(int i=1;i<=n;i++)getcost(i);
        f[0][0]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=k;j++){
                for(int u=1;u<=i;u++){
                    f[i][j]=min(f[i][j],f[u-1][j-1]+cost[u][i]);
                }
            }
        }
        cout<<f[n][k]<<"\n";
    }
}