社区讨论

配对堆求助!

P4971断罪者参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo7t8pi3
此快照首次捕获于
2023/10/27 07:23
2 年前
此快照最后确认于
2023/10/27 07:23
2 年前
查看原帖
CPP
#include<bits/stdc++.h>

using namespace std;

#define int long long
const int N=2e6+6;
struct LeftistTree{
    struct tree{
        int c,s,v,f;
    }t[N];
    #define c(p) (t[p].c)
    #define s(p) (t[p].s)
    #define v(p) (t[p].v)
    #define f(p) (t[p].f)
    int tot;
    int find(int x){
        return x==f(x)?x:f(x)=find(f(x));
    }
    int merge(int x,int y){
        if(!x||!y)return x|y;
        if(v(x)<v(y)||(v(x)==v(y)&&x>y))swap(x,y);
        if(c(x))f(c(x))=y;
        s(y)=c(x);
        f(y)=x;
        c(x)=y;
        return x;
    }
    int merge(int p){
        if(!p)return p;
        f(p)=0;
        if(!s(p))return p;
        int x=s(p),y=s(x);
        f(x)=s(p)=s(x)=0;
        return merge(merge(y),merge(p,x));
    }
    // inline void decrease(int x,int v){
    //     int p=find(x);
    //     v(x)-=v;
    //     if(x==p)return merge(p,x),void();
    //     if(c(f(x))==x)c(f(x))=s(x);
    //     else s(f(x))=s(x);
    //     if(s(x))f(s(x))=f(x);
    //     s(x)=f(x)=0;
    //     f(p)=f(x)=merge(p,x);
    // }
    inline void decrease(int p,int v){
        v(p)-=v;
        int x=merge(c(p));
        c(p)=s(p)=0;
        f(s(p))=f(p)=f(x)=f(find(p))=merge(x,find(p));
    }
    inline void mergeset(int x,int y){
        x=find(x),y=find(y);
        if(x==y)return;
        f(x)=f(y)=merge(x,y);
    }
    inline void clear(){
        tot=0;
    }
    inline void create(int x){
        t[++tot]={0,0,x,tot};
    }
}ph;
int t,w,k,n,m;
bool v[N];
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t>>w>>k;
    while(t--){
        cin>>n>>m;
        ph.clear();
        memset(v,0,sizeof(v));
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
            ph.create(x);
        }
        while(m--){
            int op,a,b;
            cin>>op>>a;
            if(op!=2)cin>>b;
            if(op==2)ph.decrease(a,ph.t[a].v);
            else if(op==3){
                a=ph.find(a);
                ph.decrease(a,min(ph.t[a].v,b));
            }
            else if(op==4)ph.mergeset(a,b);
        }
        int sum=0,ma=0;
        for(int i=1;i<=n;i++){
            int f=ph.find(i);
            if(v[f])continue;
            v[f]=1;
            sum+=ph.t[f].v;
            ma=max(ma,ph.t[f].v);
        }
        if(w==2)sum-=ma;
        if(w==3)sum+=ma;
        if(sum==0)cout<<"Gensokyo 0\n";
        else if(sum<=k)cout<<"Heaven "<<sum<<'\n';
        else cout<<"Hell "<<sum<<'\n';
    }
    return 0;
}
rt,这份代码57分,但是按照注释掉的那部分,只有两分,注释掉的那部分大体上是按照OI-wiki上写的。
CPP
// root为堆的根,x为要操作的节点,v为新的权值,调用时需保证 v <= x->v
// 返回值为新的根节点
Node *decrease_key(Node *root, Node *x, LL v) {
  x->v = v;                 // 更新权值
  if (x == root) return x;  // 如果 x 为根,则直接返回
  // 把x从fa的子节点中剖出去,这里要分x的位置讨论一下。
  if (x->father->child == x) {
    x->father->child = x->sibling;
  } else {
    x->father->sibling = x->sibling;
  }
  if (x->sibling != nullptr) {
    x->sibling->father = x->father;
  }
  x->sibling = nullptr;
  x->father = nullptr;
  return meld(root, x);  // 重新合并 x 和根节点
}
这道题要维护大根堆,那是不是我根本就无法用配对堆来写?求调,感谢!

回复

2 条回复,欢迎继续交流。

正在加载回复...